title: leetcode-剑指offer
date: 2020-12-25 16:10:37
tags: [“剑指offer”]
categories: [“剑指offer”]
description: 剑指offer刷题记录
top_img: “https://s3.ax1x.com/2020/12/25/rW8p8A.jpg“
cover: “https://s3.ax1x.com/2020/12/25/rW8p8A.jpg“
typora-root-url: ..

数组中重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findRepeatNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums) {
            if(map.containsKey(num)) {
                return num;
            } else {
                map.put(num,1);
            }
        }
        return -1;
    }
}

二维数组中的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        return dfs(matrix, target, 0, matrix[0].length - 1);
    }

    private boolean dfs(int[][] matrix, int target, int i, int j) {
        if (i >= matrix.length || j < 0) {
            return false;
        }
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] < target) {
            return dfs(matrix, target, i + 1, j);
        } else  {
            return dfs(matrix, target, i, j - 1);
        }
    }
}

替换空格

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ' '){
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        ListNode rev = null;
        int n = 0;
        while (cur != null) {
            // 双指针翻转链表
            ListNode temp = cur.next;
            cur.next = rev;
            rev = cur;
            cur = temp;
            n++;

        }
        int[] res = new int[n];
        int i = 0;
        while (i < n) {
            res[i] = rev.val;
            i++;
            rev = rev.next;
        }
        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
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> indexMap = new HashMap<>();
        int len = preorder.length;
        for (int i = 0; i < len; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode root = getTree(preorder, 0, len - 1, inorder, 0, len - 1, indexMap);
        return root;
    }

    private TreeNode getTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> indexMap) {
        if (preStart > preEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        if (preStart == preEnd) {
            return root;
        } else {
            //还有子树
            int rootIndex = indexMap.get(rootVal);
            int leftNodes = rootIndex - inStart, rightNodes = inEnd - rootIndex;
            TreeNode leftSubTree = getTree(preorder, preStart + 1, preStart + leftNodes, inorder, inStart, rootIndex - 1, indexMap);
            TreeNode rightSubeTree = getTree(preorder, preEnd - rightNodes + 1, preEnd, inorder, rootIndex + 1, inEnd, indexMap);
            root.left = leftSubTree;
            root.right = rightSubeTree;
            return root;
        }
    }
}

用两个栈实现队列

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
class CQueue {
    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void appendTail(int value) {
        stack1.add(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()) {
            if(stack1.isEmpty()) {
                return -1;
            } else {
                while(!stack1.isEmpty()) {
                    stack2.add(stack1.pop());
                }
                return stack2.pop();
            }
        }else {
            return stack2.pop();
        }
    }
}

青蛙跳台阶问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numWays(int n) {
        if(n <= 1) {
            return 1;
        }
        int pre = 1;
        int cur = 1;
        for(int i = 2; i <= n; i++) {
            int temp = cur;
            cur = (pre + cur) % 1000000007;
            pre = temp;
        }
        return cur;
    }
}

旋转数组的最小数字

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

矩阵中的路径

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
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        boolean[][] vis = new boolean[board.length][board[0].length];
        char[] chars = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == chars[0]) {
                    if(dfs(board,i,j,vis,chars,0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, int i, int j, boolean[][] vis, char[] chars, int index) {
        //终止条件
        if(i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] != chars[index] || vis[i][j]) {
            return false;
        }
        if(index == chars.length - 1) {
            return true;
        }
        vis[i][j] = true;
        boolean res = dfs(board,i + 1, j ,vis,chars,index + 1) 
                    || dfs(board,i - 1, j ,vis, chars,index + 1)
                    || dfs(board,i, j + 1,vis,chars,index + 1)
                    || dfs(board, i, j - 1,vis,chars,index + 1);
        vis[i][j] = false;
        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
class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] vis = new boolean[m][n];
        int res = dfs(m,n,k,0,0,vis);
        return res;
    }
    private int dfs(int m, int n, int k, int i, int j, boolean[][] vis){
        if(i < 0|| i >= m || j < 0 || j >= n || vis[i][j] || (numsCount(i) + numsCount(j)) > k) {
            return 0;
        }
        vis[i][j] = true;
        int res = 1 + dfs(m,n,k,i + 1,j,vis) + dfs(m,n,k,i - 1,j,vis) + dfs(m,n,k,i,j + 1,vis) + dfs(m,n,k,i, j - 1,vis);
        // 不能回溯 从同一个点出发的。
        // vis[i][j] = false;
        return res;
    }
    private int numsCount(int m) {
        int sum = 0;
        while(m > 0) {
            if(m != 0) {
                int b = m % 10;
                sum += b;
                m /= 10;
            }
        }
        return sum;
    }
}

