剑指Offer

发表于 | 分类于
字数统计: | 阅读时长 ≈

9.用两个栈实现队列

image-20220316110237876

思路：维护两个栈，第一个栈支持插入操作，第二个栈支持删除操作。

在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空，我们将第一个栈里的元素一个个弹出插入到第二个栈里，这样第二个栈里元素的顺序就是待删除的元素的顺序，要执行删除操作的时候我们直接弹出第二个栈的元素返回即可

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 CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
    	stack1 = new LinkedList<Integer>();
    	stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
		stack1.push(value);
    }
    
    public int deleteHead() {
        //如果第二个栈为空
		if (stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            return -1;
        } else {
            int deleteItem = stack2.pop();
            return deleteItem;
        }
    }
}

30.包含min函数的栈

image-20220316111044141

思路：

  • 建立一个ListNode结构类
  • MinStack类维护一个ListNode头节点，初始为null
  • push方法：头节点为null直接新建；头节点不为null时，在头结点之前插入一个节点，值为x，next指向头节点；将新的节点重新赋值给头节点，也就是每次push都将值插入头节点之前
  • pop方法：直接将头节点指向头节点的下一个节点，也就是每次pop头节点，从而实现后进后出的栈操作
  • top方法：直接返回头节点的值即可
  • min方法：直接返回头节点的min值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MinStack {
	
    //链表实现：每个节点加一个额外属性，作为当前最小值
    private Node head;
    
    /** initialize your data structure here. */
    public MinStack() {
		
    }
    
    public void push(int x) {
		if (head == null)
            head = new Node(x, x, null);
        else
            head = new Node(x, Math.min(head.min, x), head);
    }
    
    public void pop() {
		head = head.next;
    }
    
    public int top() {
		return head.val;
    }
    
    public int min() {
		return head.min;
    }
    
    private class Node {
        int val;
        int min;
        Node next;
        
        public Node (int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

思路：获取栈的最小值需要遍历整个栈，复杂度为O(N)，要将复杂度降为O(1)，可通过建立辅助栈实现

数据栈A用于存储所有元素，保证入栈函数、出栈函数、获取栈顶函数的正常逻辑

辅助栈B存储栈A中所有非严格降序的元素，则栈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
class MinStack {
    //两个队列实现
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(x, minStack.peek()));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

6.从尾到头打印链表

image-20220317132710595

思路：数组倒序存储（反转链表、栈均可）

  • 遍历获取链表长度
  • 从后向前按照索引填数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
		ListNode node = head;
        int len = 0;
        while (node != null) {
            len++;
            node=node.next;
        }
        int[] res = new int[len];
        while (head != null) {
            res[--len] = head.val;
            head = head.next;
        }
        return res;
    }
}

24.反转链表

image-20220317133142612

思路：迭代

在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
	public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            //tmp指向下一个节点
            ListNode tmp = cur.next;
            //指针反向
            cur.next = pre;
            //前进一步
            pre = cur;
            //cur前进一步
            cur = tmp;
        }
        return pre;
    }
}

35.复杂链表的复制

image-20220317133606574

思路：哈希表

利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的next和random引用指向即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
    	if (head == null) return head;
        //哈希表
        Map<Node, Node> map = new HashMap<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        //将拷贝的新的节点组成一个链表
        for (Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }
}

5.替换空格

image-20220318094918219

思路：遍历添加

在Java/Python等语言中，字符串都被设计成不可变的类型，即无法直接修改字符串的某一位字符，需要新建一个字符串实现。

  • 初始化一个StringBuilder
  • 遍历列表s中的每个字符
    • 当c为空格时：向res后添加字符串”%20”
    • 当c不为空格时：向res后添加字符c
  • 将列表res转化为字符串并返回
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public String replaceSpace(String s) {
		StringBuilder sb = new StringBuilder();
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

58.左旋转字符串

image-20220318095235462

思路：字符串切片/列表遍历拼接/字符串遍历拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String reverseLeftWords(String s, int n) {
        //public String substring(int beginIndex)
        //public String substring(int beginIndex, int endIndex)
        //字符串切片
		//return s.substring(n) + s.substring(0, n);        
        //列表遍历拼接
        StringBuilder res = new StringBuilder();
        for (int i=n; i<s.length(); i++)
            res.append(s.charAt(i));
        for (int i=0; i<n; i++) {
            res.append(s.charAt(i));
        return res.toString();
        }
    }
}

3.数组中重复的数字

image-20220320223654399

思路：遍历数组

由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前数字是重复数字。

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

53.在排序数组中查找数字

image-20220320224849123

思路：二分查找

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

要求统计数字target的出现次数，可转化为：使用二分法分别找到左边界和右边界

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

53.0~n-1中缺失的数字

image-20220321093634050

思路：排序数组的搜索问题，首先想到二分法解决

根据题意，数组可以按照以下规则划分为两部分

  • 左子数组：nums[i] = i
  • 右子数组：nums[i] ≠ i

