【算法康复训练③】剑指offer P3

文章目录

复习次数（0）

35. 包含min函数的栈

剑指 Offer 30. 包含min函数的栈 2022.7.26

class MinStack {
    Stack<Integer> sk = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
        sk.push(x);
    }
    
    public void pop() {
        if (minStack.peek().equals(sk.peek())) {
            minStack.pop();
        }
        sk.pop();
    }
    
    public int top() {
        return sk.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

36. 字符串的排列

剑指 Offer 38. 字符串的排列 2022.7.26

力扣算法 Java 刷题笔记【回溯算法篇 DFS】hot100（一）全排列、子集、组合 4

class Solution {
    public String[] permutation(String s) {
        permutaUnique(s.toCharArray());
        String[] arr = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }

        return arr;
    }

    List<String> res = new LinkedList<>();
    boolean[] used;
    StringBuilder track = new StringBuilder();

    public List<String> permutaUnique(char[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    void backtrack(char[] nums) {
        if (track.length() == nums.length) {
            res.add(track.toString());
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i] == true) {
                continue;
            }

            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            track.append(nums[i]);
            used[i] = true;
            backtrack(nums);
            track.deleteCharAt(track.length() - 1);
            used[i] = false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

37. 二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表 2022.7.26

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        traverse(root);
        head.left = pre;
        pre.right = head;

        return head;
    }

    void traverse(Node root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        if (pre == null) {
            head = root;
        } else {
            pre.right = root;
            root.left = pre;
        }
        pre = root;
        traverse(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

38. 0～n-1中缺失的数字

剑指 Offer 53 - II. 0～n-1中缺失的数字 2022.7.26

力扣算法 Java 刷题笔记【数组篇二分搜索】hot100（一）二分查找、搜索插入位置、在排序数组中查找元素的第一个和最后一个位置 3

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) {
               right = mid - 1;
            } else {
               left = mid + 1;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

39. 旋转数组的最小数字【高频】

剑指 Offer 11. 旋转数组的最小数字 2022.7.26

class Solution {
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            if (numbers[l] < numbers[r]) {
                return numbers[l];
            }

            int mid = l + (r - l) / 2;
            if (numbers[mid] > numbers[l]) {
                l = mid + 1;
            } else if (numbers[mid] < numbers[l]) {
                r = mid;
            } else {
                l++;
            }
        }

        return numbers[l];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

40. 不用加减乘除做加法

剑指 Offer 65. 不用加减乘除做加法 2022.7.27

class Solution {
    public int add(int a, int b) {
        if(a == 0 || b == 0) {
            return a == 0 ? b : a;
        }
        // 设 a = 1001
        // 设 b = 0101
        // 求和 1100
        int sum = a ^ b;
        // 进位 0001 << 1 = 0010
        int carry = (a & b) << 1;
        // add(1100, 0010)
        return add(sum, carry);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

41. 剪绳子

剑指 Offer 14- I. 剪绳子 2022.7.28

class Solution {
    public int cuttingRope(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        int res = n / 3;
        int mod = n % 3;
        if (n % 3 == 0) {
            return (int)Math.pow(3, res);
        } else if (n % 3 == 1) {
            return (int)(Math.pow(3, res - 1) * 4); 
        } else {
            return (int)(Math.pow(3, res) * 2);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

42. 剪绳子 II

剑指 Offer 14- II. 剪绳子 II 2022.7.28

class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        int res = n / 3;
        int mod = n % 3;
        int p = 1000000007;

        if (mod == 0) {
            return (int)(pow(3, res));
        } else if (mod == 1) {
            return (int)(pow(3, res - 1) * 4 % p);
        } else {
            return (int)(pow(3, res) * 2 % p);
        }
    }

    long pow (int a, int n) {
        long sum = 1;
        int p = 1000000007;
        for (int i = 0; i < n; i++) {
            sum = sum * a % p;
        }
        return sum;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

43. 二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列 2022.7.28

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verify(postorder, 0, postorder.length - 1);
    }

    boolean verify(int[] postorder, int start, int end) {
        if (start >= end) {
            return true;
        }
        int p = start;
        while (postorder[p] < postorder[end]) {
            p++;
        }
        int m = p;
        while (postorder[m] > postorder[end]) {
            m++;
        }
        return m == end && verify(postorder, start, p - 1) && verify(postorder, p, m - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

44. 第一个只出现一次的字符

剑指 Offer 50. 第一个只出现一次的字符 2022.7.28

class Solution {
    public char firstUniqChar(String s) {

        int[] nums = new int[26];
        for (int i = 0; i < s.length(); i++) {
            nums[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (nums[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

45. 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径 2022.7.28


class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return res;
        }
        dfs(root, target, new LinkedList<>());
        return res;
    }

    void dfs(TreeNode root, int sum, LinkedList<Integer> path) {
        if (root == null) {
            return;
        }
        
        sum = sum - root.val;

        if (root.left == null && root.right == null) {
            if (sum == 0) {
                path.addLast(root.val);
                res.add(new LinkedList<>(path));
                path.removeLast();
            }
            return;
        }

        path.addLast(root.val);
        dfs(root.left, sum, path);
        path.removeLast();

        path.addLast(root.val);
        dfs(root.right, sum, path);
        path.removeLast();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

46. 在排序数组中查找数字 I

剑指 Offer 53 - I. 在排序数组中查找数字 I 2022.7.29

力扣算法 Java 刷题笔记【数组篇二分搜索】hot100（一）二分查找、搜索插入位置、在排序数组中查找元素的第一个和最后一个位置 3

class Solution {
    public int search(int[] nums, int target) {
        int left_index = left_bound(nums, target);
        if (left_index == -1) {
            return 0;
        }
        int right_index = right_bound(nums, target);
        return right_index - left_index + 1;
    }

    int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid - 1;
            }
        }

        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                left = mid + 1;
            }
        }

        if (right < 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

47. 最小的k个数

剑指 Offer 40. 最小的k个数 2022.7.29

力扣算法 Java 刷题笔记【快速排序】hot100（一）快速排序快速选择算法 1

方法一：优先队列

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int[] res = new int[k];
        int i = 0;
        for (int a : arr) {
            pq.offer(a);
            if (pq.size() > arr.length - k) {
                res[i] = pq.poll();
                i++;
            }
        }
        return res;
    }
}

******** 另一种写法
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
        
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

方法二：快排

48. 数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字 2022.7.29
摩尔投票法（对拼消耗）

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candicate = 0;
        for (int num : nums) {
            if (count == 0) {
                candicate = num;
            }
            count += candicate == num ? 1 : -1;
        }
        return candicate;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

相关阅读:
速来围观，17个运维实用技巧
 dreamweaver作业静态HTML网页设计——家乡海南旅游网站
 java学习第160天，javaWeb学习第20天，p217-221（06/29）
推荐10个堪称神器的 Java 学习网站
 学习笔记17--汽车运动控制理论之现代控制理论
 RNA-Seq 笔记 [4]
tauri+vue开发小巧的跨OS桌面应用-股票体检
 docker之数据卷(Data Volumes)&dockerfile
MQ消息队列--RabbitMQ的简单入门，在SpringBoot环境
 【Spring-5.1】AbstractAutowireCapableBeanFactory#createBeanInstance实例化对象
原文地址：https://blog.csdn.net/weixin_46644403/article/details/125985298