3.数组中重复的数字

排序遍历

可以直接将数组排序，然后进行循环遍历，就可以找到数组中重复的数字了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1;i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return 0;
    }
}

Set去重

可以将该数组丢到Set集合里去重，若是添加失败就代表该数字重复，直接返回就好了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.add(i)) {
                return i;
            }
        }
        return 0;
    }
}

哈希表

跟Set差不多，添加到哈希表之前，先判断一下是否有该键，然后要是有就直接返回。

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

原地置换（类似桶排序）

遍历数组，将每一个数放在与它等值的下标下，因为题目说了数字都在1~n - 1，所以当该下标出现了与它一样的数字，代表这个数字是重复的。

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

衍生题

题目详情可以参考https://www.acwing.com/problem/content/description/15/。

这里可以使用上述的哈希和Set集合来进行查找，或者在创建一个数组，然后使用桶排序找出重复的元素。

因为必定会有一个重复的，可以理解为数组中间会出现一个环，所以可以当成寻找链表的环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int duplicateInArray(int[] nums) {
        // 快慢指针寻找相遇点
        int fast = 0；
        int slow = 0;
        while (fast == 0 || fast != slow) {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        // 寻找入环点
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}

还有就是利用分治的思想来解。类似二分查找的思想。

利用数值将数组分成两半，如果一边坑的个数小于数的个数，代表重复的数字就在那半边，所以缩小区间，直到找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int duplicateInArray(int[] nums) {
        int l = 1;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;    
            // 记录小于中间值的数的个数
            int count = 0;  
            for(int i : nums) {
                if(l <= i && i <= mid) count++;
            }
            // 个数大于坑数就进入左区间，直到找到重复的数字
            if(count > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

4.二维数组中的查找

数组遍历

直接将这个二维数组遍历，暴力破解。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int[] i : matrix) {
            for (int j : i) {
                if (j == target) return true;
            }
        }
        return false;
    }
}

二维查找

根据递增的单调性，可以从最右上角一个个进行排除，寻找对应的值。可以从右下角向左下角进行遍历（反过来也可以）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int i = 0;
        // 从最后一列开始，排除最后一列小于给定值的行
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            // 如果值大于给定值，代表当前行不存在给定值，所以遍历下一行
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}

5.替换空格

replaceAll

String类里就自带一个替换的方法了，所以可以直接进行替换。

1
2
3
4
5
class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ","%20");
    }
}

遍历字符串

直接遍历字符串，出现了空格就替换，不然就不替换。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        char[] str = s.toCharArray();
        for (char c : str) {
            if (c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}

要是不能用动态的增加字符串，就只能先遍历一遍字符串，然后判断答案的长度，然后在创建一个新的数组，然后依次放入新数组就好了。

6. 从尾到头打印链表

反转链表后输出

这里最简单的解法就是将链表反转，然后在打印链表了。

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

递归遍历

这里可以使用类似后序遍历的操作，先递归进去然后添加值，这样就类似栈了，直接从后到前输出。或者这里定义一个栈也可以进行。

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

反向输出

其实可以看到，其实从前遍历，然后反向输出就行了，其实并不用一定是正向的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    
    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;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i< list.size(); i++) {
            res[i] = list.get(list.size() - i - 1);
        }
        return res;
    }

}

两次遍历

第一次遍历链表，判断数组的个数，然后从后往前赋值就好了。之前的解法也可以改为先进行一次遍历后再赋值，这样就不用使用list集合了，效率太低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        ListNode node = head;
        int size = 0;
        while(node != null) {
            size++;
            node = node.next;
        }
        int[] res = new int[size];
        for (int i = size - 1; i > -1;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
class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        int[] res = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()) {
            res[i++] = stack.pop().val;
        }
        return res;
    }
}

7.重建二叉树

这题主要是要划分区间，划分好左子树和右子树的区间。

前序遍历的区间可以分为三个。根的值，左子树的值，右子树的值。

中序遍历的区间可以分为三个。左子树的值，根的值，右子树的值。

所以可以用前序遍历的第一个值创建节点，然后遍历前序遍历的数组，用中序遍历的数组来判断是否达到根的值。

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 {

    private int ino = 0;
    private int pre = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, long stop) {
        if (pre >= preorder.length) return null;
        // 判断该子树是否碰到根
        if (inorder[ino] == stop) {
            ino++;
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre++]);
        // 左子树的范围，到当前节点值，即到子树的根值(按前序遍历的数组)
        node.left = build(preorder,inorder,node.val);
        // 右子树的范围，从当前节点到最后
        node.right = build(preorder,inorder,stop);

        return node;
    }

}