缺失的数字等于右子数组的首位元素对应的索引；因此考虑二分法查找右子数组的首位元素

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        int i=0, j=nums.length-1;
        while (i<=j) {
            int m=(i+j)/2;	//计算中点
            if (nums[m] == m) i = m+1;	//右子数组的首位元素 一定在区间[m+1, j]中，因此执行i=m+1
            else j = m-1;	//左子数组的末尾元素 一定在区间[i,m-1]中，因此执行j=m-1
        }
        return i;	//跳出时，变量i和j分别指向 右子数组的首位元素 和 左子数组的末位元素。因此返回i即可
    }
}

4.二维数组中的查找

image-20220322224247970

思路：利用从上到下递增，从左到右递增的特点

将矩阵逆时针旋转45°，并将其转化为图形式，其类似于二叉搜索树

通过从“根节点”开始搜索，遇到比target大的元素就向左，反之向右，即可找到目标值target

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
		int i=matrix.length-1, j=0;
        while (i>=0 && j<matrix[0].length) {
            if (matrix[i][j] > target) i--;
            else if (matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
}

11.旋转数组的最小数字

image-20220322224818422

思路：排序数组的查找问题首先考虑使用二分法解决

寻找旋转数组的最小元素即为寻找右排序数组的首个元素

  • 初始化：声明i,j双指针分别指向nums数组左右两端
  • 循环二分：设m为每次二分的中点，可分为以下三种情况
    • 当nums[m] > nums[j]时：m一定在 左排序数组 中，即旋转点x一定在[m+1, j]闭区间内，因此执行i=m+1
    • 当nums[m] < nums[j]时：m一定在 右排序数组 中，即旋转点x一定在[i, m]闭区间内，因此执行j=m
    • 当nums[m] = nums[j]时：无法判断m在哪个排序数组中，即无法判断旋转点x在[i,m]还是[m+1, j]闭区间内，因此缩小判断范围，执行j=j-1
  • 返回值：当 i=j 时跳出二分循环，并返回 旋转点的值 nums[i]即可

image-20220322230750006

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minArray(int[] nums) {
		int i = 0, j = nums.length - 1;
        while (i<j) {
            int m = (i + j) / 2;
            if (nums[m] > nums[j]) i=m+1;	//m在左序列中
            else if (nums[m] < nums[j]) j = m;	//m在右序列中
            else j--;
        }
        return nums[i];
    }
}

补充思考：为什么本题二分法不用 nums[m]和nums[i] 作比较？

二分目的是判断 mm 在哪个排序数组中，从而缩小区间。而在nums[m]>nums[i]情况下，无法判断m在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中； i初始值无法确定在哪个排序数组中。

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

image-20220323094608551

思路：哈希表

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public char firstUniqChar(String s) {
		HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for (char c : sc)
            dic.put(c, !dic.containsKey(c));
        for (char c : sc)
            if (dic.get(c)) return c;
        return ' ';
    }
}

32_1.从上到下打印二叉树

image-20220323095407779

思路：从上到下打印，即按层打印。使用二叉树的广度优先搜索

BFS通常借助队列的先入先出特性来实现

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
		if (root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>() {{add(root);}};
        ArrayList<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            //移出并返回队列头部的元素，如果队列为空，则返回null
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for (int i=0; i<ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
}

32_2.从上到下打印二叉树

image-20220323110229286

思路：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印

  • BFS循环
    1. 新建一个临时列表，用于存储当前层打印结果
    2. 当前层打印循环
    3. 将当前层结果添加入res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for (int i=queue.size(); i>0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

32_3.从上到下打印二叉树

image-20220323111010622

思路：层序遍历+双端队列

利用双端队列的两端皆可添加元素的特性，设打印列表(双端队列)tmp，并规定

  • 奇数层 添加到tmp尾部
  • 偶数层 添加到tmp头部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for (int i=queue.size(); i>0; i--) {
                TreeNode node = queue.poll();
                if (res.size() % 2 == 0) tmp.addLast(node.val);	//偶数层->队列头部
                else tmp.addFirst(node.val);	//奇数层->队列尾部
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

26.树的子结构

思路：若树B是树A的子结构，则子结构的根节点可能为树A的任意一个节点。因此，判断树B是否是树A的子结构，需要完成以下两步工作

  1. 先遍历树A中每个节点a
  2. 判断树A中以a为根节点的子树是否包含树B
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
		return (A!=null && B!=null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    
    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);
    }
}

27.二叉树的镜像

思路：递归法

根据定义，递归遍历二叉树，交换每个节点的左右子节点，即可生成二叉树的镜像

  1. 终止条件：当节点root为空时，则返回null
  2. 递推工作
    1. 初始化节点tmp，用于暂存root的左子节点
    2. 开启递归右子节点，并将返回值作为root的左子节点
    3. 开启递归左子节点，并将返回值作为root的右子节点
  3. 返回值：返回当前节点root
1
2
3
4
5
6
7
8
9
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
		if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

28.对称的二叉树

思路：从顶至底递归判断

1
2
3
4
5
6
7
8
9
10
class Solution {
    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);
    }
}

10_1.斐波那契数列

image-20220324133705521

思路：

  1. 动态规划：最佳解法
  2. 递归：大量重复的递归计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = (p + q) % MOD;
        }
        return r;
    }
}

10_2.青蛙跳台阶问题

image-20220324135825095

思路：动态规划

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

63.股票的最大利润

image-20220324141414661