剪绳子

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int cuttingRope(int n) {
       int[] dp = new int[n + 1];
       for(int i = 0;i <= n; i++) {
           int max = 0;
           for(int j = i - 1; j >= 0; j--) {
               max = Math.max(max,Math.max(j * (i - j), j * dp[i - j]));
           }
           dp[i] = max;
       }
       return dp[n];
    }
}

剪绳子 II

尽可能凑3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int cuttingRope(int n) {
        if(n < 4) {
            return n - 1;
        } else if( n == 4) {
            return n;
        }
        long res = 1;
        while(n > 4) {
            res *= 3;
            res %= 1000000007;
            n -= 3; 
        }
        return (int)(res * n % 1000000007);
    }
}

二进制中1的个数

位运算！

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
           res += n & 1;
           n = n >>> 1;
        }
        return res;
    }
}

数值的整数次方

位运算！！

二分快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1 / x;
        if(n % 2 == 0) {
            double t = myPow(x, n / 2);
            return t * t;
        } else {
            double t = myPow(x, n / 2);
            if(n < 0) x =  1 / x;
            return t * t * x;
        }
    }
}

打印从1到最大的n位数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] printNumbers(int n) {
        int size = 10;
        for(int i = 1; i < n; i++) {
            size *= 10;
        }
        int[] res = new int[size - 1];
        for(int i = 0; i < size - 1; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}

调整数组顺序使奇数位于偶数前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] exchange(int[] nums) {
        int temp = 0, left = 0, right = nums.length - 1;
        while(left < right) {
            if(nums[left] % 2 == 1) {
                left++;
            } else if(nums[right] % 2 == 0) {
                right--;
            } else{
                temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }
}

链表中倒数第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode low = head, fast = head;
        for(int i = 1; i < k; i++) {
            fast = fast.next;
        }
        while(fast.next != null) {
            fast = fast.next;
            low = low.next;
        }
        return low;
    }
}

合并两个排序的链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode(-1), pre = newHead;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
                pre = pre.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
                pre = pre.next;
            }
        }
        if(l1 != null) {
            pre.next = l1;
        }
        if(l2 != null) {
            pre.next = l2;
        }
        return newHead.next;
    }
}

树的子结构

两个dfs 对A前序遍历每个节点与b比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    public boolean dfs(TreeNode A, TreeNode B){
        if(B == null) return true;
        if(A == null) return false;
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        mirror(root);
        return root;
    }
    private void mirror(TreeNode root) {
        if(root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirror(root.left);
        mirror(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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return dfs(root.left, root.right);
    }
    private boolean dfs(TreeNode left, TreeNode right) {
        if(left == null && right == null) {
            return true;
        }
        if(left == null || right == null) {
            return false;
        }
        return left.val == right.val && dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}

顺时针打印矩阵

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
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int row = matrix.length;
        if (row == 0) {
            return new int[0];
        }
        int col = matrix[0].length;
        int[] res = new int[row * col];
        int index = 0, left = 0, top = 0, right = col - 1, bottom = row - 1;
        while (true) {
            //从左到右
            for (int i = left; i <= right; i++) {
                res[index++] = matrix[top][i];
            }
            if (++top > bottom) {
                break;
            }
            // 从上到下
            for (int i = top; i <= bottom; i++) {
                res[index++] = matrix[i][right];
            }
            if (--right < left) {
                break;
            }
            // 从右到左
            for (int i = right; i >= left; i--) {
                res[index++] = matrix[bottom][i];
            }
            if (--bottom < top) {
                break;
            }
            // 从下到上
            for (int i = bottom; i >= top; i--) {
                res[index++] = matrix[i][left];
            }
            if (++left > right) {
                break;
            }
        }
        return res;
    }
}