上面是通过前序遍历和中序遍历去创建一颗二叉树，接下来是通过中序遍历和后序遍历来创建一个二叉树，其实差不多。

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 { 
    
    private int ino = 0;
    private int pos = 0;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pos = postorder.length - 1;
        ino = inorder.length - 1;
        return build(inorder,postorder,Integer.MIN_VALUE - 1);
    }
    
    public TreeNode build(int[] inorder, int[] postorder,long stop) {
        if (pos == -1) return null;
        if (inorder[ino] == stop) {
            ino--;
            return null;
        }
        TreeNode node = new TreeNode(postorder[pos--]);
        node.right = build(inorder,postorder,node.val);
        node.left = build(inorder,postorder,stop);
        return node;
    }
    
}

8.二叉树的下一个节点

题目详情可以参考https://www.acwing.com/problem/content/31/

这里就是直接找下一个节点就好了。

于是会有两种情况。

  1. 当前节点有右子树。那么该节点的下一个节点就是右子树里的最左子节点。
  2. 当前节点没有右子树，那就要追溯回原来第一个是其father左儿子的节点。
    • 该节点是父节点的左孩子，这样下一个节点就是它的father
    • 该节点是父孩子的右孩子，这样下一个节点就是该左子树的父节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        // 存在右子树的情况
        if (p.right != null) {
            p = p.right;
            while(p.left != null) p = p.left;
            return p;
        }
        // 不存在右子树的情况
        while(p.father != null && p == p.father.right) p = p.father;
        
        return p.father;
    }
}

9.用两个栈实现队列

这里先来分析一下这两个栈的作用。栈是先进后出的数据结构，而队列是先进先出的，所以无法进行互通，引入第二个栈是用来存储第一个栈中出栈的元素，这样第二个栈的元素就是第一个栈元素的倒序了，直接出栈就是最先进来的元素了。

入队就直接压入第一个栈中就可以了。

主要是要探讨出队的情况。

  1. 当第二个栈中还有元素的时候，代表这些元素是最先进入的元素，所以直接出栈就是之前最先入队的元素了。
  2. 当第二个栈和第一个栈都没有元素了，那就证明队列为空。
  3. 当第二个栈没有元素，第一个栈有元素，那就直接将第一个栈的元素全部出栈压入第二栈，实现倒序。
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 CQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if (!stack2.isEmpty()) return stack2.pop();
        if (stack1.isEmpty()) return -1;
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
    
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

10.斐波那契数列

剑指Offer这题的斐波那契数列是结果取模的，因为返回的是int，除了这个需要注意的，其他的和经常的解法差不多了。

递归

可以考虑直接递归，但一般都会超时。

1
2
3
4
5
6
7
class Solution {
    public int fib(int n) {
        if (n < 0) return 0;
        if (n == 1 || n == 2) return 1;
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            if (dp[i] >= 1000000007) dp[i] -= 1000000007;
        }
        return dp[n];
    }
}

迭代解法

这里是可以考虑dp数组的迭代解法的，但是这里只是一次性达到答案，不会回头了，所以记录之前的状态并没有什么意思，所以可以创建临时变量保存需要的临时变量就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = b;
            b = a + b;
            a = temp;
            if (b >= 1000000007) b -= 1000000007;
        }
        return b;
    }
}

青蛙跳台阶

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

11.旋转数组的最小数字

排序

可以直接排序在取第一个。

1
2
3
4
5
6
class Solution {
    public int minArray(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }
}

不递增

找到第一个不递增的数字那就是最小的数字了。

1
2
3
4
5
6
7
8
class Solution {
    public int minArray(int[] numbers) {
        for (int i = 0;i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) return numbers[i + 1];
        }
        return numbers[0];
    }
}

二分查找

二分查找最主要的就是划分区间，需要先分析一下怎样确定好区间。

  1. 中间的数大于最右边的数，代表期间不会单调递增，直接进入右边的区间
  2. 中间的数小于最右边的数，代表期间是单调递增的，直接进入左边的区间
  3. 要是中间的数与最右边的数相等，那就缩进一下区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minArray(int[] numbers) {
        int l = 0;
        int r = numbers.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (numbers[mid] > numbers[r]) {
                l = mid + 1;
            } else if (numbers[mid] < numbers[r]) {
                r = mid;
            } else {
                r -= 1;
            }
        }
        return numbers[l];
    }
}

12.矩阵中的路径