思路：动态规划

  • 状态定义：设动态规划列表dp，dp[i]代表以price[i]为结尾的子数组的最大利润
  • 转移方程：由于限定“买卖该股票一次”，因此前i日最大利润dp[i]等于前i-1日最大利润dp[i-1]和第i日卖出的最大利润中的最大值
  • 初始状态：dp[0]=0，即首日利润为0
  • 返回值：dp[n-1]，其中n为dp列表长度
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
		int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

42.连续子数组的最大和

image-20220324142018725

思路：动态规划

  • 状态定义：dp[i]代表以元素nums[i]为结尾的连续子数组最大和
  • 转移方程：若dp[i-1]<=0，说明dp[i-1]对dp[i]产生负贡献，即dp[i-1]+nums[i]还不如nums[i]本身大
  • 初始状态：dp[0]=nums[0]，即以nums[0]结尾的连续子数组最大和为nums[0]
  • 返回值：返回dp列表中的最大值，即全局最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
		int res = nums[0];
        int former = 0;	//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
        int cur = nums[0];	//用于记录dp[i]的值
        for (int num : nums) {
            cur = num;
            cur += Math.max(former, 0);
            res = Math.max(res, cur);
            former = cur;
        }
        return res;
    }
}

47.礼物的最大价值

image-20220324144141260

思路：动态规划

单元格只可能从上边或左边到达

  • 状态定义：dp(i,j)代表从棋盘的左上角开始，到达单元格(i,j)时能拿到礼物的最大累计价值
  • 转移方程：四种情况
  • 初始状态：dp[0][0]=price[0][0]
  • 返回值：dp[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxValue(int[][] grid) {
	int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) continue;
                if(i == 0) grid[i][j] += grid[i][j - 1] ;
                else if(j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m-1][n-1];
    }
}

46. 把数字翻译成字符串

image-20220325113836843

Picture1.png

思路：动态规划

  • 状态定义：dp[i]代表以Xi为结尾的数字的翻译方案数量
  • 转移方程：若Xi和Xi-1组成的两位数字可以被翻译，则dp[i]=dp[i-1]+dp[i-2]；否则dp[i]=dp[i-1]
  • 初始状态：dp[0]=dp[1]=1
  • 返回值：dp[n]，即此数字的翻译方案数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int translateNum(int num) {
		//字符串遍历
        String s = String.valueOf(num);
        int a=1, b=1;	//空间优化
        for (int i=2; i<=s.length(); i++) {
            String tmp = s.substring(i-2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : b;
            a = b;
            b = c;
        }
        return b;
    }
}

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

image-20220325132529375

思路：动态规划降低时间复杂度

使用暴力法时间复杂度N^3

  • 状态定义：dp[j]代表以字符s[j]为结尾的“最长不重复子字符串”的长度
  • 转移方程：固定右边界j，设字符s[j]左边距离最近的相同字符为s[i]，即s[i]=s[j]
    • 当 i < 0，即s[j]左边无相同字符，则 dp[j] = dp[j-1] + 1；
    • 当dp[j - 1] < j - i，说明字符s[i]在子字符串dp[j-1]区间之外 ，则dp[j]=dp[j-1]+1；
    • 当dp[j−1]≥j−i，说明字符 s[i]在子字符串 dp[j-1]区间之中 ，则dp[j]的左边界由s[i]决定，即 dp[j] = j - i；
  • 返回值：max(dp)，即全局“最长不重复子字符串”的长度
  • Picture1.png
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int lengthOfLongestSubstring(String s) {
		Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;	//空间复杂度优化
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); 	//获取索引i
            dic.put(s.charAt(j), j);		//更新哈希表
            tmp = tmp < j-i ? tmp + 1 : j - i;	//dp[j-1] -> dp[j]
            res = Math.max(res, tmp);		// max(dp[j - 1], dp[j])
        }
        return res;
    }
}

思路：双指针 + 哈希表

  • 哈希表统计字符s[j]最后一次出现的索引
  • 根据上轮左指针i和dic[s[j]]，每轮更新左边界i，保证区间[i+1,j]内无重复字符且最大
  • 更新结果
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

18.删除链表的节点

image-20220326102942907

思路：双指针

删除节点需要两步：定位节点、修改引用

  1. 定位节点：遍历链表，直到head.val == val时跳出，即可定位目标节点
  2. 修改引用：设节点cur的前驱节点为pre，后继节点为cur.next；则执行pre.next=cur.next，即可实现删除cur节点
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
		if (head.val == val) return head.next;
        ListNode pre = head, cur = head.next;
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if (cur != null) pre.next = cur.next;
        return head;
    }
}

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

image-20220326104017085

思路：双指针

使用双指针可以不用统计链表长度

  1. 初始化：双指针都指向头节点
  2. 构建双指针距离：前指针先向前走k步
  3. 双指针共同移动：循环中，双指针每轮都向前走一步，直至前指针走过链表尾结点时跳出循环。此时，后指针与尾结点距离k-1，即后指针指向倒数第k个节点
  4. 返回值：返回后指针即可
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
		ListNode former = head, latter = head;
        for(int i = 0; i < k; i++)
            former = former.next;
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

25.合并两个排序的链表

image-20220327110656807

