Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

剑指offer-刷题记录

Posted on Edited on In ,
Symbols count in article: 42k Reading time ≈ 38 mins.

数组中重复的数字

最简单的用set判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findRepeatNumber(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    Set<Integer> set = new HashSet<>();
    for (int x : nums) {
        if (!set.contains(x)) {
            set.add(x);
        } else {
            return x;
        }
    }
    return -1;
}

官方题解，交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findRepeatNumber(int[] nums) {
    int temp;
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i){
            if (nums[i] == nums[nums[i]]){
                return nums[i];
            }
            temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return -1;
}

当然也可以排序后遍历，或者用新数组做桶标记。

二维数组中的查找

找对位置从左上角开始，大则左，小则下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    int row = matrix.length;
    int col = matrix[0].length;
    int x = 0 , y = col - 1;
    int temp;
    while (x < row && y >= 0) {
        temp = matrix[x][y];
        if (temp == target) {
            return true;
        } else if (temp > target) {
            y--;
        } else {
            x++;
        }
    }
    return false;
}

替换空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String replaceSpace(String s) {
    if (s == null || s.length() == 0) {
        return s;
    }
    final String space = "%20";
    final char[] arr = s.toCharArray();
    StringBuilder sb = new StringBuilder();
    for(char c : arr) {
        if (c != ' ') {
            sb.append(c);
        } else {
            sb.append(space);
        }
    }
    return sb.toString();
}

从头到尾打印链表

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] reversePrint(ListNode head) {
    if (head == null) {
        return new int[0];
    }
    List<Integer> list = new ArrayList<>();
    while (head != null) {
        list.add(head.val);
        head = head.next;
    }
    Collections.reverse(list);
    int[] ans = new int[list.size()];
    for(int i = 0 ; i < list.size() ; i++){
        ans[i] = list.get(i);
    }
    return ans;
}

当然也可以考虑先直接将链表倒序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] reversePrint(ListNode head) {
    if(head==null){
        return new int[]{};
    }
    int count = 0;
    ListNode pre = null;
    ListNode node = null;
    while(head!=null){
        count++;
        node = head.next;
        head.next = pre;
        pre = head;
        head=node;
    }
    head=pre;
    int[] res = new int[count];
    for(int i=0;i<count;i++){
        res[i] = head.val;
        head = head.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
HashMap<Integer,Integer> map = new HashMap<>();
int[] pre,in;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0 ; i < inorder.length ; ++i) {
        map.put(inorder[i],i);
    }
    this.in = inorder;
    this.pre = preorder;
    return helper(0,pre.length,0,inorder.length);
}

private TreeNode helper(int pS,int pE,int iS,int iE) {
    if (pE == pS) {
        return null;
    }
    TreeNode root = new TreeNode(pre[pS]); //根节点
    int rootIndex = map.get(pre[pS]); //中序遍历根节点
    int left = rootIndex - iS;
    root.left = helper(pS + 1,pS + left + 1,iS,rootIndex);
    root.right = helper(pS + 1 + left,pE,rootIndex + 1,iE);
    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // 下面四行代码其实就是把数组转换成list
        List<Integer> pre = new ArrayList();
        for(int i : preorder) pre.add(i);
        List<Integer> in = new ArrayList();
        for(int i : inorder) in.add(i);

        //其实这个函数就这一行
        return f(pre,in);
    }

    TreeNode f(List pre, List in){
        // 递归停止条件，就是遍历完了列表
	    if(pre.size() == 0) return null;

        // 前序遍历的第一个，一定是root呀
        int val = (int) pre.get(0);
	    TreeNode root = new TreeNode(val);

        // 从中序遍历里面找到root的位置，酒吧中序遍历分成两部分了
	    int index = in.indexOf(root.val);

        //别问 问就是递归
	    root.left = f(pre.subList(1,1+index), 
                        in.subList(0,index));
	    root.right = f(pre.subList(1+index, pre.size()), 
                        in.subList(1+index, in.size()) );
	    return root;
	}
}

作者：acnesu

用两个栈实现队列

一个栈用来入队，一个用来出队

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 {

    Stack<Integer> s1;
    Stack<Integer> s2;

    public CQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void appendTail(int value) {
        s1.push(value);
    }

    public int deleteHead() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        if (s2.empty()){
            return -1;
        } else {
            return s2.pop();
        }
    }
}

斐波纳契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int fib(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    int fo = 0, f1 = 1;
    int ans = 1;
    for (int i = 2 ; i <= n ; i++){
        ans = (fo + f1) % 1000000007 ;
        fo = f1;
        f1 = ans;
    }
    return ans;
}

跳台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
public int numWays(int n) {
    if (n < 2) {
        return 1;
    }
    int fo = 1, f1 = 2;
    int ans = 2;
    for (int i = 2 ; i < n ; i++){
        ans = (fo + f1) % 1000000007 ;
        fo = f1;
        f1 = ans;
    }
    return ans;
}

旋转数组

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

矩阵中的路径