包含min函数的栈

用一个min记录当前最小值

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
49
class MinStack {

    /** initialize your data structure here. */
    private Node head;
    public MinStack() {

    }
    
    public void push(int x) {
       if(head == null){
           head = new Node(x, x);
       } else {
           Node newhead = new Node(x, Math.min(head.min, x));
           newhead.next = head;
           head = newhead;
       }
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int min() {
        return head.min;
    }
    private class Node {
        int val;
        //当前最小值
        int min;
        Node next;
        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

栈的压入、弹出序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        if(n == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        while(i < n && j < n) {
            while(stack.isEmpty() || stack.peek() != popped[j] && i < n) {
                stack.push(pushed[i++]);
            }
            while(!stack.isEmpty() && stack.peek() == popped[j] && j < n) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

从上到下打印二叉树

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

从上到下打印二叉树 II

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

从上到下打印二叉树 III

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        // 0 right 1 left
        int flag = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            flag++;
            LinkedList<Integer> list = new LinkedList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(flag % 2 == 0) {
                    list.addFirst(node.val);
                } else {
                    list.addLast(node.val);
                }
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return isBST(postorder, 0, postorder.length - 1);
    }

    private boolean isBST(int[] postorder, int i, int j) {
        if(i > j) {
            return true;
        }
        int left = i;
        while(postorder[left] < postorder[j]) {
            left++;
        }
        int right = left;
        while(postorder[left] > postorder[j]) {
            left++;
        }
        return left == j && isBST(postorder,i, right - 1) && isBST(postorder, right, j - 1);
    }
}

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

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<>();
        backtrack(root, sum, new ArrayList<>());
        return res;
    }
    private void backtrack(TreeNode root, int sum, List<Integer> list) {
        if(root == null) {
            return;
        }
        
        list.add(root.val);
        sum -= root.val;
        if(sum == 0 && root.left == null && root.right == null){
            // 叶子节点
            res.add(new ArrayList<>(list));
        } else {
            backtrack(root.left, sum, list);
            backtrack(root.right, sum, list);
        }
        sum += root.val;
        list.remove(list.size() - 1);
        
    }
}

复杂链表的复制

hashmap

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return head;
        }
        Map<Node, Node> map = new HashMap<>();
        for(Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        for(Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }
}