经典的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
34
35
36
37
38
class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int row = board.length;
        int col = board[0].length;
        // 标记是否经过的数组
        boolean[][] isVisited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 遍历每个点，确定dfs的起点
                if (board[i][j] == word.charAt(0) && dfs(board,word,0,i,j,isVisited)) return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,String word,int n,int x,int y,boolean[][] isVisited){
        if (board[x][y] != word.charAt(n)) return false;
        if (n == word.length() - 1) return true;
        // 标记经过
        isVisited[x][y] = true;
        // 偏移数组，上下左右
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        // 按上下左右开始偏移
        for (int i = 0; i < 4; i++) {
            int lx = x + dx[i];
            int ly = y + dy[i];
            // 保证下一步没有越界而且没有经过
            if (lx >= 0 && lx < board.length && ly >= 0 && ly < board[0].length && !isVisited[lx][ly]) {
                if (dfs(board,word,n + 1,lx,ly,isVisited)) return true;
            }
        }
        // 取消标记，回溯
        isVisited[x][y] = false;
        return false;
    }
}

13.机器人的运动范围

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
class Solution {
    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) return 0;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(0,0,k,isVisited);
    }

    public int dfs(int i,int j,int k,boolean[][] isVisited) {
        if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || !isAllowed(i,j,k)) return 0;
        isVisited[i][j] = true;
        // 上下左右
        return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
    }
	// 判断是否合法
    public boolean isAllowed(int m, int n, int k) {
        int sum = 0;
        while (m != 0) {
            sum += m % 10;
            m = m / 10;
        }
        while (n != 0) {
            sum += n % 10;
            n = n / 10;
        }
        if (sum <= k) return true;
        else return false;
    }
}

看看别人的发现判断是否合法不用这么麻烦，还可以优化一下，所以变成下面这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) return 0;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(0,0,k,isVisited);
    }

    public int dfs(int i,int j,int k,boolean[][] isVisited) {
        if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || (i/10+i%10+j/10+j%10)>k) return 0;
        isVisited[i][j] = true;
        return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
    }

}

从0,0开始，其实只用向右和向下就可以走完全部的格子了，所以可以去掉向左和向上的dfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) return 0;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(0,0,k,isVisited);
    }

    public int dfs(int i,int j,int k,boolean[][] isVisited) {
        if (i >= isVisited.length || j >= isVisited[0].length || isVisited[i][j] || (i/10+i%10+j/10+j%10)>k) return 0;
        isVisited[i][j] = true;
        return dfs(i+1,j,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
    }

}

14.1 剪绳子

动态规划

这一题刚开始给我的想法是使用动态规划去解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int cuttingRope(int n) {
        if (n == 1 || n == 2) return 1;
        if (n == 3) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            int max = 0;
            // j >i / 2就会出现重复了，所以就不需要那部分的数据比较了
            for (int j = 1; j <= i / 2; j++) {
                max = Math.max(max,dp[j] * dp[i - j]);
            }
            dp[i] = max;
        }
        return dp[n];
    }
}

贪婪算法

搬用题解关于该题的解释。

  1. 任何大于1的数都可由2和3相加组成。
  2. 因为都能有2和3组成，所以当3的数量越多，乘积越大。当剩余的绳子长度大于等于5，尽可能剪长度为3的绳子。
  3. 有一个特例。当剩余的绳子长度等于4，就将绳子剪为两段2。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int cuttingRope(int n) {
        if (n == 1 || n == 2) return 1;
        if (n == 3) return 2;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
}

14.2 剪绳子2

这题将数据量变大了很多，使用动态规划就会很麻烦，所以用刚刚的贪婪算法，修改一下。

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

15.二进制中1的个数

用方法

有个方法是可以算出二进制中1的个数。

1
2
3
4
5
public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

位运算

通过数字与1的与运算，来判断最后一个二进制的数是不是1，是的话与运算会返回1，就这样逐个判断二进制1的个数。

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}

还有一个就是用n & (n - 1)来判断，这样的与运算会消去二进制中最右边的1。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
}

n & (n - 1)还能用来判断是不是2的幂。

16.数值的整数次方

这里直接使用相乘的算法会超时，所以用到了快速幂的写法。这里需要注意的点是n为负数的时候，int的负数会比正数多一个，力扣上正好用到了这个边界−2147483648，所以需要用long类型来存储。

快速幂的迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public double myPow(double x, int n) {
        // 每个数的0次方都等于1
        if (n == 0) return 1;
        // 因为负数是比正数多一个数的，如果取得是负数的最小值，取反就会超出正数的最大值，所以使用long
        long num = n;
        double res = 1.0;
        // 如果是负次方，就转换为正数次方
        if (n < 0) {
            x = 1 / x;
            num = -num;
        }
        // 若num还大于0代表运算还没有结束
        while (num > 0) {
            // 当次方数为奇数的时候，就乘底数，次方数减一，转换为次方数为偶数的情况
            if ((num & 1) == 1) res *= x;
            // 次方数为偶数的时候，底数平方，次方数除以2，缩短运算
            x = x * x;
            num >>= 1;
        }
        return res;
    }
}

快速幂的递归写法