思路：双指针

  1. 初始化：伪头节点，节点cur指向dum
  2. 循环合并：当l1或l2为空时跳出
  3. 合并剩余尾部
  4. 返回值：合并链表在伪节点dum之后，因此返回dum.next即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode(0), cur = dum;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dum.next;
    }
}

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

image-20220327110829126

思路：双指针

headA的节点数量为a，headB的节点数量为b，两链表的公共尾部的节点数量c，则有

  • 头节点headA到node前，共有a-c个节点
  • 头节点headB到node前，共有b-c个节点

指针A遍历完链表A再遍历链表B，指针B遍历完链表B再遍历链表A，当指针A和B重合时，若不指向null，则为目标节点

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

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

image-20220328113226279

思路：双指针

双指针分列数组左右两端，循环执行：

  1. 指针i从左往右寻找偶数
  2. 指针j从右往左寻找奇数
  3. 将偶数nums[i]和奇数nums[j]交换
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] exchange(int[] nums) {
		int i=0, j=nums.length - 1, tmp;
        while (i<j) {
            while (i<j && (nums[i] & 1) == 1) i++;
            while (i<j && (nums[j] & 1) == 0) j--;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

57.和为s的两个数字

image-20220328113807235

思路：双指针

利用排序数组的条件，使用双指针将空间复杂度降至O(1)

  1. 初始化：双指针位于数组左右两端
  2. 循环搜索：当双指针相遇时跳出
  3. 返回空数组，代表无和为target的数字组合
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
		int i=0, j=nums.length-1;
        while (i<j) {
            int s = nums[i]+nums[j];
            if (s<target) i++;
            else if (s>target) j--;
            else return new int[] {nums[i], nums[j]};
        }
        return new int[0];
    }
}

58_1.翻转单词顺序

image-20220328123309870

思路：双指针

  • 倒序遍历字符串s，记录单词左右索引边界i,j
  • 每确定一个单词的边界，则将其添加至单词列表res
  • 最终，将单词列表拼接为字符串，并返回即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
		s = s.trim();
        int j = s.length()-1, i=j;
        StringBuilder res = new StringBuilder();
        while (i>=0) {
            while (i>=0 && s.charAt(i) != ' ') i--;	//搜索首个空格
            res.append(s.substring(i+1, j+1)+" ");  //添加单词
            while (i>=0 && s.charAt(i) == ' ') i--;	//跳过单词间空格
            j = i;		//j指向下一个单词的尾字符
        }
        return res.toString().trim();	//转化为字符串并返回
    }
}

12.矩阵中的路径

image-20220329132107365

思路：深度优先搜索+剪枝

  • 递归参数：当前元素在矩阵board中的行列索引i和j，当前目标字符在word中的索引k
  • 终止条件
    1. 返回false：行或列索引越界；当前矩阵元素与目标字符不同；当前元素已访问过
    2. 返回true:k=len(word)-1，即当前字符串word已全部匹配
  • 递推工作
    1. 标记当前矩阵元素：将board[i][j]修改为空字符，代表已经访问过
    2. 搜索下一单元格：朝当前元素的上下左右四个方向开启下层递归，使用或连接，并记录结果至res
    3. 还原当前矩阵元素：将board[i][j]元素还原至初始值
  • 返回值：返回布尔量res，代表是否搜索到目标字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean exist(char[][] board, String word) {
		char[] words = word.toCharArray();
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = ' ';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}

13.机器人的运动范围

image-20220329132205453

思路：搜索与回溯-深度优先遍历

  • 递归参数：当前元素在矩阵中的行列索引i和j，两者的数位和si,sj
  • 终止条件：
    1. 行列索引越界
    2. 数位和超出目标值
    3. 当前元素已经访问过
  • 递推工作：
    1. 标记当前单元格：将索引(i,j)存入visited中，代表此单元格已经被访问
    2. 搜索下一单元格：计算当前元素的下、右两个方向元素的数位和，并开启下层递归
  • 回溯返回值：返回1+右方搜索的可达解总数+下方搜索的可达解总数,代表从本单元格递归搜索的可达解总数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
		this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if (i>=m || j>=n || k<si+sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1+dfs(i+1, j, (i+1)%10 != 0 ? si+1 : si-8, sj) + dfs(i, j+1, si, (j+1)%10 != 0 ? sj+1 : sj-8);
    }
}

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

image-20220331124230620