构造 拼接和拆分

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return head;
        }
        Node cur = head;
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        cur = head;
        while(cur != null) {
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        cur = head.next;
        Node pre = head, res = head.next;
        while(cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        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
45
46
47
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) {
            return root;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    private void dfs(Node cur) {
        if(cur == null) {
            return;
        }
        // 中序遍历
        dfs(cur.left);
        if(pre == null) {
            head = cur;
        } else {
            pre.right = cur;
        }
        cur.left = pre;
        pre = cur;
        dfs(cur.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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String SEP = ",";
    String NULL = "null";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null) {
            sb.append(NULL).append(SEP);
            return sb.delete(sb.length() - 1, sb.length() - 1).toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node == null) {
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(node.val).append(SEP);
            queue.offer(node.left);
            queue.offer(node.right);
        }
        sb.delete(sb.length() - 1, sb.length() - 1);
        return sb.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()) {
            return null;
        }
        String[] nodes = data.split(SEP);
        if(nodes[0].equals(NULL)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        for(int i = 1; i < nodes.length;) {
            TreeNode parent = queue.poll();
            String left = nodes[i++];
            if(!left.equals(NULL)) {
                parent.left = new TreeNode(Integer.parseInt(left));
                queue.offer(parent.left);
            } else {
                parent.left = null;
            }
            String right = nodes[i++];
            if(!right.equals(NULL)) {
                parent.right = new TreeNode(Integer.parseInt(right));
                queue.offer(parent.right);
            } else {
                parent.right = null;
            }      
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

字符串的排列

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
class Solution {
    List<String> res =  new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    private void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) {
                continue;
            }
            set.add(c[i]);
            swap(i, x);
            dfs(x + 1);
            // 回溯
            swap(i, x);
        }
    }
    private void swap(int a, int b) {
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            if(map.get(nums[i]) > (nums.length / 2)) {
                return nums[i];
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int majorityElement(int[] nums) {
       int count = 0;
       int card = nums[0];
       for(int num : nums) {
           if(count == 0) {
               card = num;
           }
           count += card == num ? 1: -1;
       }
       return card;
    }
}

最小的k个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length == 0 || k == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (o1, o2) -> o1 - o2);
        for(int a : arr) {
            queue.offer(a);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}

数据流中的中位数

image-20210302110141216

保证中位数一直在堆顶

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
class MedianFinder {
    private PriorityQueue<Integer> large;
    private PriorityQueue<Integer> small;
    /** initialize your data structure here. */
    public MedianFinder() {
        large = new PriorityQueue<>();
        small = new PriorityQueue<>((a, b) -> b - a);
    }
    
    public void addNum(int num) {
        if(small.size() >= large.size()) {
            small.offer(num);
            large.offer(small.poll());
        } else {
            large.offer(num);
            small.offer(large.poll());
        }
    }
    
    public double findMedian() {
        if(large.size() > small.size()) {
            return large.peek();
        } else if(large.size() < small.size()) {
            return small.peek();
        }
        return (large.peek() + small.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

连续子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; 
        int res = dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

整数中 1 出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        long i = 1;
        while(n / i != 0) {
            long high = n / (10 * i); //高位
            long cur = (n / i) % 10;
            long low = n - (n / i) * i;
            if(cur == 0) {
                count += high * i;
            } else if (cur == 1) {
                count += high * i + (low + 1);
            } else {
                count += (high + 1) * i;
            }
            i *= 10;
        }
        return count;
    }
}

数字序列中某一位的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while(n > count) {
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0'; 
    }
}

把数组排成最小的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String minNumber(int[] nums) {
        List<String> list = new ArrayList<>();
        for (int num : nums) {
            list.add(new Integer(num).toString());
        }
        list.sort(((o1, o2) -> (o1 + o2).compareTo(o2 + o1)));
        StringBuilder stringBuilder = new StringBuilder();
        for (String s : list) {
            stringBuilder.append(s);
        }
        return stringBuilder.toString();
    }
}

把数字翻译成字符串

Picture1.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int translateNum(int num) {
        String numStr = String.valueOf(num);
        char[] numChar = numStr.toCharArray();
        int n = numChar.length;
        int[] dp = new int[n];
        dp[0] = 1;
        if (num < 10) {
            return 1;
        }
        dp[1] = 1 + (numChar[0] == '1' || (numChar[0] == '2' && numChar[1] <= '5') ? 1 : 0);
        for (int i = 2; i < n; i++) {
            if(numChar[i - 1] == '1' || (numChar[i - 1] == '2' && numChar[i] <= '5')) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.println(dp[i]);
        }
        return dp[n - 1];
    }
}

礼物的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];
        //base case
        dp[0][0] = grid[0][0];
        for(int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }
}

公平的糖果棒交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        int delta = (sumA - sumB) / 2;
        Set<Integer> set = new HashSet<>();
        for(int a : A) {
            set.add(a);
        }
        for(int b : B) {
            if(set.contains(b + delta)) {
                return new int[]{b + delta, b};
            }
        }
        return new int[]{-1, -1};
    }
}

最长不含重复字符的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0, valid = 0, res = 0;
        while(right < s.length()) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                window.put(d, window.get(d) - 1);
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}

丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int nthUglyNumber(int n) {
        int p2 = 0, p3 = 0, p5 = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
            if (dp[i] == dp[p2] * 2) {
                p2++;
            }
            if (dp[i] == dp[p3] * 3) {
                p3++;
            }
            if (dp[i] == dp[p5] * 5) {
                p5++;
            }
        }
        return dp[n - 1];
    }
}

第一个只出现一次的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
}

数组中的逆序对

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
class Solution {
    public int reversePairs(int[] nums) {
        return merge(nums, 0, nums.length - 1);
    }

    private int merge(int[] arr, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        int count = merge(arr, start, mid) + merge(arr, mid + 1, end);
        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            count += arr[i] <= arr[j] ? 0 : mid + 1 - i;
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= end) {
            temp[k++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, start, end - start + 1);
        return count;
    }
}