1
2
3
4
5
6
7
8
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == -1) return 1 / x;
        if ((n & 1) == 1) return myPow(x * x,n >> 1) * x;
        else return myPow(x * x,n >> 1);
    }
}

18.删除链表的节点

这里可以直接查到那个需要删除的节点，然后改变链表的指向就好了。

迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return head;
        if (head.val == val) return head.next;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode pre = newHead;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur.next = null;
                break;
            }
            pre = pre.next;
            cur = cur.next;
        }
        return newHead.next;
    }
}

递归写法

1
2
3
4
5
6
7
8
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) return head.next;
        head.next = deleteNode(head.next,val);
        return head;
    }
}

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

这题一看题目就是有点像快排的思想，双指针遍历就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            while (nums[l] % 2 != 0 && l < r) l++;
            while (nums[r] % 2 == 0 && l < r) r--;
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        return nums;
    }
}

22.链表中倒数第K个节点

快慢指针

这题用快慢指针还是很简单的，先让快指针走N步，然后快慢指针一起走，当快指针都到链表尾部，那么慢指针就是倒数第K个节点了。

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

24.反转链表

迭代

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

递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head);
    }
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

25.合并两个排序的链表

迭代

这个只要遍历就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                cur.next = l2;
                l2 = l2.next;
            } else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        if (l1 == null) cur.next = l2;
        else cur.next = l1;
        return head.next;
    }
}

递归

递归的解法挺简洁的，但是可能会有点绕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 要不要这行都可以
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

26. 树的子结构

首先要先找到A中与B节点的头节点相等的点，然后递归判断A与B的左子树与右子树，看是否结构与节点值相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution { 
    
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return check(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    
    // 判断a树是否和b树是一样的
    public boolean check(TreeNode A, TreeNode B) {
        // 若B节点为空，无论A节点是否为空，都是A树的子结构
        if (B == null) return true;
        // 因为此时B节点不为空，但是如果A节点为空，那么B树就不为A树的子结构了
        if (A == null) return false;
        // 两个值不相同，代表树种该位置两个节点不一样
        if (A.val != B.val) return false;
        // 判断左子树与右子树
        return check(A.left, B.left) && check(A.right, B.right);
    }
}

27.二叉树的镜像

转换镜像，那就是将左子树变为右子树，右子树变为左子树就可以了。

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

28.对称的二叉树

这题递归主要是要理清思路。将左子树和右子树传入，然后比较值，在将左子树的左子树和右子树的右子树，右子树的左子树和左子树的右子树放入递归判断就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return check(root.left, root.right);
    }
    
    public boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

29.顺时针打印矩阵

这题和那题螺旋矩阵差不多，最主要的就是遍历的边界的界定，这还是有点麻烦的。

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 int[] spiralOrder(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return new int[0];
        int cols = matrix[0].length;
        if (cols == 0) return new int[0];
        int count = 0;
        int[] res = new int[rows * cols];
        int up = 0, down = rows - 1, left = 0, right = cols - 1;
        // 注意调整边界时要注意不可过界
        while (count < rows * cols) {
            // 向右，遍历完，上边界下移
            for (int j = left; j <= right && left <= right; j++) {
                res[count++] = matrix[up][j];
            }
            up++;
            // 向下，遍历完，右边界左移
            for (int i = up; i <= down && up <= down; i++) {
                res[count++] = matrix[i][right];
            }
            right--;
            // 向左，遍历完，下边界上移
            for (int j = right; j >= left && up <= down; j--) {
                res[count++] = matrix[down][j];
            }
            down--;
            // 向上，遍历完，左边界右移
            for (int i = down; i >= up && left <= right; i--) {
                res[count++] = matrix[i][left];
            }
            left++;
        }
        return res;
    }
}

30. 包含min函数的栈

找到最小元素其实并不难，这题难的地方是调用min，push，pop的时间复杂度都要为O(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
class MinStack {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if (stack2.isEmpty()) {
            stack2.push(x);
        } else {
            stack2.push(Math.min(x, stack2.peek()));
        }
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

31. 栈的压入和弹出序列

这个问题就可以创建一个栈，然后进行模拟压入和弹出就可以了。

如果压入了弹出序列的数，就弹出就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        for (int i : pushed) {
            stack.push(i);
            while (!stack.isEmpty() && stack.peek() == popped[start]) {
                stack.pop();
                start++;
            }
        }
        return stack.isEmpty();
    }
}

32.1.从上到下打印二叉树

这题就是层序遍历就可以了，要注意的就是确定数组的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.poll();
            list.add(node.val);
            if (node.left != null) deque.offer(node.left);
            if (node.right != null) deque.offer(node.right);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

32.2.从上到下打印二叉树