DFS

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
private char[] ss ;
private int col;
private int row;
private char[][] board;
public boolean exist(char[][] board, String word) {
    ss = word.toCharArray();
    this.col = board.length;
    this.row = board[0].length;
    this.board = board;
    for (int i = 0 ; i < col ; ++i) {
        for (int j = 0 ; j < row ; ++j) {
            if (helper(i,j,0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean helper(int i,int j,int k) {
    if (i >= col || i < 0 || j >= row || j < 0 || board[i][j] != ss[k]) {
        return false;
    }
    if (k == ss.length - 1) {
        return true;
    }
    char temp = board[i][j];
    board[i][j] = '#';
    boolean check = helper(i + 1, j, k + 1) || helper(i - 1, j, k + 1) ||
            helper(i, j + 1, k + 1) ||helper(i , j - 1, k + 1);
    board[i][j] = temp;
    return check;
}

机器人的运动范围

DFS

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
private int counts = 0;
private boolean[][] visited;
public int movingCount(int m, int n, int k) {
    visited = new boolean[m][n];
    helper(0,0,m,n,k);
    return counts;
}

private void helper(int x,int y,int m,int n,int k) {
    if (x >= m || x < 0 || y >= n || y < 0 || calLimit(x, y) > k || visited[x][y]) {
        return;
    }
    counts++;
    visited[x][y] = true;
    helper(x + 1,y,m,n,k);
    helper(x - 1,y,m,n,k);
    helper(x,y + 1,m,n,k);
    helper(x,y - 1,m,n,k);
}

private int calLimit(int x,int y) {
    int ans = 0;
    while (x > 0) {
        ans += x % 10;
        x /= 10;
    }
    while (y > 0) {
        ans += y % 10;
        y /= 10;
    }
    return ans;
}

题解里的优化点：

数位之和计算：

image-20200902215909217

1
(x + 1) % 10 != 0 ? s_x + 1 : s_x - 8
搜索方向简化：

  • 数位和特点： 根据数位和增量公式得知，数位和每逢 进位 突变一次。

  • 解的三角形结构：

    • 根据数位和特点，矩阵中 满足数位和的解 构成的几何形状形如多个 等腰直角三角形 ，每个三角形的直角顶点位于 0, 10, 20, …0,10,20,… 等数位和突变的矩阵索引处 。
    • 三角形内的解虽然都满足数位和要求，但由于机器人每步只能走一个单元格，而三角形间不一定是连通的，因此机器人不一定能到达，称之为 不可达解 ；同理，可到达的解称为 可达解 （本题求此解） 。

  • 结论：

    根据可达解的结构，易推出机器人可

    仅通过向右和向下移动，访问所有可达解。

    • 三角形内部： 全部连通，易证；
    • 两三角形连通处： 若某三角形内的解为可达解，则必与其左边或上边的三角形连通（即相交），即机器人必可从左边或上边走进此三角形。

剪绳子

1
2
3
4
5
6
7
8
9
10
11
12
public int cuttingRope(int n) {
    if (n <= 3) {
        return n - 1;
    }
    long a = 1;
    while(n > 4){
        n = n - 3;
        a = a * 3;
        a = a % 1000000007;
    }
    return (int) (a * n % 1000000007);
}

二进制数中一的个数

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
    int ans = 0;
    while (n != 0) {
        ans++;
        n &= n - 1;
    }
    return ans;
}

数值的整次方

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public double myPow(double x, int n) {
    if (x == 0) {
        return 0;
    }
    long b = n;
    double ans = 1.0;
    if (b < 0) {
        x = 1 / x;
        b = -b;
    }
    while (b > 0) {
        if (b % 2 == 1) {
            ans *= x;
        }
        x *= x;
        b >>= 1;
    }
    return ans;
}

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

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[] exchange(int[] nums) {
    if (nums == null || nums.length == 0) {
        return nums;
    }
    int len = nums.length;
    int left = 0 , right = len - 1;
    while (left < right) {
        while (left < len && nums[left] % 2 == 1) {
            left++;
        }
        while (right >= 0 && nums[right] % 2 == 0) {
            right--;
        }
        if (left >= right) {
            break;
        }
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        right--;
        left++;
    }
    return nums;
}

合并链表

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
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode dummy = new ListNode(-1);
    ListNode head = dummy;
    int v1,v2;
    while (l1 != null && l2 != null) {
        v1 = l1.val;
        v2 = l2.val;
        if (v1 <= v2) {
            head.next = l1;
            l1 = l1.next;
        } else {
            head.next = l2;
            l2 = l2.next;
        }
        head = head.next;
    }
    if (l2 != null) {
        head.next = l2;
    } else if (l1 != null) {
        head.next = l1;
    }
    return dummy.next;
}

树的子结构

递归

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null) {
        return false;
    }
    return  (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

private boolean recur(TreeNode A, TreeNode B) {
    if(B == null) return true;
    if(A == null || A.val != B.val) return false;
    return recur(A.left, B.left) && recur(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
public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null) {
        return false;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(A);
    TreeNode temp;
    while (!queue.isEmpty()) {
        temp = queue.poll();
        if (temp.left != null) {
            queue.add(temp.left);
        }
        if (temp.right != null) {
            queue.add(temp.right);
        }
        if (temp.val == B.val) {
            boolean ans = recur(temp,B);
            if (ans) {
                return ans;
            }
        }
    }
    return false;
}

二叉树的镜像

1
2
3
4
5
6
7
8
9
public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode z = root.left;
    root.left = mirrorTree(root.right);
    root.right = mirrorTree(z);
    return root;
}

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        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
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root.left);
    queue.add(root.right);
    TreeNode left,right;
    while (!queue.isEmpty()) {
        left = queue.poll();
        right = queue.poll();
        if (left != null && right != null && right.val == left.val) {
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        } else if (left == null && right == null) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}

递归

1
2
3
4
5
6
7
8
public boolean isSymmetric(TreeNode root) {
    return root == null ? true : recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
    if(L == null && R == null) return true;
    if(L == null || R == null || L.val != R.val) return false;
    return recur(L.left, R.right) && recur(L.right, R.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
private static final int[] dx = new int[]{0,1,0,-1};
private static final int[] dy = new int[]{1,0,-1,0};
public int[] spiralOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return new int[0];
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    int counts = 0 ,end = rows * cols,dir = 0;
    int x = 0, y = 0;
    int[] ans = new int[end];
    while (counts < end) {
        ans[counts] = matrix[x][y];
        matrix[x][y] = Integer.MIN_VALUE;
        counts++;
        //在范围内，且数字没有修改过
        if (!inRange(x,y,dir,rows,cols) && matrix[x + dx[dir]][y + dy[dir]] != Integer.MIN_VALUE) {
            x += dx[dir];
            y += dy[dir];
        } else {
            dir++;
            dir %= 4;
            x += dx[dir];
            y += dy[dir];
        }
    }
    return ans;
}

private boolean inRange(int x , int y,int k,int row,int col) {
    int ddx = x + dx[k], ddy = y + dy[k];
    boolean ans = ddx >= row || ddx < 0 || ddy >= col || ddy < 0;
    return ans;
}
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
public int[] spiralOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return new int[0];
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[] ans = new int[rows * cols];
    int top = 0, down = rows - 1 , left = 0,right = cols - 1,count = 0;
    while (true) {
        for (int i = left; i <= right ; ++i) {
            ans[count++] = matrix[top][i];
        }
        if (++top > down) {
            break;
        }
        for (int i = top ; i <= down ; ++i){
            ans[count++] = matrix[i][right];
        }
        if (--right < left) {
            break;
        }
        for (int i = right ; i >= left ; --i) {
            ans[count++] = matrix[down][i];
        }
        if(--down < top) {
            break;
        }
        for (int i = down;i >= top ; --i) {
            ans[count++] = matrix[i][left];
        }
        if (++left > right) {
            break;
        }
    }
    return ans;
}

栈的压入与弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int index = 0 , len = pushed.length;
    for (int num : pushed) {
        stack.push(num);
        //模拟出栈过程
        while (!stack.empty() && stack.peek() == popped[index]) {
            stack.pop();
            index++;
        }
    }
    return stack.empty();
}

链表中倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head,slow = head;
    while (fast != null && k > 0) {
        fast = fast.next;
        k--;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode pre = null, cur = head,next = null;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

合并两个排序链表

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
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode dummy = new ListNode(-1);
    ListNode head = dummy;
    int v1,v2;
    while (l1 != null && l2 != null) {
        v1 = l1.val;
        v2 = l2.val;
        if (v1 <= v2) {
            head.next = l1;
            l1 = l1.next;
        } else {
            head.next = l2;
            l2 = l2.next;
        }
        head = head.next;
    }
    if (l2 != null) {
        head.next = l2;
    } else if (l1 != null) {
        head.next = l1;
    }
    return dummy.next;
}

树的子结构

递归

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null) {
        return false;
    }
    return  (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

private boolean recur(TreeNode A, TreeNode B) {
    if(B == null) return true;
    if(A == null || A.val != B.val) return false;
    return recur(A.left, B.left) && recur(A.right, B.right);
}

二叉树的镜像

注意是镜像复制，所以left复制的是right，right复制的是left

1
2
3
4
5
6
7
8
9
public TreeNode mirrorTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode z = root.left;
    root.left = mirrorTree(root.right);
    root.right = mirrorTree(z);
    return root;
}