思路：先序遍历+路径记录

  • 初始化：结果列表res，路径列表path
  • 返回值：返回res即可
  • 递推工作：
    1. 路径更新：将当前节点值root.val加入路径path
    2. 目标值更新：tar = tar-root.val
    3. 路径记录：当root为叶节点且路径和等于目标值，则将此路径path加入res
    4. 先序遍历：递归左右子节点
    5. 路径恢复：向上回溯前，需将当前节点从路径path中删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
		recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) { 
        if (root == null) return ;
        path.add(root.val);
        tar -= root.val;
        if (tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

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

image-20220331124411503

思路：中序遍历

使用中序遍历访问树的各节点cur；并在访问每个节点时构建cur和前驱节点pre的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可

  1. 终止条件：当节点cur为空，代表越过叶节点，直接返回
  2. 递归左子树
  3. 构建链表：
    1. 当pre为空时：代表正在访问链表头节点，记为head
    2. 当pre不为空时：修改双向节点引用，即pre.right=cur, cur.left=pre
    3. 保存cur:更新pre=cur，即节点cur是后继节点的pre
  4. 递归右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if (root==null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if (cur == null) return;
        dfs(cur.left);
        if (pre != null) pre.right = cur;
        else head = cur;	//尾节点指向头节点
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

54.二叉搜索树的第k大节点

image-20220401153927291

思路：转化为求“此树的中序遍历倒序的第k个节点”

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

45.把数组排成最小的数

image-20220402124955223

思路：求拼接起来的最小数字，本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y,则规定排序判断规则为

  • 若拼接字符串x+y>y+x，则x>y
  • 反之，则x<y
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String minNumber(int[] nums) {
		String[] strs = new String[nums.length];
        for (int i=0; i<nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y)->(x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for (String s:strs)
            res.append(s);
        return res.toString();
    }
}

61.扑克牌中的顺子

image-20220402131055952

思路：

需满足如下条件

  1. 除大小王外，所有牌无重复
  2. 设此5张牌中最大的牌为max，最小的牌为min。需满足max-mix<5
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

40.最小的k个数

image-20220403165040979

思路:快速排序

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
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
		if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }
    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }
    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }
}

41.数据流中的中位数

image-20220414173712576

思路:建立一个 小顶堆 A 和 大顶堆 B，各保存列表的一半元素

设元素总数为 N = m + n，其中 m和 n分别为 A和 B中的元素个数

  1. 当m=n时，需向A添加一个元素。实现方法：将新元素 num插入至 B，再将 B堆顶元素插入至 A
  2. 当m!=n时，需向 B添加一个元素。实现方法：将新元素num插入至 A，再将 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
class MedianFinder {

    /** initialize your data structure here. */
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

55_1.二叉树的深度

image-20220404130847134

思路：后序遍历

递归实现

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

55_2.平衡二叉树

image-20220404130943563

思路：后序遍历+剪枝

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

64.求1+2+…+n

image-20220405124223267

思路：利用递归，逻辑运算符的短路效应

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

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

image-20220406131045411

思路:迭代

  1. 循环搜索：当节点root为空时跳出
    1. 当p,q都在root的右子树中，则遍历至root.right
    2. 当p,q 都在 root的左子树中，则遍历至 root.left
    3. 否则，说明找到了最近公共祖先，跳出
  2. 返回值：最近公共祖先root
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}

68_2.二叉树的最近公共祖先

image-20220406132058952

思路：考虑通过递归对二叉树进行==先序遍历==，当遇到节点p或q时返回。从底至顶回溯，当节点p,q在节点root的异侧时，节点root即为最近公共祖先，则向上返回root

  1. 终止条件
    1. 当越过叶节点，则直接返回null
    2. 当root等于p,q，则直接返回root
  2. 递推工作
    1. 开启递归左子节点，返回值记为left
    2. 开启递归右子节点，返回值记为right
  3. 返回值：根据left,right，可展开为四种情况
    1. 当left和right同时为空：说明root的左右子树中都不包含p,q，返回null
    2. 当left和right同时不为空，说明p,q分别列在root的异侧，因此root为最近公共祖先，返回root
    3. 当left为空 ，right 不为空 ：p,q都不在 root的左子树中，直接返回 right。具体可分为两种情况：
      1. p,q 其中一个在 root的右子树中，此时right指向 p（假设为 p）；
      2. p,q 两节点都在 root的右子树中，此时的 right指向最近公共祖先节点
    4. 当left不为空 ，right为空：与情况3同理
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) return null; // 1.
        if(left == null) return right; // 3.
        if(right == null) return left; // 4.
        return root; // 2. if(left != null and right != null)
    }
}

7.重建二叉树

image-20220407131448929

思路：

  1. 前序遍历的首元素为树的根节点node的值
  2. 在中序遍历中搜索根节点node的索引，可将中序遍历划分为左子树|根节点|右子树
  3. 根据中序遍历中的左右子树的节点数量，可将前序遍历划分为根节点|左子树|右子树

通过以上三步，可确定三个节点：1.树的根节点；2.左子树根节点；3.右子树根节点

根据分治算法思想，对于树的左、右子树，仍可复用以上方法划分子树的左右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                          // 递归终止
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic.get(preorder[root]);			// 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;									    // 回溯返回根节点
    }
}

16.数值的整数次方

image-20220408131353688

思路：快速幂

二分法角度

  1. 当x=0时直接返回0
  2. 初始化res=1
  3. 当n<0时，把问题转化至n>=0的范围内
  4. 循环计算：当n=0时跳出
    1. 当n&1=1时，当前x乘入res
    2. 执行x=x^2
    3. 执行n右移一位
  5. 返回res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

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

image-20220408130004388

思路：递归分治