两个链表的第一个公共节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode head1 = headA, head2 = headB;
        int num1 = 0, num2 = 0;
        while (head1 != null) {
            num1++;
            head1 = head1.next;
        }
        while (head2 != null) {
            num2++;
            head2 = head2.next;
        }
        int abs = Math.abs(num1 - num2);
        if (num1 > num2) {
            while (abs-- > 0) {
                headA = headA.next;
            }
        } else {
            while (abs-- > 0) {
                headB = headB.next;
            }
        }
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode head1 = headA, head2 = headB;
        while (head1 != head2) {
            head1 = head1 != null ? head1.next : headB;
            head2 = head2 != null ? head2.next : headA;
        }
        return head1;
    }
}

在排序数组中查找数字 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        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;
            }
        }
        int res = 0;
        while (left < nums.length && nums[left] == target) {
            res++;
            left++;
        }
        return res;
    }
}

0～n-1中缺失的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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) {
                if (mid == 0 || nums[mid - 1] == mid - 1) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

二叉搜索树的第k大节点

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int target;
    private int res;
    public int kthLargest(TreeNode root, int k) {
        target = k;
        dfs(root);
        return res;
    }
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        target--;
        if (target == 0) {
            res = root.val;
            return;
        }
        dfs(root.left);
    }
}

二叉搜索树的第k大节点

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int target;
    private int res;
    public int kthLargest(TreeNode root, int k) {
        target = k;
        dfs(root);
        return res;
    }
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        target--;
        if (target == 0) {
            res = root.val;
            return;
        }
        dfs(root.left);
    }
}

二叉树的深度

1
2
3
4
5
6
7
8
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isBalanced(root.left) && isBalanced(root.right) && Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1;
    }
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

数组中数字出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] singleNumbers(int[] nums) {
        int k = 0;
        for (int num : nums) {
            k ^= num;
        }
        int mask = 1;
        while ((k & mask) == 0) {
            mask <<= 1;
        }
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

数组中数字出现的次数 II

和为s的两个数字

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

和为s的连续正数序列

1.滑动窗口

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
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int left = 1, right = 1, sum = 0;
        while (right < target) {
            sum += right;
            while (sum > target) {
                sum -= left++;
            }
            if (sum == target) {
                int[] temp = new int[right - left + 1];
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = i + left;
                }
                list.add(temp);
            }
            right++;
        }
        int[][] res = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

2.数学

如果有两个连续的数之和等于target，那么相差为1， (target - 1) % 2 == 0， 且数组一定是从 (target - 1) / 2开始的，数组的元素就是2个；如果是3个连续的数组，那么三个数之间相差为1、2，(target - 1 - 2) % 3 == 0，且数组一定是从 (target - 1 - 2) / 3开始的，数组元素是3个，依次类推，但是注意target必须是大于0的数，且res需要倒序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int i = 1;
        while (target > 0) {
            target -= i++;
            if (target > 0 && target % i == 0) {
                int[] temp = new int[i];
                for (int j = 0; j < i; j++) {
                    temp[j] = target / i + j;
                }
                list.add(temp);
            }
        }
        Collections.reverse(list);
        int[][] res = new int[list.size()][];
        for (int j = 0; j < list.size(); j++) {
            res[j] = list.get(j);
        }
        return res;
    }
}

翻转单词顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String reverseWords(String s) {
        String[] strings = s.strip().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = strings.length - 1; i >= 0; i--) {
            if (strings[i].equals("")) {
                continue;
            }
            if (i == 0) {
                stringBuilder.append(strings[i]);
            } else {
                stringBuilder.append(strings[i]).append(" ");
            }
        }
        return stringBuilder.toString();
    }
}

左旋转字符串

1
2
3
4
5
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n) + s.substring(0, n);
    }
}

滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        int left = 0, right = k - 1;
        int[] res = new int[nums.length - k + 1];
        int i = 0;
        while (right < nums.length) {
            int max = nums[left];
            for (int j = left + 1; j <= right; j++) {
                max = Math.max(max, nums[j]);
            }
            res[i++] = max;
            left++;
            right++;
        }
        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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        for (int i = k; i < nums.length; i++) {
            if (deque.peekFirst() == nums[i - k]) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            res[i - k + 1] =deque.peekFirst();
        }
        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
class MaxQueue {
    // 储存数据的队列
    Queue<Integer> queue;
    // 储存最大值
    Deque<Integer> deque;
    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    
    public int max_value() {
        if (deque.isEmpty()) {
            return -1;
        } else {
            return deque.peekFirst();
        }
    }
    
    public void push_back(int value) {
        while (!deque.isEmpty() && deque.peekLast() < value) {
            deque.removeLast();
        }
        deque.addLast(value);
        queue.offer(value);
    }
    
    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        int q = queue.poll();
        if (q == deque.peekFirst()) {
            deque.removeFirst();
        }
        return q;
    }
}

n个骰子的点数

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
class Solution {
    public double[] dicesProbability(int n) {
        /**
         * (n,s)  = (n - 1, s-1) + (n-1 ,s-2)+...+(n-1,s-5)
         * dp[i][j] ，表示投掷完 i枚骰子后，点数 j 的出现次数
         */
        if (n == 1) {
            return new double[]{0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667};
        }
        int[][] dp = new int[n + 1][6 * n + 1];
        double[] res = new double[5 * n + 1];

        // base case
        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= 6 * n; j++) {
                dp[i][j] = dp[i - 1][j - 1];
                int k = 1;
                while (k <= 5) {
                    k++;
                    if (j - k < 1) {
                        break;
                    }
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        int[] dp2 = Arrays.copyOfRange(dp[n], n, 6 * n + 1);
        double sum = 0;
        for (int i : dp2) {
            sum += i;
        }
        for (int i = 0; i < res.length; i++) {
            res[i] = dp2[i] / sum;
        }
        return res;
    }
}

扑克牌中的顺子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int zeros = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) {
                zeros++;
                continue;
            } else {
                if (nums[i] == nums[i + 1]) {
                    return false;
                } else {
                    zeros -= nums[i + 1] - nums[i] - 1;
                }
            }
        }
        return zeros >= 0;
    }
}

圆圈中最后剩下的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }
}

股票的最大利润

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, -prices[i]);
        }
        return dp_0;
    }
}

求1+2+…+n

1
2
3
4
5
6
7
8
class Solution {
    public int sumNums(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumNums(n - 1);
    }
}

不用加减乘除做加法

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

构建乘积数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] constructArr(int[] a) {
        int[] res = new int[a.length];
        for (int i = 0, sum = 1; i < a.length; sum *= a[i], i++) {
            res[i] = sum;
        }

        for (int i = a.length - 1, sum = 1; i >= 0; sum *= a[i], i--) {
            res[i] *= sum;
        }
        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
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public int strToInt(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int index = 0;
        while (index < str.length() && str.charAt(index) == ' ') {
            index++;
        }
        int flag = 0;
        if (index >= str.length()) {
            return 0;
        }

        if (str.charAt(index) == '-') {
            flag = 1;
            index++;
        } else if (str.charAt(index) == '+') {
            flag = 0;
            index++;
        }
        if (index >= str.length() || str.charAt(index) < '0' || str.charAt(index) > '9') {
            return 0;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int wei = -1;
        for (int i = index; i < str.length(); i++) {
            if (str.charAt(i) > '9' || str.charAt(i) < '0') {
                break;
            }
            stringBuilder.append(str.charAt(i));
            wei++;
        }
        if (stringBuilder.length() == 0) {
            return 0;
        }
        double res = 0;
        for (int i = 0; i < stringBuilder.length(); i++) {
            res += (stringBuilder.charAt(i) - '0') * Math.pow(10, wei);
            wei--;
        }
        if (res > Integer.MAX_VALUE) {
            if (flag == 0) {
                return Integer.MAX_VALUE;
            } else {
                return Integer.MIN_VALUE;
            }
        }
        if (flag == 0) {
            return (int) res;
        } else {
            return (int) (0 - res);
        }
    }
}

二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }
}

二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        } else {
            return null;
        }
    }
}