对称的二叉树

按照层序遍历，最开始直接加入根节点的左右子树，之后判断左右子树的4个子节点是否对称，加入队列时要注意顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root.left);
    queue.add(root.right);
    TreeNode left,right;
    while (!queue.isEmpty()) {
        left = queue.poll();
        right = queue.poll();
        if (left != null && right != null && right.val == left.val) {
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        } else if (left == null && right == null) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}

顺时针打印矩阵

憨批写法

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
private static final int[] dx = new int[]{0,1,0,-1};
private static final int[] dy = new int[]{1,0,-1,0};
public int[] spiralOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return new int[0];
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    int counts = 0 ,end = rows * cols,dir = 0;
    int x = 0, y = 0;
    int[] ans = new int[end];
    while (counts < end) {
        ans[counts] = matrix[x][y];
        matrix[x][y] = Integer.MIN_VALUE;
        counts++;
        //在范围内，且数字没有修改过
        if (!inRange(x,y,dir,rows,cols) && matrix[x + dx[dir]][y + dy[dir]] != Integer.MIN_VALUE) {
            x += dx[dir];
            y += dy[dir];
        } else {
            dir++;
            dir %= 4;
            x += dx[dir];
            y += dy[dir];
        }
    }
    return ans;
}

private boolean inRange(int x , int y,int k,int row,int col) {
    int ddx = x + dx[k], ddy = y + dy[k];
    boolean ans = ddx >= row || ddx < 0 || ddy >= col || ddy < 0;
    return ans;
}