这个也是层序遍历，与上一题不一样的是要先确定每层的节点数然后将每层的节点加入到临时链表存储，之后在加入到答案列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> list = new ArrayList<>();
            while (size-- != 0) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
            res.add(list);            
        }
        return res;
    }
}

32.3从上到下打印二叉树

这个就是要记录一下层数，这里的倒序可以分为两种解法。

  1. 倒着加入到列表
  2. 加入到列表之后再倒序

两种方法哪个都可以，我就使用了第二种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = deque.size();
            while (size-- != 0) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
            if (res.size() % 2 != 0) Collections.reverse(list);
            res.add(list);
        }
        return res;
    }
}

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

后序遍历的遍历序列大致可以分成这样[ 左子树 | 右子树 | 根节点 ]

又因为是二叉搜索树，故左子树的所有节点应该比根节点小，右子树的所有节点应该比根节点大

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 boolean verifyPostorder(int[] postorder) {
        return check(postorder,0,postorder.length - 1);
    }
    
	// 判断该树是否正确
    public boolean check(int[] postorder, int start, int end) {
        // start >= end代表该树只有小于等于1的节点，所以不用判断，返回true
        if (start >= end) return true;
        int p = start;
        // mid 为根节点的值
        int mid = postorder[end];
        // 检查左子树区间节点是否正确
        while (postorder[p] < mid) {
            p++;
        }
        int lr = p;
        // 检查右子树区间节点是否正确
        while (postorder[p] > mid) {
            p++;
        }
        // 两个区间正确的话，p会遍历到根节点的位置，即p == end的话该树正确
        if (p != end) return false;
        // 然后遍历左子树和右子树是否正确
        return check(postorder, start, lr - 1) && check(postorder, lr, end - 1);
    }
}

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

回溯

直接进行回溯就可以了。

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 {
    
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return res;
    }

    public void dfs(TreeNode node, int target) {
        if (node == null) return;
        // 先进行添加在判断条件，如果是先判断条件的话，target的判断就不能使用减法了，需要多添加一个b
        path.addFirst(node.val);
        target -= node.val;
        // 若此时当前节点是子节点，并且target为0了，就代表是一条路径
        if(target == 0 && node.left == null && node.right == null) {
            res.add(new LinkedList(path));
        }
        // 遍历左子树和右子树
        dfs(node.left, target);
        dfs(node.right, target);
        // 状态回溯
        path.removeLast();
    }
}

35. 复杂链表的复制

哈希表

直接先将链表复制下来，然后逐个给复制随机指针指向就可以了。

链表复制很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node newhead = new Node(head.val);
        Node newcur = newhead;
        Node cur = head.next;
        while (cur != null) {
            Node node = new Node(cur.val);
            newcur.next = node;
            newcur = node;
            cur = cur.next;
        }
        return newhead;
    }
    
}

到这就会发现，这题的难点是怎样复制随机指针的指向。

这里可以用哈希表存储链表节点，键为原链表节点，值为新链表节点。

所以根据原链表节点的随机指针就能确定新链表的随机指针了。

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 Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node newHead = new Node(head.val);
        map.put(head, newHead);
        // 链表复制节点，并存储节点到哈希表
        Node newCur = newHead;
        Node cur = head.next;
        while (cur != null) {
            Node node = new Node(cur.val);
            newCur.next = node;
            newCur = node;
            map.put(cur, newCur);
            cur = cur.next;
        }
        // 给节点的随机指针赋值
        while (head != null) {
            map.get(head).random = map.get(head.random);
            head = head.next;
        }
        return newHead;
    }
}

拼接加拆分

将原链表和新链表拼接在一起

原节点1 —> 新节点1 —> 原节点2 —> 新节点2 ………..

这样的话，新节点的随机指针指向的前一个节点就是原节点的随机指针指向了。

将随机指针赋值完之后，将这个整合的链表中的新节点提取出来，拆分成一个新的链表就可以得到复制的链表了。

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 Node copyRandomList(Node head) {
        if (head == null) return head;
        // 为链表的每个节点复制一个节点并接在该节点后面
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        // 为新的复制节点的随机指针赋值
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 链表拆分
        Node newHead = head.next;
        Node newCur = newHead;
        cur = head;
        while (newCur.next != null) {
            cur.next = cur.next.next;
            newCur.next = newCur.next.next;
            cur = cur.next;
            newCur = newCur.next;
        }
        // 如果不加这句，系统判定是原来的节点，d
        cur.next = null;
        return newHead;
        
    }
}

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

排序

先排序，因为出现的次数超过一半，所以数组中间的数一定是超过一半的数字。