根据二叉搜索树的定义，可以通过递归，判断所有子树的正确性，若所有子树都正确，则此序列为二叉搜索树的后序遍历

  • 终止条件：当i>=j，说明此子树节点数量<=1,无需判别正确性，直接返回true
  • 递推工作
    1. 划分左右子树：遍历后序遍历的[i,j]区间元素，寻找第一个大于根节点的节点，索引记为m。
    2. 判断是否为二叉搜索树
      • 左子树区间内所有节点都已经满足条件了，只需要判断右子树区间即可
      • 右子树区间内所有节点应>postorder[j]。实现方式为遍历
  • 返回值：所有子树都需要正确才可判定正确
    1. p=j，判断此树是否正确
    2. recur(i,m-1):判断此树的左子树是否正确
    3. recur(m, j-1):判断此树的右子树是否正确
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean verifyPostorder(int[] postorder) {
		return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, 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 && recur(postorder, i, m-1) && recur(postorder, m, j-1);
    }
}

15. 二进制中1的个数

image-20220410210438876

思路：逐位判断

  • 若n&1=0，则n二进制最后一位为0；
  • 若n&1=1，则n二进制最后一位为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;
    }
}

65.不用加减乘除做加法

image-20220410210739120

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}
//递归
class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        
        // 转换成非进位和 + 进位
        return add(a ^ b, (a & b) << 1);
    }
}

56_1.数组中数字出现的次数

image-20220411134612917

思路：设两个只出现一次的数字x,y，由于x!=y，则x和y二进制至少有一位不同，据此可以将nums拆分为分别包含x和y的两个子数组

易知两个子数组都满足 除一个数字之外，其他数字都出现了两次 因此，仿照以上简化问题的思路，分别对两个子数组遍历执行异或操作，即可得到两个只出现一次的数字x,y

  1. 遍历nums执行异或
  2. 循环左移计算m (x⊕y的首位1)
  3. 拆分nums为两个子数组
  4. 分别遍历两个子数组执行异或
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] singleNumbers(int[] nums) {
        int x=0, y=0, n=0, m=1;
        for (int num : nums)	//1.遍历异或
            n ^= num;
        while ((n&m)==0)		//2.循环左移，计算m
            m<<=1;
        for (int num : nums){	//3.遍历nums分组
            if ((num & m) != 0) x^=num;
            else y^=num;
        }
        return new int[]{x, y};	//返回出现一次的数字
    }
}

56_2.数组中数字出现的次数

image-20220411140142626

思路：出现三次的数字，各二进制位出现的次数都是3的倍数。因此，统计所有数字的各二进制位中1出现次数，并对3求余，结果则为只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int singleNumber(int[] nums) {
		//遍历统计
        int[] counts = new int[32];
        for (int num:nums) {
            for (int j=0; j<32; j++) {
                counts[j] += num & 1;	//获取二进制数字num的最右一位
                num >>>=1;	//无符号右移操作
            }
        }
        int res=0, m=3;
        for (int i=0; i<32; i++) {
            //左移操作和或运算，将counts数组中各二进位的值恢复
            res <<=1;
            res |= counts[31-i]%m;
        }
        return res;
    }
}

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

image-20220411144607697

思路：哈希表统计&数组排序&摩尔投票法

摩尔投票法核心理念为票数正负抵消，为本题最佳解法

记数组首个元素为n1,众数为x，遍历并统计票数。当票数和为0时，剩余数组的众数一定不变

利用此特性，每轮假设发生票数和=0都可以缩小剩余数组区间。当遍历完成时，最后一轮假设的数字即为众数。

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

66.构建乘积数组

image-20220411150235894

思路：根据主对角线（全为1）可将表格分为上三角和下三角两部分。分别迭代计算下三角和上三角两部分的乘积

  1. 初始化：数组B，其中B[0]=1，辅助变量tmp=1
  2. 计算B[i]的下三角各元素的乘积，直接乘入B[i]
  3. 计算B[i]的上三角各元素的乘积，记为tmp，并乘入B[i]
  4. 返回B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] constructArr(int[] a) {
		int len = a.length;
        if (len == 0) return new int[0];
        int[] b = new int[len];
        b[0]=1;
        int tmp=1;
        for (int i=1; i<len; i++){
            b[i] = b[i-1]*a[i-1];
        }
        for (int i=len-2; i>=0; i--){
            tmp *= a[i+1];
            b[i] *= tmp;
        }
        return b;
    }
}

14_1.剪绳子

image-20220412150426135

思路：

  1. 当所有绳长度相等时，乘积最大
  2. 最优的绳段长度为3
1
2
3
4
5
6
7
8
9
class Solution {
    public int cuttingRope(int n) {
		if (n<=3) return n-1;
        int a=n/3, b=n%3;
        if (b==0) return (int)Math.pow(3, a);
        if (b==1) return (int)Math.pow(3, a-1)*4;	//将1+3转换成2+2
        return (int)Math.pow(3, a)*2;		//返回3^a * 2
    }
}

57_2.和为s的连续正数序列

image-20220412151212168