题解4轮遍历

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
public int[] spiralOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return new int[0];
    }
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[] ans = new int[rows * cols];
    int top = 0, down = rows - 1 , left = 0,right = cols - 1,count = 0;
    while (true) {
        for (int i = left; i <= right ; ++i) {
            ans[count++] = matrix[top][i];
        }
        if (++top > down) {
            break;
        }
        for (int i = top ; i <= down ; ++i){
            ans[count++] = matrix[i][right];
        }
        if (--right < left) {
            break;
        }
        for (int i = right ; i >= left ; --i) {
            ans[count++] = matrix[down][i];
        }
        if(--down < top) {
            break;
        }
        for (int i = down;i >= top ; --i) {
            ans[count++] = matrix[i][left];
        }
        if (++left > right) {
            break;
        }
    }
    return ans;
}

最小栈

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

        Stack<Integer> min;
        Stack<Integer> stack;

        /** initialize your data structure here. */
        public MinStack() {
            min = new Stack<>();
            stack = new Stack<>();
        }

        public void push(int x) {
            stack.push(x);
            if (min.empty() || min.peek() >= x) {
                min.push(x);
            }
        }

        public void pop() {
            if (stack.pop().equals(min.peek())) {
                min.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int min() {
            return min.peek();
        }
    }

栈的压入与弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int index = 0 , len = pushed.length;
    for (int num : pushed) {
        stack.push(num);
        //模拟出栈过程
        while (!stack.empty() && stack.peek() == popped[index]) {
            stack.pop();
            index++;
        }
    }
    return stack.empty();
}

从上到下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] levelOrder(TreeNode root) {
    if (root == null) {
        return new int[0];
    }
    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> list = new ArrayList<>();
    TreeNode temp ;
    queue.add(root);
    while (!queue.isEmpty()) {
        temp = queue.poll();
        list.add(temp.val);
        if (temp.left != null) {
            queue.add(temp.left);
        }
        if (temp.right != null) {
            queue.add(temp.right);
        }
    }
    return list.stream().mapToInt(Integer::intValue).toArray();
}

从上到下打印二叉树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
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    TreeNode temp;
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        for(int i = 0 ; i < size; ++i) {
            temp = queue.poll();
            list.add(temp.val);
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
        ans.add(list);
    }
    return ans;
}

从上到下打印二叉树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
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    TreeNode temp;
    int size = 0;
    boolean flag = true;
    while (!queue.isEmpty()) {
        size = queue.size();
        List<Integer> z = new LinkedList<>();
        for(int i = 0 ; i < size ; ++i) {
            temp = queue.poll();
            z.add(temp.val);
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        if (flag) {
            ans.add(z);
        } else {
            Collections.reverse(z);
            ans.add(z);
        }
        flag = !flag;
    }
    return ans;
}

二叉搜索树的后序遍历