1
2
3
4
5
6
7
class Solution {
    public int majorityElement(int[] nums) {
        if (nums.length <= 2) return nums[0];
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int majorityElement(int[] nums) {
        if (nums.length <= 2) return nums[0];
        int count = 0;
        int temp = 0;
        for (int num : nums) {
            if (count == 0) temp = num;
            if (num == temp) {
                count++;
            } else {
                count --;
            }
        }
        return temp;
    }
}

40. 最小的k个数

暴力解法

直接排序取前k个数行了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) return new int[0];
        Arrays.sort(arr);
        int[] mink = new int[k];
        for (int i = 0; i < k; i++) {
            mink[i] = arr[i];
        }
        return mink;
    }
}

快速排序

因为要返回的最小的K个数，并没有说是有序的k个数，所以，快速排序的时候，排到第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
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, 0, arr.length - 1, k);
    }

    public int[] quickSort(int[] arr, int left, int right, int k) {
        int i = left, j = right, x = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= x) j--;
            while (i < j && arr[i] <= x) i++;
            if (i < j) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        arr[left] = arr[i];
        arr[i] = x;
        if (i > k) return quickSort(arr, left, i - 1, k);
        if (i < k) return quickSort(arr, i + 1, right, k);
        return Arrays.copyOf(arr, k);
    }
}

45.把数组排成最小的数

最简单的方法找出数组的全排序，得到所有数字的可能性，然后比较每个数字的大小就可以了。

不过这会很麻烦，暂时不考虑这种解法。

解法的关键是这个数组该怎么排序。使用普通的大于小于关系当然是不行的，所以需要自定义一个大小关系。

这里就定义了一个关系。要是ab > ba，那就设为a > b。

这里就不多加证明了。

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 String minNumber(int[] nums) {
        if (nums.length == 1) return String.valueOf(nums[0]);
        sort(nums, 0, nums.length - 1);
        StringBuilder res = new StringBuilder();
        for (int num : nums) {
            res.append(num);
        }
        return res.toString();
    }

    // 快排
    public void sort(int[] nums, int l , int r) {
        if (l >= r) return;
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (check(x,nums[i]));
            do j--; while (check(nums[j],x));
            if (i < j) swap(nums, i, j);
        }
        sort(nums, l, j);
        sort(nums, j + 1, r);
    }
	// 判断i是否大于j(自定义的大于)
    public boolean check(int i, int j) {
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        a.append(i).append(j);
        b.append(j).append(i);
        return a.toString().compareTo(b.toString()) > 0;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    
}

Java还有更简单的排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String minNumber(int[] nums) {
        if (nums.length == 1) return String.valueOf(nums[0]);
        List<String> list = new ArrayList<>();
        for (int num : nums) {
            list.add(String.valueOf(num));
        }
        // 这个排序虽然简单，但是效率好像没有快排高
        list.sort((o1,o2) -> (o1 + o2).compareTo(o2 + o1));
        return String.join("",list);
    }

}

46.把数字翻译成字符串

递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int translateNum(int num) {
        if (num <= 9) return 1;
        int ba = num % 100;
        if (ba <= 9 || ba >= 26) {
            return translateNum(num / 10);
        } else {
            return translateNum(num / 10) + translateNum(num / 100);
        }
    }
}

47.礼物的最大价值

回溯

这种题目回溯一般会超时，因为会有很多分支，把所有可能都计算出来了，如果题目需要遍历到所有可能，回溯会是一种很好的方法。

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

    private int res = -1;

    public int maxValue(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        dfs(grid, 0, 0, grid[0][0], visited);
        return res;
    }

    public void dfs(int[][] grid, int x, int y, int count, boolean[][] visited) {
        if (x == grid.length - 1 && y == grid[0].length - 1) {
            res = Math.max(count, res);
        }
        if (x + 1 < grid.length && !visited[x + 1][y]) {
            visited[x + 1][y] = true;
            dfs(grid, x + 1, y, count + grid[x + 1][y],visited);
            visited[x + 1][y] = false;
        }

        if (y + 1 < grid[0].length && !visited[x][y + 1]) {
            visited[x][y + 1] = true;
            dfs(grid, x, y + 1, count + grid[x][y + 1],visited);
            visited[x][y + 1] = false;
        }
    }
}

动态规划

回溯减枝就可以想到动态规划了，存储最大的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {

    public int maxValue(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[rows][cols];
    }

}

这里其实可以优化为一维数组的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {

    public int maxValue(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[] dp = new int[cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[cols];
    }

}

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

这题两重循环的暴力解很大概率会超时，所以就不用暴力解了。

这里最好的方法就是滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len <= 1) return len;
        int l = 0, max = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            // 如果已经存在重复的字符，就更新窗口的左边界让字符串不重复
            if (map.containsKey(s.charAt(i))) {
                // 重新定义窗口左边界
                l = Math.max(l, map.get(s.charAt(i)) + 1);
            }
            // 更新（添加）map里字符的坐标
            map.put(s.charAt(i),i);
            // 计算最大值
            max = Math.max(max, i - l + 1);
        }
        return max;
    }
}