思路：滑动窗口

  1. 初始化：左边界i=1,右边界j=2,元素和s=3,结果列表res;
  2. 循环：当i>=j时跳出
    • 当s>target时，向右移动左边界，更新元素和
    • 当s<target时，向右移动右边界，更新元素和
    • 当s=target时，记录连续整数序列，并向右移动左边界
  3. 返回res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] findContinuousSequence(int target) {
		int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i<j){
            if (s==target) {
                int[] ans = new int[j-i+1];
                for(int k=i; k<=j; k++)
                    ans[k-i] = k;
                res.add(ans);
            }
            if (s>=target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

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

image-20220412152204133

1
2
3
4
5
6
7
8
9
10
class Solution {
    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;
    }
}

29.顺时针打印矩阵

image-20220413131355027

思路：模拟

  1. 空值处理
  2. 初始化：四个边界，结果列表res
  3. 循环打印
    1. 根据边界打印，即将元素按顺序添加至列表res尾部
    2. 边界向内收缩1
    3. 判断是否打印完毕，若打印完毕则跳出
  4. 返回值：res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

31.栈的压入、弹出序列

image-20220413131552983

思路：模拟

  1. 初始化：辅助栈stack,弹出序列的索引i
  2. 遍历压栈序列：各元素记为num
    1. 元素num入栈
    2. 循环出栈：若stack的栈顶元素=弹出序列元素popped[i]，则执行出栈与i++
  3. 返回值：若stack为空，则此弹出序列合法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
		Stack<Integer> stack = new Stack<>();
        int i=0;
        for(int num:pushed) {
            stack.push(num);
            while(!stack.isEmpty() && stack.peek()==popped[i]) {
                //循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

20.表示数值的字符串

image-20220413131714196

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 Solution {
    public boolean isNumber(String s) {
        // s为空对象或 s长度为0(空字符串)时, 不能表示数值
        if(s == null || s.length() == 0) return false; 
        // 标记是否遇到数位、小数点、‘e’或'E'
        boolean isNum = false, isDot = false, ise_or_E = false; 
        // 删除字符串头尾的空格，转为字符数组，方便遍历判断每个字符
        char[] str = s.trim().toCharArray();  
        for(int i=0; i<str.length; i++) {
            // 判断当前字符是否为 0~9 的数位
            if(str[i] >= '0' && str[i] <= '9') isNum = true; 
            else if(str[i] == '.') { // 遇到小数点
                // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
                if(isDot || ise_or_E) return false; 
                isDot = true; // 标记已经遇到小数点
            }
            else if(str[i] == 'e' || str[i] == 'E') { // 遇到‘e’或'E'
                // ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
                if(!isNum || ise_or_E) return false; 
                ise_or_E = true; // 标记已经遇到‘e’或'E'
            // 重置isNum，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
                isNum = false; 
            }
            else if(str[i] == '-' ||str[i] == '+') { 
                // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
                if(i!=0 && str[i-1] != 'e' && str[i-1] != 'E') return false; 
            }
            else return false; // 其它情况均为不合法字符
        }
        return isNum;
    }
}

67.把字符串转换成整数

image-20220413131801360

思路：

  1. 首部空格：删除即可
  2. 符号位：三种情况，新建一个变量保存符号位，返回前判断正负即可
  3. 非数字字符：遇到首个非数字的字符时，应立即返回
  4. 数字字符
    1. 字符转数字：数字的ASCII码与0的ASCII码相减即可
    2. 数字拼接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int strToInt(String str) {
        char[] c = str.trim().toCharArray();
        if(c.length == 0) return 0;
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 1, sign = 1;
        if(c[0] == '-') sign = -1;
        else if(c[0] != '+') i = 0;
        for(int j = i; j < c.length; j++) {
            if(c[j] < '0' || c[j] > '9') break;
            if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (c[j] - '0');
        }
        return sign * res;
    }
}

59_1.滑动窗口的最大值

image-20220413131910097

思路：单调队列

  1. 初始化：双端队列deque，结果列表res
  2. 滑动窗口：左边界范围i∈[1-k, n-k],右边界范围j∈[0,n-1]
    1. 若i>0且队首元素deque[0]=被删元素nums[i-1];则队首元素出队
    2. 删除deque内所有<nums[j]的元素，以保持deque递减
    3. 将nums[j]添加至deque尾部
    4. 若已形成窗口(i>=0)：将窗口最大值（即队首元素deque[0]）添加至列表res
  3. 返回值：返回结果列表res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int j=0, i=1-k; j<nums.length; i++,j++) {
            //删除deque中对应的nums[i-1]
            if(i>0 && deque.peekFirst() == nums[i-1])
                deque.removeFirst();
            //保持deque递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast();
            deque.addLast(nums[j]);
            //记录窗口最大值
            if(i>=0)
                res[i] = deque.peekFirst();
        }
        return res;
    }
}

59_2.队列的最大值