参考题解https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/jian-dan-yi-dong-zhu-shi-cu-pin-zhi-xing-yong-shi-/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean verifyPostorder(int[] postorder) {
    Stack<Integer> stack = new Stack<>();
    int root = Integer.MAX_VALUE;
    for (int i = postorder.length - 1 ; i >= 0 ;--i) {
        // 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
        if (postorder[i] > root ) {
            return false;
        }
        while (!stack.empty() && stack.peek() > postorder[i]) {
            // 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
            // 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
            root = stack.pop();
        }
        stack.push(postorder[i]);
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int[] postorder;
public boolean verifyPostorder(int[] postorder) {
    this.postorder = postorder;
    return helper(0,postorder.length - 1);
}

private boolean helper(int i,int j) {
    if (i >= j) {
        return true;
    }
    int p = i;
    //划分左子树
    while (postorder[p] < postorder[j]) {
        p++;
    }
    int m = p;
    //划分友子树
    while (postorder[p] > postorder[j]) {
        p++;
    }
    return p == j && helper(i,m - 1) && helper(m,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
List<List<Integer>> ans;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    helper(new ArrayList<>(),root,sum);
    return ans;
}

private void helper(List<Integer> l,TreeNode root,int rest) {
    if (root == null) {
        return;
    }
    l.add(root.val);
    rest -= root.val;
    if (rest == 0 && root.left == null && root.right == null) {
        ans.add(new ArrayList<>(l));
    }
    if (root.left != null) {
        helper(l, root.left, rest);
    }
    if (root.right != null) {
        helper(l, root.right, rest);
    }
    l.remove(l.size() - 1);
}

复杂链表的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Node copyRandomList(Node head) {
    if (head == null) {
        return head;
    }
    Map<Node,Node> copy = new HashMap<>();
    Node p = head;
    while (p != null) {
        copy.put(p,new Node(p.val));
        p = p.next;
    }
    p = head;
    while (p != null) {
        copy.get(p).next = copy.get(p.next);
        copy.get(p).random = copy.get(p.random);
    }
    return copy.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
public Node copyRandomList(Node head) {
    if (head == null) {
        return head;
    }
    Node p = head,copy = null,temp = null;
    while (p != null) {
        copy = new Node(p.val);
        copy.next = p.next;
        p.next = copy;
        p = copy.next;
    }
    p = head;
    while (p != null) {
        if (p.random != null) {
            p.next.random = p.random.next;
        }
    }
    copy = head.next;
    p = head;
    while (p != null && p.next != null) {
        temp = p.next;
        p.next = p.next.next;
        p = temp;
    }
    return copy;
}

二叉搜索树与双向链表

重新排序

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
public Node treeToDoublyList(Node root) {
    if (root == null) {
        return root;
    }
    PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.val - o2.val;
        }
    });
    dfs(root,queue);
    Node head = queue.peek();
    Node cur = head , pre = null;
    while (!queue.isEmpty()) {
        cur = queue.poll();
        cur.right = queue.peek();
        cur.left = pre;
        pre = cur;
    }
    head.left = cur;
    cur.right = head;
    return head;
}

private void dfs(Node root,PriorityQueue<Node> queue) {
    if (root == null) {
        return;
    }
    queue.offer(root);
    dfs(root.left,queue);
    dfs(root.right,queue);
}

利用二叉搜索树中序为递增

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
Node preNode = null,headNode = null;
public Node treeToDoublyList(Node root) {
    if (root == null) {
        return root;
    }
    dfs(root);
    headNode.left = preNode;
    preNode.right = headNode;
    return headNode;
}

private void dfs(Node root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    if (preNode != null) {
        preNode.right = root;
    } else {
        headNode = root;
    }
    root.left = preNode;
    preNode = root;
    dfs(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
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
73
public class Codec{

    public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            if (root == null) {
                return null;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            final String space = " ";
            final String n = "null";
            final TreeNode nn = new TreeNode(Integer.MIN_VALUE);
            queue.offer(root);
            TreeNode temp;
            while (!queue.isEmpty()) {
                temp = queue.poll();
                if (temp.val != Integer.MIN_VALUE) {
                    sb.append(temp.val).append(space);
                } else {
                    sb.append(n).append(space);
                    continue;
                }
                if (temp.left != null && temp.left.val != Integer.MIN_VALUE) {
                    queue.offer(temp.left);
                } else {
                    //sb.append(n).append(space);
                    queue.offer(nn);
                }
                if (temp.right != null && temp.right.val != Integer.MIN_VALUE) {
                    queue.offer(temp.right);
                } else {
                    //sb.append(n).append(space);
                    queue.offer(nn);
                }
            }
            //ystem.out.println(sb.toString());
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            String[] s = data.substring(0,data.length() - 1).split(" ");
            final String n = "null";
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(s[0]));
            queue.offer(root);
            int index = 0;
            TreeNode temp;
            while (index < s.length && !queue.isEmpty()) {
                temp = queue.poll();
               // temp.val = Integer.parseInt(s[index]);
                //System.out.println("s[" + index + "]: " + s[index]);
                index++;
                if (s[index].equals(n)) {
                    temp.left = null;
                } else {
                    temp.left = new TreeNode(Integer.parseInt(s[index]));
                    queue.offer(temp.left);
                }
                index++;
                if (s[index].equals(n)) {
                    temp.right = null;
                } else {
                    temp.right = new TreeNode(Integer.parseInt(s[index]));
                    queue.offer(temp.right);
                }
            }
            //System.out.println(serialize(root));
            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
28
29
30
31
32
33
public String[] permutation(String s) {
    if (s == null || s.length() == 0) {
        return new String[0];
    }

   // String[] ans = new String[factorial(s.length())];
    List<String> ans = new ArrayList<>();
    char[] c = s.toCharArray();
    dfs(c,0,ans);
    return ans.toArray(new String[ans.size()]);
}

private void dfs(char[] c,int index,List<String> ans) {
    if (index == c.length - 1) {
        ans.add(String.valueOf(c));
        return;
    }
    char tmp;
    HashSet<Character> set = new HashSet<>();
    for (int i = index; i < c.length ; ++i) {
        if (set.contains(c[i])) {
            continue;
        }
        set.add(c[i]);
        tmp = c[i];
        c[i] = c[index];
        c[index] = tmp;
        dfs(c,index + 1,ans);
        tmp = c[i];
        c[i] = c[index];
        c[index] = tmp;
    }
}

数组中出现次数超过一半

1
2
3
4
5
6
7
8
9
10
11
12
13
public int majorityElement(int[] nums) {
    int current = nums[0];
    int val = 1;
    for(int i = 0 ; i < nums.length ; ++i) {
        if (val == 0) {
            current = nums[i];
            val = 1;
        } else {
            val = nums[i] == current ? val + 1 : val - 1;
        }
    }
    return current;
}

最小的k个数

1
2
3
4
5
6
7
8
9
10
11
12
public int[] getLeastNumbers(int[] arr, int k) {
    if (arr == null || arr.length == 0) {
        return new int[0];
    }
    Arrays.sort(arr);
    
    int[] ans = new int[k];
    for (int i = 0 ; i < k ; ++i) {
        ans[i] = arr[i];
    }
    return ans;
}
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
public int[] getLeastNumbers(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k == 0) {
        return new int[0];
    }
    return quickSort(arr,0,arr.length - 1,k - 1);
}

private int[] quickSort(int[] arr,int left,int right,int k) {
    int index = partition(arr,left,right);
    if (index == k) {
        return Arrays.copyOf(arr,index + 1);
    }
    return index > k ? quickSort(arr,left,index-1,k) : quickSort(arr,index + 1, right,k);
}

private int partition(int[] nums,int left,int right) {
    //选取一个随机枢纽基准值
    int random = new Random().nextInt(right - left + 1) + left;
    swap(nums,left,random);
    int value = nums[left];
    int i = left + 1 , j = right;
    while (true) {
        while (i <= right && nums[i] < value) {
            ++i;
        }
        while (j > left && nums[j] > value)
            --j;
        if (i >= j) {
            break;
        }
        swap(nums,i,j);
        i++;
        j--;
    }
    swap(nums,left,j);
    return j;
}

private static void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

数据中的中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MedianFinder {

        PriorityQueue<Integer> minHeap,maxHeap;

        /** initialize your data structure here. */
        public MedianFinder() {
            minHeap = new PriorityQueue<>();  //小顶堆，保留较大的一部分
            maxHeap = new PriorityQueue<>(Collections.reverseOrder());  //大顶堆，保留较小的一部分
        }

        public void addNum(int num) {
            if (minHeap.size() != maxHeap.size()) {
                minHeap.add(num);
                maxHeap.add(minHeap.poll());
            } else {
                maxHeap.add(num);
                minHeap.add(maxHeap.poll());
            }
        }

        public double findMedian() {
            return minHeap.size() != maxHeap.size() ? minHeap.peek() : (minHeap.peek() + maxHeap.peek()) / 2.0; 
        }
    }

连续数组的最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int sum = 0;
    int max = Integer.MIN_VALUE;
    for (int x : nums) {
        if (sum > 0) {
            sum += x;
        } else {
            sum = x;
        }
        max = Math.max(max,sum);
    }
    return max;
}

1的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//每一位出现1的最大数量
private static final int[] count = {0,1,20,300,4000,50000,600000, 7000000, 80000000, 900000000};
public int countDigitOne(int n) {
    int ans = 0;
    int index = 0, pow = 1,pre = 0;
    while (n != 0) {
        //记录当前位数的值
        int rest = n % 10;
        if (rest == 1) {
            ans += pre + 1 + count[index];
        } else if (rest > 1) {
            ans += pow + rest * count[index];
        }
        pre = pre + rest * pow;
        pow *= 10;
        index++;
        n /= 10;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
    //确定目标数字
    //因为start为起始，所以要n-1
    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
15
16
17
18
19
20
21
public String minNumber(int[] nums) {
    if (nums == null || nums.length == 0) {
        return null;
    }
    int len = nums.length;
    String[] s = new String[len];
    for (int i = 0 ; i < len ; ++i) {
        s[i] = String.valueOf(nums[i]);
    }
    Arrays.sort(s, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);
        }
    });
    StringBuilder sb = new StringBuilder();
    for (String x : s) {
        sb.append(x);
    }
    return sb.toString();
}

把数字翻译成字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int translateNum(int num) {
    String s = String.valueOf(num);
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2 ; i <= s.length(); ++i) {
        String temp = s.substring(i - 2,i);
        if(temp.compareTo("10") >= 0 && temp.compareTo("26") < 0) {
            dp[i] = dp[i - 1] + dp[i - 2];
        } else {
            dp[i] = dp[i - 1];
        }
    }
    return dp[s.length()];
}