49. 丑数

使用动态规划，主要是凑成最小的丑数，然后一个个凑到第N个，就是用2,3,5的公倍数从小凑到N。

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

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

这题用正常思维就可以解决了，暂时找不到更优的解法，都是先存储出现的次数，然后在遍历找出第一个次数为1的字符。

我这里就是用了哈希来进行存储，用数组也是可以的，因为题目标明了只有小写字母。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        for (char c : s.toCharArray()) {
            if (map.get(c) == 1) return c;
        } 
        return ' ';
    }
}

51.数组中的逆序对

暴力破解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int reversePairs(int[] nums) {
        int[] sum = new int[nums.length];
        for (int i = 0; i < sum.length; i++) {
            for (int j = i + 1; j < sum.length; j++) {
                if (nums[i] > nums[j]) sum[i]++;
            }
        }
        int res = 0;
        for (int s : sum) {
            res += s;
        }
        return res;
    }
}

超时了。。O(n^2)的确很容易超时。

归并排序

这个真没想出来。不过这题的确是归并排序的经典题，求出当前数与前面的数或者是后面的数的大小关系的个数的题基本都是归并排序来进行实现的。

归并排序主要分为两个个部分，递归划分，排序合并。

所以在排序合并的时候就能记录出逆序对的个数了。

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

    private int res = 0;
    private int[] temp;

    public int reversePairs(int[] nums) {
        temp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int l, int r) {
        // 划分终止
        if (l >= r) {
            return 0;
        }
		// 递归划分
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        // 排序合并
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                // 理解了这个结果的计算就容易了
                //如果j位置小于i位置，那么j位置小于i位置后所有的右半边的数
                res += mid - i + 1;
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= r) {
            temp[k++] = nums[j++];
        }
        // 排序结果放入原数组，完成排序
        for (i = l, j = 0; i <= r; i++, j++) {
            nums[i] = temp[j];
        }
        return res;
    }

}

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

这题每个节点的数字都不是唯一的，所以不能用普通存储的方式来查找第一个公共节点。

所以需要考虑一下直接遍历，唯一的问题就是，这两个链表不一定是等长的。所以我们需要想办法弄成等长的。

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode n1 = headA;
        ListNode n2 = headB;
        // 都遍历了一段公共的节点与两个链表不公共的部分，凑成了等长的
        while (n1 != n2) {
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n1;
    }
}

53.1在排序数组中查找数字1

暴力破解

直接循环一遍即可。

1
2
3
4
5
6
7
8
9
class Solution {
    public int search(int[] nums, int target) {
        int res = 0;
        for (int n : nums) {
            if (n == target) res++;
        }
        return res;
    }
}

二分查找

因为数组本身就是排好序的，所以很容易联想到二分查找。查找到第一个小于目标数字的数，然后循环找出有多少个目标数字就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        int res = 0;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        while (l < nums.length && nums[l++] == target) {
            res++;
        }
        return res;
    }
}

53.20~n-1中缺少的数字

暴力破解

数组本身是递增的，直接递增，就能直接查找到缺少的数字。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            if (num != res) return res;
            res++;
        }
        return res;
    }
}

求和

求和然后逐个减去数组中的数字，这样就能找出缺少的数字了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i <= nums.length; i++) {
            res += i;
        }
        for (int num : nums) {
            res -= num;
        }
        return res;
    }
}

二分查找

数组有序，那就是二分查找。

最主要的问题是查找什么。

若是每个数字都不缺少，那n这个数字应该会在数组的n的下标的位置。

要是有个数字缺少了，数组就会乱序，所以我们只要找到第一个乱序的数字，即为答案。

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

56.1 数组中数字出现的次数

位运算

首先看到这题就想到之前写的找出唯一一个不是两个数的数字，使用异或很快就解决了问题。

不过这里的数组有两个这样的数，所以就无法直接异或得到答案，需要进行一些处理。

58.2 左旋转字符串

切片

直接截出这两段字符串然后换位置就可以了。

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
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        char[] arr = s.toCharArray();
        for (int i = n; i < arr.length; i++) res.append(arr[i]);
        for (int i = 0; i < n; i++) res.append(arr[i]);
        return res.toString();
    }
}

60. n个筛子的点数

这题是动态规划问题，状态转移方程有点类似多重背包。