image-20220413132058393

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 MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;
    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    public int max_value() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }
    public void push_back(int value) {
        queue.offer(value);
        while(!deque.isEmpty() && deque.peekLast() < value)
            deque.pollLast();
        deque.offerLast(value);
    }
    public int pop_front() {
        if(queue.isEmpty()) return -1;
        if(queue.peek().equals(deque.peekFirst()))
            deque.pollFirst();
        return queue.poll();
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

37.序列化二叉树

image-20220414163345860

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

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

38.字符串的排列

image-20220414163440986

思路：回溯法

  1. 终止条件：当x=len(c)-1时，代表所有位已固定，则将当前组合c转化为字符串并加入res，并返回
  2. 递推参数：当前固定位x
  3. 递推工作：初始化一个Set，用于排除重复的字符；将第x位字符与i∈[x,len(c)]字符分别交换，并进入下一层递归
    1. 剪枝：若c[i]在set中，代表其实重复字符，因此剪枝
    2. 将c[i]加入Set，以便之后遇到重复字符时剪枝
    3. 固定字符：将字符c[i]和c[x]交换，即固定c[i]为当前位字符
    4. 开启下层递归：调用dfs(x+1)，即开始固定第x+1个字符
    5. 还原交换：将字符c[i]与c[x]交换（还原之前的交换）
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 {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
		c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if (x == c.length-1) {
            res.add(String.valueOf(c));	//添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i=x; i<c.length; i++) {
            if(set.contains(c[i])) continue;	//重复 因此剪枝
            set.add(c[i]);
            swap(i,x);	//交换 将c[i]固定在第x位
            dfs(x+1);	//开启固定第x+1位字符
            swap(i,x);	//恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

19.正则表达式匹配

image-20220414174429975

思路：动态规划

1
2
3
4
5
class Solution {
    public boolean isMatch(String s, String p) {
		
    }
}

49.丑数

image-20220414174523999

思路：动态规划

  • 状态定义：设动态规划列表dp，dp[i]代表第i+1个丑数
  • 转移方程：
    1. 当索引a,b,c满足以下条件时，dp[i]为三种情况的最小值
    2. 每轮计算dp[i]后，需要更新索引a,b,c的值，使其始终满足方程条件。实现方法：分别独立判断dp[i]和dp[a]x2,dp[b]x3,dp[c]x5的大小关系，若相等则相应索引a,b,c加1

dp[a]×2>dp[i−1]≥dp[a−1]×2 dp[b]×3>dp[i−1]≥dp[b−1]×3 dp[c]×5>dp[i−1]≥dp[c−1]×5

dp[i] = min(dp[a]x2, dp[b]x3, dp[c]x5)

  • 初始状态：dp[0]=1，即第一个丑数为1
  • 返回值：dp[n-1]，即返回第n个丑数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int nthUglyNumber(int n) {
        int a=0,b=0,c=0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i=1; i<n; i++) {
            int n2 = dp[a]*2, n3 = dp[b]*3, n5=dp[c]*5;
            dp[i] = Math.min(Math.min(n2,n3),n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n-1];
    }
}

60.n个骰子的点数

image-20220415204852173

思路：动态规划

可通过子问题的解f(n-1)可递推计算出f(n)，而输入一个骰子的解f(1)已知，因此可通过解f(1)依次递推出任意解f(n)

由于新增骰子的点数只可能为1至6，因此概率f(n-1,x)仅与f(n,x+1),f(n,x+2)……f(n,x+6)相关。因而，遍历f(n-1)中各点数和的概率，并将其相加至f(n)中所有相关项，即可完成f(n-1)至f(n)的递推

通常做法是声明一个二维数组dp, dp[i][j]代表前i个骰子的点数和j的概率，并执行状态转移。而由于dp[i]仅由dp[i-1]递推得出，为降低空间复杂度，只建立两个一维数组dp和tmp交替前进即可

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

51.数组中的逆序对

image-20220415214612858

思路：

  1. 终止条件：当l>=r时，代表子数组长度为1，此时终止划分
  2. 递归划分：计算数组中点m,递归划分左子数组和右子数组
  3. 合并与逆序对统计
    1. 暂存数组nums闭区间[l,r]内的元素至辅助数组tmp
    2. 循环合并：设置双指针i,j分别指向左右子数组的首元素
      • 当i=m+1时：代表左子数组已合并完，因此添加右子数组当前元素tmp[j]，并执行j=j+1
      • 否则，当j=r+1时：代表右子数组已合并完，因此添加左子数组当前元素tmp[i],并执行i=i+1
      • 否则，当tmp[i]<=tmp[j]:添加左子数组当前元素tmp[i，并执行i=i+1
      • 否则添加右子数组当前元素tmp[j]，并执行j=j+1；此时构成m-i+1个逆序对，统计添加至res
  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
class Solution {
    int[] nums, tmp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length-1);
    }
    private int mergeSort(int l, int r) {
        //终止条件
        if(l>=r) return 0;
        //递归划分
        int m=(l+r)/2;
        int res = mergeSort(l,m)+mergeSort(m+1, r);
        //合并阶段
        int i=l,j=m+1;
        for(int k=l;k<=r;k++)
            tmp[k] = nums[k];
        for(int k=l;k<=r;k++) {
            if(i==m+1)
                nums[k]=tmp[j++];
            else if(j==r+1||tmp[i]<=tmp[j])
                nums[k]=tmp[i++];
            else {
                nums[k]=tmp[j++];
                res+=m-i+1;	//统计逆序对
            }
        }
        return res;
    }
}

14_2.剪绳子

image-20220415223334179

思路：贪心算法

  1. 如果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1
  2. 如果 n == 4，返回4
  3. 如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段；每次乘法操作后记得取余就行
  4. 以上2和3可以合并
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int cuttingRope(int n) {
        if(n < 4){
            return n - 1;
        }
        long res = 1;
        while(n > 4){
            res  = res * 3 % 1000000007;
            n -= 3;
        }
        return (int) (res * n % 1000000007);
    }
}