礼物的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxValue(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    int row = grid.length, col = grid[0].length;
    int[] dp = new int[col];
    for (int i = 0 ; i < row ; ++i) {
        for(int j = 0 ; j < col; ++j) {
            if (j == 0) {
                dp[j] += grid[i][j];
                continue;
            }
            dp[j] = Math.max(dp[j],dp[j - 1]) + grid[i][j];
        }
    }
    return dp[col - 1];
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() <= 0) {
        return 0;
    }
    int[] set = new int[128];
    char[] ss = s.toCharArray();
    int max = 0 ,len = s.length(),left = 0;
    char tmp;
    for (int i = 0 ; i < len ; ++i) {
        tmp = ss[i];
        set[tmp]++;
        while (left < len && set[ss[i]] > 1) {
            tmp = ss[left];
            set[tmp]--;
            left++;
        }
        max = Math.max(i - left + 1 , max);
    }
    return max;
}

丑数

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

第一个只出现一次的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static final char SPACE = ' ';
public char firstUniqChar(String s) {
    if (s == null || s.length() == 0) {
        return SPACE;
    }
    int[] map = new int[26];
    char[] c = s.toCharArray();
    for (char x : c){
        map[x - '0']++;
    }
    for (char x : c) {
        if (map[x - '0'] == 1){
            return x;
        }
    }
    return SPACE;
}

数组中的逆序对

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
73
74
75
76
77
78
79
80
81
82
83
84
85
public int reversePairs(int[] nums) {
        int len = nums.length;
        ForkJoinPool pool = new ForkJoinPool();
        RecursiveTask<Integer> task = new MergeAndCount(nums,0,nums.length - 1);
        ForkJoinTask<Integer> res = pool.submit(task);
        int ans = 0;
        try {
            ans = res.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
        return ans;
    }

    private static class MergeAndCount extends RecursiveTask<Integer> {

        private int[] nums;
        private int left;
        private int right;
        private int[] temp;

        public MergeAndCount (int[] nums,int left,int right) {
            this.nums = nums;
            this.left = left;
            this.right = right;
            temp = new int[nums.length];
            System.out.println("called by thread : " + Thread.currentThread().getName());
        }

        @Override
        protected Integer compute() {
            int len = nums.length;
            if (len < 2 || left == right) {
                return 0;
            }
            int mid = left + (right - left) / 2;
            MergeAndCount leftPairs = new MergeAndCount(nums,left,mid);
            MergeAndCount rightPairs = new MergeAndCount(nums,mid + 1,right);
            invokeAll(leftPairs,rightPairs);
            int r1 = leftPairs.join();
            int r2 = rightPairs.join();

            // 如果整个数组已经有序，则无需合并，注意这里使用小于等于
            if (nums[mid] <= nums[mid + 1]) {
                return r1 + r2;
            }
            int crossPairs = mergeAndCount(nums, left, mid, right, temp);
            return r1 + r2 + crossPairs;
        }

        private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
            for (int i = left; i <= right; i++) {
                temp[i] = nums[i];
            }

            int i = left;
            int j = mid + 1;

            int count = 0;
            for (int k = left; k <= right; k++) {
                // 有下标访问，得先判断是否越界
                if (i == mid + 1) {
                    nums[k] = temp[j];
                    j++;
                } else if (j == right + 1) {
                    nums[k] = temp[i];
                    i++;
                } else if (temp[i] <= temp[j]) {
                    // 注意：这里是 <= ，写成 < 就不对，请思考原因
                    nums[k] = temp[i];
                    i++;
                } else {
                    nums[k] = temp[j];
                    j++;

                    // 在 j 指向的元素归并回去的时候，计算逆序对的个数，只多了这一行代码
                    count += (mid - i + 1);
                }
            }
            return count;
        }

    }