dp[i][j] += dp[i - 1][j - k] * dp[1][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
class Solution {
    public double[] dicesProbability(int n) {
        double[][] dp = new double[n + 1][6 * n + 1];
        // 初始化一颗筛子的情况
        for (int i = 1; i <= 6; i++) dp[1][i] = (double) 1 / 6;
		
        for (int i = 2; i <= n; i++) {
           	// i颗筛子的最大点数
            int max = 6 * i;    
            // 遍历i颗筛子的所有点数求出概率
            for (int j = i; j <= max; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j - k <= 0) {   
                        continue;
                    }
                    dp[i][j] += dp[i - 1][j - k] * dp[1][k];
                }
            }
        }
		// 存储答案
        double[] res = new double[5 * n + 1];
        int value = n;
        for (int i = 0; i < res.length; i++) {
            res[i] = dp[n][value++];
        }
        return res;

    }
}

61. 扑克牌的顺子

首先确定答案的约束。

  1. 抽到的五张牌是不是连续的。
  2. 抽到的五张牌是不重复的。
  3. 大小王可以换为任意一张牌，可以存在重复的0

这里可以找出一定的规律，抽到的五张牌中最大的减去最小的小于5就可以说明这五张牌是重复的了。

Set去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> res = new HashSet<>();
        int max = -1, min = 14;
        for (int i : nums) {
            if (i == 0) continue;
            max = Math.max(max,i);
            min = Math.min(min,i);
            // 如果有重复的就返回false
            if (!res.add(i)) return false;
        }
        return max - min < 5;
    }
}

排序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for(int i = 0; i < 4; i++) {
            // 统计大小王的个数，用于寻找最小的牌
            if (nums[i] == 0) count++;
            // 若是重复了就直接返回false
            else if (nums[i] == nums[i + 1]) return false;
        }
        // 最大的牌减去最小的牌小于5d
        return nums[4] - nums[count] < 5;
    }
}

62.圆圈中最后剩下的数字

模拟转圈

直接按照题意进行转圈删除，最后一个剩下没被删除的就是答案了。

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

约瑟夫环公式

这题就算典序的约瑟夫环的问题。

约瑟夫环有一个递推公式。

F(n,m) = (f(n - 1,m) + m) % n

F(n,m)表示的是n个人报数，报到m的人会被杀掉，最终胜利者的编号，也就是这题的答案。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int lastRemaining(int n, int m) {
        int res = 0;
        // f(2,m)是最初的状态，需要加到F(n,m)才是最终答案
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}

63. 股票的最大利润

这题是经典的动态规划题，不过这一题只交易一次。所以只需要找到一个最小的数买进，最大的数卖出就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int res = 0, min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 找到一个更小的数就替换
            if (prices[i] <= min) {
                min = prices[i];
            } else {
                res = Math.max(res,prices[i] - min);
            }
        }
        return res;
    }
}

64. 求1+2+…+n

这题题目是不难的，但是题目的要求让这题变难了，不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

这里运用到了&&短路与的特性，判断了第一个子式后如果是false就不会进行判断第二个子式了。

1
2
3
4
5
6
7
class Solution {
    public int sumNums(int n) {
        int sum = n;
        boolean flag = n > 0 && (sum += sumNums(n - 1)) > 0;
        return sum;
    }
}

65. 不用加减乘除做加法

不用加减乘除，那就肯定是位运算了。然后就只能看题解了。

^表示两个数无进位的求和，比如16 + 4,无进位求和就是等于10的，相当于进位没有了。

&表示两个数进位的个数，比如6 + 4 ，答案是等于1的，因为进了一位，需要在左移一位才能等于10。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int add(int a, int b) {
        // 直到进位数为0，就停止循环
        while(b != 0) { 
            int c = (a & b) << 1;  
            a ^= b; 
            b = c; 
        }
        return a;
    }
}

66. 构建乘积数组

这题主要是除了当前元素其他元素都相乘，其实就算数左边的元素的乘积与右边元素的乘积的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] constructArr(int[] a) {
        if (a.length <= 1) return a;
        int[] res = new int[a.length];
        int left = 1;
        int right = 1;
        for(int i = 0; i < a.length; i++) {
            res[i] = left;
            left *= a[i];
        }
        for(int i = a.length - 1; i > -1; i--) {
            res[i] *= right;
            right *= a[i];
        }
        return res;
    }
}

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

这题主要总结节点的情况，该题的节点应该是分为三种的。

  1. p和q都在左子树
  2. p和q都在右子树
  3. p和q一个在左子树，一个在右子树（这种情况的节点就算二叉树的最近公共祖先）

了解了状态这题应该就不难了。

1
2
3
4
5
6
7
8
9
10
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.left,p,q);
        if (root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right,p,q);
        return root;
    }
}

68.2 二叉树的最近公共祖先

这题的分析跟上面的情况一样，只是判断子树的情况不太一样。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left == null) return right;
        if (right == null) return left;
        if (left != null && right != null) return root;
        return null;
    }
}