链表相交节点

1
2
3
4
5
6
7
8
9
10
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode node1=headA;
    ListNode node2=headB;
    while (node1!=node2){
        node1=(node1==null)?headB:node1.next;
        node2=(node2==null)?headA:node2.next;
    }
    return node1;
}

在排序数组中查找数字

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
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 {
            right = mid - 1;
        }
    }
    int j = left;
    if (right >= 0 && nums[right] != target) {
        return 0;
    }
    //左边界
    left = 0;
    right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    int i = right;
    return j - i - 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
36
37
public int search(int[] nums, int target) {
    int count=0;
    if(nums.length==0||binarySearch(nums,target)==-1){
        return 0;
    }
    int index=binarySearch(nums,target);
    count++;
    int left=index-1;
    while(left>=0&&nums[left]==target){
        count++;
        left--;
    }
    int right=index+1;
    while(right<nums.length&&nums[right]==target){
        count++;
        right++;
    }
    return count;
}

public static int binarySearch(int[] nums,int target){
    int left=0;
    int right=nums.length;
    int mid=(left+right)/2;

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

0-n中缺失的数字

1
2
3
4
5
6
7
8
9
10
11
12
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) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

二叉搜索树中第k大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int res, k;
public int kthLargest(TreeNode root, int k) {
    this.k = k;
    dfs(root);
    return res;
}
void dfs(TreeNode root) {
    if(root == null || k == 0) {
        return;
    }
    dfs(root.right);
    if(--k == 0) {
        res = root.val;
    }
    dfs(root.left);
}

二叉树的深度

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

平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private boolean flag = false;
public boolean isBalanced(TreeNode root) {
    depth(root);
    return !flag;
}

private int depth(TreeNode root) {
    if (root == null || flag) {
        return 0;
    }
    int left = 0,right = 0;
    if (root.left != null) {
        left = depth(root.left) + 1;
    }
    if (root.right != null) {
        right = depth(root.right) + 1;
    }
    if (Math.abs(left - right) > 1) {
        flag = true;
    }
    return Math.max(left,right);
}

数组中只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] singleNumbers(int[] nums) {
    int xor = 0;
    for (int i : nums)// 一样的抵消,不一样的两个数字异或运算结果必定有一位是1
        xor ^= i;

    int mask = xor & (-xor);

    int[] ans = new int[2];
    for (int i : nums) {
        if ((i & mask) == 0)//== 0、 == mask 两种结果
            ans[0] ^= i;
        else
            ans[1] ^= i;
    }

    return ans;
}

和为s的连续正序列

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
public int[][] findContinuousSequence(int target) {
    if (target <= 2) {
        return new int[0][0];
    }
    List<int[]> list = new ArrayList<>();
    int temp,a0;
    for (int i = 2 ; i < target ; ++i) {
        temp = target - i * (i - 1) / 2;
        if (temp <= 0) {
            break;
        }
        if (temp % i == 0) {
            a0 = temp / i;
            int[] ans = new int[i];
            for (int j = 0 ; j < i ; ++j) {
                ans[j] = a0 + j;
            }
            list.add(ans);
        }
    }
    int len = list.size();
    int[][] ans = new int[len][];
    for (int i = 0 ; i < len ; ++i) {
        ans[i] = list.get(len - i);
    }
    return ans;
}

反转单词顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String reverseWords(String s) {
    if (s == null || s.length() == 0) {
        return s;
    }
    String[] ss = s.trim().split(" ");
    StringBuilder sb = new StringBuilder();
    int len = ss.length;
    for (int i = len - 1 ; i >= 0 ; --i) {
        if (ss[i].equals("")) {
            continue;
        }
        sb.append(ss[i]).append(' ');
    }
    return sb.toString().trim();
}

左旋转字符串

1
2
3
public String reverseLeftWords(String s, int n) {
    return s.substring(n, s.length()) + s.substring(0, 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
public int[] maxSlidingWindow(int[] nums, int k) {
    int len = nums.length;
    if (len * k == 0) {
        return new int[0];
    }
    int maxIndex = 0, max = Integer.MIN_VALUE;
    int[] ans = new int[len - k + 1];
    int index = 0;
    for (int i = 0 ; i < k ; ++i) {
        if (nums[i] > max) {
            max = nums[i];
            maxIndex = i;
        }
    }
    ans[index++] = max;
    for (int i = k ; i < len ; ++i) {
        //不在索引内
        if (maxIndex < i - k + 1) {
            maxIndex = i - k + 1;
            max = nums[i - k + 1];
            for (int j = i - k + 1 ; j < i ; ++j) {
                if (nums[j] > max) {
                    max = nums[j];
                    maxIndex = j;
                }
            }
        }
        if (nums[i] > max) {
            max = nums[i];
            maxIndex = i;
        }
        ans[index++] = max;
    }
    return ans;
}

队列的最大值

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 MaxQueue {

    Deque<Integer> max,nor;
    public MaxQueue() {
        max = new LinkedList<>();
        nor = new LinkedList<>();
    }

    public int max_value() {
        if (max.isEmpty()) {
            return -1;
        }
        return max.peek();
    }

    public void push_back(int value) {
        nor.offer(value);
        while (!max.isEmpty() && max.peekLast() < value) {
            max.pollLast();
        }
        max.addLast(value);
    }

    public int pop_front() {
        if (nor.isEmpty()) {
            return -1;
        }
        int ans = nor.poll();
        if (!max.isEmpty() && ans == max.peek()) {
            max.poll();
        }
        return ans;
    }
}

n个骰子的点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public double[] twoSum(int n) {
    if (n <= 0) {
        return new double[0];
    }
    double[] pre = new double[6];
    Arrays.fill(pre,1 / 6.0);
    for (int i = 2 ; i <= n ; ++i) {
        double[] tmp = new double[5 * i + 1];
        for (int j = 0 ; j < pre.length ; ++j) {
            for (int l = 0 ; l < 6 ; ++l) {
                tmp[l + j] += pre[j] / 6;
            }
        }
        pre = tmp;
    }
    return pre;
}

扑克牌中的顺子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isStraight(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    Arrays.sort(nums);
    int zero = 0;
    for (int i = 0;i < nums.length - 1 ; ++i) {
        if (nums[i] == 0) {
            zero++;
            continue;
        }
        if (nums[i] == nums[i + 1]) {
            return false;
        }
        //用大小王去填充中间的沟壑
        zero -= nums[i + 1] - nums[i] - 1;
    }
    //如果是00123那也能算是顺子，因为00能填充任意位置
    return zero >= 0;
}

圆圈中的最后剩下的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lastRemaining(int n, int m) {
    List<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
public int lastRemaining(int n, int m) {
    int ans = 0;
    // 最后一轮剩下2个人，所以从2开始反推
    for (int i = 2; i <= n; i++) {
        ans = (ans + m) % i;
    }
    return ans;
}

股票最大利润

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    int profit = Integer.MIN_VALUE;
    int min = prices[0];
    for (int i = 1 ; i < prices.length ; ++i) {
        profit = Math.max(profit,prices[i] - min);
        min = Math.min(min,prices[i]);
    }
    return Math.max(profit,0);
}

等差数列求和

1
2
3
public int sumNums(int n) {
       return (int) (Math.pow(n, 2) + n) >> 1;
   }

不用加减乘除实现加法

1
2
3
4
5
6
7
8
9
public int add(int a, int b) {
    if (b == 0) {
        return a;
    }
    int c = a & b;
    c = c << 1;
    int d = a ^ b;
    return add(d,c);
}
1
2
3
4
5
6
7
8
9
public int add(int a, int b) {
       while (b != 0) {
           int plus = (a ^ b); // 求和（不计进位）. 相同位置0，相反位置1
           b = ((a & b) << 1); // 计算进位. 先保留同为1的位，都为1的位要向左进位，因此左移1位
           a = plus;
       }
       return a;
   }

字符串转整数

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
public int strToInt(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    long ans = 0 ;
    boolean neg = false;
    char[] c = str.toCharArray();
    int index = 0;
    while (index < c.length && c[index] == ' ') {
        index++;
    }
    if (index == c.length) {
        return 0;
    }
    char temp = c[index];
    if ((temp < '0' || temp > '9') && temp != '+' && temp != '-') {
        return 0;
    }
    if (temp == '-') {
        index++;
        neg = true;
    } else if (temp == '+') {
        index++;
    }
    temp = c[index];
    while (index < c.length && temp >= '0' && temp <= '9') {
        ans = ans * 10 + temp - '0';
        if (!neg && ans > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (neg && -ans < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        index++;
        temp = c[index];
    }
    return neg ? (int)-ans : (int)ans;
}

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

1
2
3
4
5
6
7
8
9
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left,p,q);
    }
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right,p,q);
    }
    return root;
}

判定字符串是否唯一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isUnique(String astr) {
    if (astr == null || astr.length() == 0) {
        return true;
    }
    int[] map = new int[128];
    char[] cc = astr.toCharArray();
    for (char ch : cc) {
        if (map[ch] >= 1) {
            return false;
        } else {
            map[ch]++;
        }
    }
    return true;
}

判断是否互为字符重排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean CheckPermutation(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    if (len1 != len2) {
        return false;
    }
    int[] map = new int[128];
    char[] chars = s1.toCharArray();
    for (char ch : chars) {
        map[ch]++;
    }
    chars = s2.toCharArray();
    for (char ch : chars) {
        map[ch]--;
    }
    for (int x : map) {
        if (x != 0) {
            return false;
        }
    }
    return true;
}