【数据结构与算法】LeetCode：剑指Offer30天计划

第 1 天栈与队列

1. 剑指 Offer 09. 用两个栈实现队列

思路：

设置栈 1、2，
添加元素时直接在栈 1 中压入元素即可
删除元素时：如果栈 2 不为空则直接将 2 中元素弹出，如果 2 为空，则将 1 中元素全部弹出并依次压住 2 中，再将 2 的栈顶元素弹出（如果栈 2 仍然为空，则说明栈 1 也为空，返回 -1）

代码：

class CQueue {  

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

    public CQueue() {
        // 初始化两个栈
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        // 栈2空则将1中元素全部压入2中
        if (stack2.isEmpty()) 
            while (!stack1.isEmpty()) stack2.push(stack1.pop());
        if (stack2.isEmpty()) return -1;
        else 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();
 */

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

思路：

push() 中只需要每次把当前最小值与新的值 x 作比较并更新最小值就能解决
pop() 时如果当前值是最小值，就得用前一个最小值代替当前最小值，但是再次 pop() 又得有前前个最小值，故考虑使用一个栈 min 来保存最小值序列。在这个栈中，每次使用 push() 需要更新最小值时就把新的最小值压入栈中，这样，栈 min 的栈顶元素就是当前栈 stack 的最小值

代码：

class MinStack {

    /** initialize your data structure here. */
    
    LinkedList<Integer> stack;
    LinkedList<Integer> min;

    public MinStack() {
        stack = new LinkedList<>();
        min = new LinkedList<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (min.isEmpty() || min.peek() >= x) 
            min.push(x);
    }
    
    public void pop() {
        if (stack.pop().equals(min.peek())) 
            min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return min.peek();
    }
}

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

第 2 天链表

1. 剑指 Offer 06. 从尾到头打印链表

思路一：

使用辅助栈存储链表信息，建立数组保存从站内依次弹出的元素

class Solution {
    public int[] reversePrint(ListNode head) {
        我的-辅助栈
        LinkedList<Integer> stack = new LinkedList<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.pop();
        }
        return res;
    }
}

思路二：

遍历链表得到链表的长度，然后顺序遍历链表，在数组中逆序添加元素

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        cur = head;
        int[] res = new int[count];
        for (int i = count - 1; i >= 0; i--) {
            res[i] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}

2. 剑指 Offer 24. 反转链表

思路：

设置变量 pre 保存前一个结点

代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

3. 剑指 Offer 35. 复杂链表的复制

（通过建立新的 Node 结点来复制原来的链表，而不是将原来结点的引用当作是新结点）

思路一（哈希表）：

建立一个包含 <原结点，新节点> 的哈希表
根据原节点的前后关系建立新节点的前后关系
根据原节点的 random 指针建立新节点的 random 指针

/*
// 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;
        HashMap<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);			// 建立 next 指针
            map.get(cur).random = map.get(cur.random);		// 建立 random 指针
        }
        return map.get(head);
    }
}

思路二（原地修改）：

初始链表：1—>2->3
将新结点拷贝到原结点之后：1->1'->2->2'->3->3'
分离结点：
- 1->2->3
- 1'->2'->3'

class Solution {
    public Node copyRandomList(Node head) {
        // 原地修改法
        if (head == null) return null;
        // 原结点后拷贝新结点
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        // 建立新结点的 random 指针
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = node.next;
            newNode.random = (node.random != null) ? node.random.next : null;
        }
        // 分离链表
        Node newHead = head.next;
        for (Node node = head, temp = null; node != null && node.next != null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }
        return newHead;
    }
}

第 3 天字符串

1. 剑指 Offer 05. 替换空格

简单，略

2. 剑指 Offer 58 - II. 左旋转字符串

简单，略

第 4 天查找算法（简单）

1. 剑指 Offer 03. 数组中重复的数字

思路一（辅助数组）：

数组中的数的范围是 0 ~ n - 1，故可以使用一个辅助数组 arr（初始化元素为 0）来判断一个数是否出现过
遍历数组：
- 若 arr[num] 值为 0 ，说明该数之前未出现过，则将 arr[num] 的值改为 1
- 若 arr[num] 值为 1 ，说明该数之前出现过，返回 arr[num]

class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] arr = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) 
            arr[i] = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (arr[nums[i]] == 1) return nums[i];
            arr[nums[i]] = 1;
        }
        return -1;
    }
}

该方法采用的是空间换时间的策略，时间复杂度可以达到 O(n)，空间复杂度为 O(n)

同样的可以使用一个集合来保存 arr 中的元素

思路二（原地置换法）：

class Solution {
    public int findRepeatNumber(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) 
                    return nums[i];
                temp = nums[i];
                nums[i] = nums[nums[i]];
                nums[nums[i]] = temp;
            }
        }
        return -1;
    }
}

这种方法不需要使用额外的辅助空间，是算法的进一步优化，大大降低了空间复杂度

时间复杂度可以达到 O(n)，空间复杂度为 O(1)

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

思路一（顺序遍历）：

顺序遍历数组，到目标值后开始计数，到下一个数时停止计数，结束遍历

class Solution {
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i = 0; i < nums.length && nums[i] <= target; i++) {
            if (nums[i] == target) count++;
        }
        return count;	
    }       
}

思路二（二分查找定界）：

顺序遍历没用充分利用到升序数组的特性，可以考虑采用二分查找提升效率

目标值是连续出现的，可以使用二分查找确定出目标值的上下边界，做差就能得到目标值的个数

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }

    public int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            // <= 是往右靠，能找到上边界
            if (nums[m] <= tar) 
                i = m + 1;
            else
                j = m - 1;
        }
        return i;
    }
}

一般给的题目千万不要掉以轻心，习惯了直接遍历，面试的时候也可能就被直接遍历过去了

升序（降序）数组多往二分查找的方向上想一想

顺序遍历时间复杂度：O(n)

优化后二分查找时间复杂度：O(logn)

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

思路一（顺序遍历）：

顺序遍历数组，遍历过程中判断当前值与其下标是否相等，不等则返回当前下标

需要注意几种特殊情况：

[0]：缺失 1
[1]：缺失 0
[0, 1, 2]：缺失 n

class Solution {
    public int missingNumber(int[] nums) {
        if (nums.length == 1 && nums[0] == 0) 
            return 1;
        if  (nums.length == 1 && nums[0] == 1)
            return 0;
        if (nums.length == nums[nums.length - 1] + 1) 
            return nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        return -1;
    }
}

思路二（二分查找）：

数组为升序数组，同样可以考虑使用二分查找进行优化

二分查找时：

若 nums[mid] == mid ：说明 mid 之前没有缺失数字
否则，说明 mid 之前就有缺失，令 r = mid - 1

循环结束，l就是缺失数字的下标

class Solution {
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == mid) 
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }
}

第 5 天查找算法（中等）

1. 剑指 Offer 04. 二维数组中的查找

思路：

站在矩阵右上角看，可以将矩阵当作是一个 BST 来处理，右上角元素为根节点，往左走数值减小，往下走，数值增大

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        int col = matrix[0].length - 1, row = 0;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target)
                return true;
            else if (matrix[row][col] < target)
                row++;
            else
                col--;
        }
        return false;
    }
}

这种题明显可以用暴力搜索解决，时间复杂度：O(n^2)，但是用暴力法就大概率被 pass 了

从右上角开始走，利用这个顺序关系可以在O(m+n)的复杂度下解决这个题

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

思路

可以顺序遍历，但是就慢了

数组是由升序数组旋转而成，同样可以考虑使用二分查找

当中间值小于最右侧的值时：说明右侧元素全部有序
当中间值大于最右侧的值时：说明左侧元素全部有序
当中间值等于最右侧的值时：说明最小值就在中间值与最右侧之间，不断逼近即可

class Solution {
    public int minArray(int[] numbers) {
        // 二分法
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}

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

思路一（辅助数组）：

使用一个大小为 26 的数组记录下每个字母出现的次数，再遍历一遍数组就能得到只出现一次的字符

但是！这样虽然能通过，可求出的只是按字母表顺序排列的第一个出现一次的字符，并不是数组中第一个只出现一次的字符，还是存在漏洞

class Solution {
    public char firstUniqChar(String s) {
        // 辅助数组（过了但是不太符合题意）
        int[] alph = new int[26];
        for (int i =  0; i < s.length(); i++) {
            alph[s.charAt(i) - 'a'] += 1;
        }
        for (int i =  0; i < s.length(); i++) {
            if (alph[s.charAt(i) - 'a'] == 1)
                return s.charAt(i);
        }
        return ' ';
}

思路二（链式哈希表）：

借助链式哈希表（LinkedHashMap<字符，是否是第一次出现>）来寻找第一个只出现一次的元素

class Solution {
    public char firstUniqChar(String s) {
        // 链式哈希表
        Map<Character, Boolean> dic = new LinkedHashMap<>();
        char strArr = s.toCharArray();
        for (c : strArr) 
            // true：未重复出现过 false：重复出现过
            dic.put(c, !dic.containsKey(c));
        for (Map.Entry<Character, Boolean> d : dic.entrySet())
            if (d.getValue())
                return d.getKey();
        return ' ';
    }
}

第 6 天搜索与回溯算法（树的层序遍历）

1. 剑指 Offer 32 - I. 从上到下打印二叉树

思路：

考察常规的层序遍历，借助队列就能实现

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            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;
    }
}

2. 剑指 Offer 32 - II. 从上到下打印二叉树 II

思路：

层序遍历的过程中，每次循环时队列中的元素个数即为当前层的元素个数

只要在循环中再嵌套一层循环for (int i = queue.size(); i > 0; i--)，不断将结点值加入 List 中就能实现分层打印

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<List<Integer>>();
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> temp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

3. 剑指 Offer 32 - II. 从上到下打印二叉树 II

思路：

分层层序遍历（如上题）的过程中，增加对当前所处层的判断即可

当前层为偶数层：顺序打印
当前层为奇数层：逆序打印

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<List<Integer>>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            LinkedList<Integer> temp = new LinkedList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                // 顺序打印
                if (res.size() % 2 == 0) temp.addLast(node.val);
                // 逆序打印
                else temp.addFirst(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

第 7 天搜索与回溯（树的递归）

1. 剑指 Offer 26. 树的子结构

思路：

判断 B 是否为 A 的子树，需要使用先序遍历对 A 的每一个结点进行遍历，来寻找一棵与 B 结构相同的子树

class Solution {
    // 主函数确定根的起点
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 排除特例
        if (A == null || B == null) return false;
        // 先序遍历
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    // 判断两棵树的结构是否相同
    boolean recur(TreeNode A, TreeNode B) {
        // B 先全部遍历完，说明结构相同
        if (B == null) return true;
        // A 先全部遍历完或者 A 与 B 的值不同，说明结构不同
        if (A == null || A.val != B.val) return false;
        // 判断子树是否相同
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

2. 剑指 Offer 27. 二叉树的镜像

思路：

通过递归交换左右子树

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
		if (root == null) return null;
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }
}

3. 剑指 Offer 28. 对称的二叉树

思路：

对称二叉树结点的左子树的左子树与右子树的右子树相同，左子树的右子树与右子树的左子树相同

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }

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

第 8 天动态规划(简单)

1. 剑指 Offer 10- I. 斐波那契数列

思路一（递归法）：

存在大量重复计算，时间复杂度高

思路二（动态规划—辅助数组）：

使用长度为 n 的辅助数组来保存斐波那契数列，减少递归算法中重复的计算

class Solution {
    public int fib(int n) {
        if(n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] %= 1000000007;
        }
        return dp[n];
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

思路三（动态规划—辅助变量）：

每一项都只与前两项有关，故在迭代时可以将辅助数组替换为两个辅助变量，大大减小时间复杂度

class Solution {
    public int fib(int n) {
        int a = 0, b = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

2. 剑指 Offer 10- II. 青蛙跳台阶问题🚩

思路：

青蛙每次只能只能跳一级或两级台阶，那么第 n 级台阶的跳法，应该是：
$$
f(n)=f(n-1)+f(n-2)
$$

让青蛙跳到倒数第二级台阶后，再跳一级
让青蛙跳到倒数第一级台阶后，再跳两级

初始状态：$f(0)=1,f(1)=1$

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;
    }
}

3. 剑指 Offer 63. 股票的最大利润

思路：

在遍历数组的过程中，维护一个最小值 min，最小值初试为prices[0]

如果prices[i]大于min，则更新利润res
否则说明当前的prices[i]比min还小，则更新min

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) 
            return 0;
        int res = 0, min = prices[0];
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] <= min)
                min = prices[i];
            else
                res = Math.max(res, prices[i] - min);
        }
        return res;
    }
}

第 9 天动态规划（中等）

1. 剑指 Offer 42. 连续子数组的最大和

思路：

定义状态数组 $dp[i]$ 来表示数组中从某个位置到 $i$ 的数最大和

初始状态 $dp[0] = nums[0]$

状态转移方程：$dp[i]=max(dp(i-1)+nums[i],nums[i])$

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i=1;i < nums.length;i++){
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            res = Math.max(max,dp[i]);
        }
        return res;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

进一步的，我们可以原地修改数组 nums以减小空间复杂度

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(nums[i], res);
        }
        return res;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

2. 剑指 Offer 47. 礼物的最大价值

思路：

定义状态数组 $dp[i][j]$，表示从原点到位置 (i，j) 处可最多拿到价值多少的礼物

因为只能向右或向下移动，故数组上边界状态转移方程： $dp[0][j]=dp[0][j-1]+grid[0][j]$

同理，左边界状态转移方程：$dp[i][0]=dp[i-1][0]+grid[i][0]$

其他位置的状态转移方程：$dp[i][j]=grid[i][j]+max(dp[i][j-1]，dp[i-1][j])$

同样如上题，我们可以通过原地修改来减小空间复杂度

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) 
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/solution/mian-shi-ti-47-li-wu-de-zui-da-jie-zhi-dong-tai-gu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第 11 天双指针

1. 剑指 Offer 18. 删除链表的节点

思路：

删除链表某节点既是找到删除节点的前置结点

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) return head.next;
        ListNode pre = head, cur = head;
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        return head;
    }
}

2.剑指 Offer 22. 链表中倒数第k个节点

思路（快慢指针）：

设置两个指针，让慢指针原地不动，快指针先走 k 个，此时快慢指针相距 k

让快慢指针同时开始移动，每次都移动一个单位，当快指针走完时，相距 k 个单位的慢指针刚好指向倒数第 k 个

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode tmp = head, cur = head;
        for (int i = 0; i < k; i++) {
            tmp = tmp.next;
        }
        while (tmp != null) {
            tmp = tmp.next;
            cur = cur.next;
        }
        return cur;
    }
}

第 12 天双指针

1. 剑指 Offer 25. 合并两个排序的链表

思路一（循环）：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 设置头节点
        ListNode head = new ListNode(0), cur = head;
        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 head.next;
    }
}

思路二（递归）：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        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;
        }
    }
}

2. 剑指 Offer 52. 两个链表的第一个公共节点

思路一（哈希集合）：

设置一个集合，遍历链表1，将链表1 中的元素加入集合中，然后遍历链表 2 ，判断结点是否在集合中，若在，既为公共结点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/liang-ge-lian-biao-de-di-yi-ge-gong-gong-pzbs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(m + n)

空间复杂度：O(n)

思路二（双指针）：

设公共部分长度为 $len$，则有 $skipA + len + skipB = skipB + len + skipA$

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode n1 = headA;
        ListNode n2 = headB;
        
        while(n1 != n2){
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n1;
    }
}

程序员的浪漫：“两个结点不断的去对方的轨迹中寻找对方的身影，只要二人有交集，就终会相遇 💖”

时间复杂度：O(m + n)

空间复杂度：O(1)

第 13 天双指针

1. 剑指 Offer 21. 调整数组顺序使奇数位于

思路：

设置头尾双指针，头指针++直到遇到偶数，尾指针–直到遇到奇数，交换头尾指针指向的值，重复上述操作

思路有点像快排

class Solution {
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r && l < nums.length && r > 0) {
            while (l < r && nums[l] % 2 != 0) l++;
            while (l < r && nums[r] % 2 == 0) r--;
            if (l < r) swap(nums, l, r);
        }
        return nums;
    }

    int[] swap(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
        return nums;
    }
}

2. 剑指 Offer 57. 和为s的两个数字

思路一（二分法）：

顺序遍历数组，若第 $i$ 个元素为 a，则使用二分查找查找 $target-a$ 即可

时间复杂度：$O(nlogn)$

空间复杂度：$O(1)$

思路二（双指针）👍：

所给数组是递增数组，可以采用头尾指针 $l、r$

若 $nums[l]+nums[r]<target$，则 $l++$
若 $nums[l]+nums[r]>target$，则 $r–$
若 $nums[l]+nums[r]=target$，则说明找到

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l < r) {
            int val = nums[l] + nums[r];
            if (val == target) return new int[]{nums[l], nums[r]};
            else if (val < target) l++;
            else r--;
        }
        return new int[]{};
    }
}

3. 剑指 Offer 58 - I. 翻转单词顺序

思路：

设置双指针 $i、j$ 记录单词边界，删除字符串两端空格，逆序遍历字符串

每确定一个单词的边界，则将其添加到单词列表中

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(); // 转化为字符串并返回
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/mian-shi-ti-58-i-fan-zhuan-dan-ci-shun-xu-shuang-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第 14 天搜索与回溯算法

1. 剑指 Offer 12. 矩阵中的路径🚩

思路：

dfs + 回溯；
使用二维布尔数组记录之前的位置是否已经被访问过，如果已经被访问过的话，则在 dfs 的过程中，直接 return false 即可。也就是说，此路已经不通了；
如果当前遍历到的字符不等于 board[i][j] 位置上的字符，那么说明此路也是不通的，因此返回 false；
至于递归结束的条件：如果指针 k 能够来到 word 的最后一个字符，那么说明能够在矩阵 board 中找到一条路径，此时返回 true；
在遍历到当前 board[i][j] 的时候，首先应将该位置的 visited[i][j] 设置为 true，表明访问过；
然后，递归地去 board[i][j] 的上下左右四个方向去找，剩下的路径；
在 dfs 的过程当中，如果某条路已经不通了，那么那么需要回溯，也就是将 visited[i][j] 位置的布尔值重新赋值为 fasle；
最后，返回 ans 即可。

参考：CarolL3

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0) 
            return false;
        char[] words = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, visited, i, j, 0))
                    return true;
            }
        }
        return false;
    }

    boolean dfs(char[][] board, char[] words, boolean[][] visited, int i, int j, int k) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
                || words[k] != board[i][j] || visited[i][j])
            return false;
        if (k == words.length - 1)
            return true;
        visited[i][j] = true;
        boolean ans = false;
        ans = dfs(board, words, visited, i + 1, j, k + 1)
            || dfs(board, words, visited, i - 1, j, k + 1)
            || dfs(board, words, visited, i, j + 1, k + 1)
            || dfs(board, words, visited, i, j - 1, k + 1);
        visited[i][j] = false;
        return ans;
    }
}

2. 剑指 Offer 13. 机器人的运动范围

思路：

同上题

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }

    private int dfs(int i, int j, int m, int n, int k, boolean visited[][]) {
        if (i < 0 || i >= m || j < 0 || j >= n || (i/10 + i%10 + j/10 + j%10) > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited) + 
               dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + 1;
    }
}

第 15 天搜索与回溯算法

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

思路：

典型的二叉树方案搜索问题，使用回溯法解决（先序遍历 + 路径记录）

class Solution {
    
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

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

    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if (root.left == null && root.right == null && tar == 0) 
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }

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

思路：

将二叉搜索树排成有序序列 ==> 中序遍历

遍历时，判断当前结点是否是首个结点，如果是首个结点还要做特殊处理（左子节点是头节点而不是上一个结点）

遍历结束，连接链表头尾形成双向循环链表

class Solution {
    Node head, pre;
    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); 
    }
}

3. 剑指 Offer 54. 二叉搜索树的第k大节点

思路：

由于是二叉搜索树，故可以采用中序遍历，将遍历结果依次保存到一个列表中，从而得到一个升序列表，升序列表中倒数第 k 个元素就是第 k 大的元素

class Solution {
    public int kthLargest(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        inOrder(root, list);
        return list.get(list.size() - k);
    }

    void inOrder(TreeNode root, ArrayList<Integer> list) {
        if (root == null)
            return;
        if (root.left != null) 
            inOrder(root.left, list);
        list.add(root.val);
        if (root.right != null) 
            inOrder(root.right, list);
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

进一步优化：

其实遍历到第 k 大元素的时候，就可以停止遍历了

遍历过程采用 右-根-左 的中序遍历，那么遍历过程得到的其实是一个降序序列

设置一个变量 count 记录当前元素是第几大，当 count == k 时，返回结果

// 全局变量    
private int ans = 0, count = 0;
	
void inOrder(TreeNode root, int k) {
    if (root == null)
        return;
    if (root.left != null) 
        inOrder(root.left, list);
    if (++count == k) {
        ans = root.val;
        return;
    }
    if (root.right != null) 
        inOrder(root.right, list);
}

第 16 天排序

1. 剑指 Offer 45. 把数组排成最小的数

思路：

需要将字符按特定规则排序，排序后进行组合，就能得到最小的数

排序的规则：

若拼接字符串 $ x + y > y + x$ ，则 $ x$ “大于” $y$
反之，若 $x + y < y + x$，则 $x$ “小于” $y$

class Solution {
    public String minNumber(int[] nums) {
        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);
    }
}

2. 剑指 Offer 61. 扑克牌中的顺子

思路：

根据题意，此 5 张牌是顺子的充分条件如下：

除大小王外，所有牌无重复；

设此 5 张牌中最大的牌为 $max $，最小的牌为 $min $（大小王除外），则需满足：$max - min < 5$

因而，可将问题转化为：此 5 张牌是否满足以上两个条件？

作者：jyd
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int min = 14, max = 0;
        for (int num : nums) {
            if (num == 0) continue;
            min = Math.min(min, num);
            max = Math.max(max, num);
            if (set.contains(num)) return false;
            set.add(num);
        }
        return (max - min) < 5;
    }
}

第 17 天排序

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

思路：

将数组进行排序，排序后取数组前 k 个元素既为结果

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        // Arrays.sort(arr);
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOfRange(arr, 0, k);
    }

    void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partation(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    int partation(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && pivot <= arr[high]) high--;
            arr[low] = arr[high];
            while (low < high && pivot >= arr[low]) low++;
            arr[high] = arr[low]; 
        }
        arr[low] = pivot;
        return low;
    }
}

第 18 天搜索与回溯算法

1. 剑指 Offer 55 - I. 二叉树的深度

思路一（dfs）：

直接看代码！

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

思路二（bfs）：

设置变量 depth 记录树深，层序遍历，每遍历一层，depth++，就类似于按层打印二叉树的思想

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            depth++;
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return depth;
    }
}

2. 剑指 Offer 55 - II. 平衡二叉树

思路一：

分别求出每个结点作为树的根节点时树的深度，再对每个结点递归的进行判断是否为平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) 
            return true;
        if (Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1)
            return isBalanced(root.left) && isBalanced(root.right);
        return false;
    }
    
    int getDepth(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(getDepth(root.left), getDepth(root.right));
    }
}

该方法虽然容易想到，但是在计算深度时会产生大量重复计算，时间效率较低

时间复杂度：$O(nlogn)$

空间复杂度：$O(n)$

思路二：

对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    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;
    }
}

参考：面试题55 - II. 平衡二叉树（从底至顶、从顶至底，清晰图解）

时间复杂度：$O(n)$

空间复杂度：$O(n)$

第 19 天搜索与回溯算法

1. 剑指 Offer 64. 求1+2+…+n

思路一（调包）：

class Solution {
    public int sumNums(int n) {
        return IntStream.range(1, n + 1).sum();
    }
}

思路二（巧用 &&）：

在式子 A && B 中，如果 A 为 false，则整个表达式已经是 false 了，就不用执行 B 的内容了

由此，我们可以用 B 来递归计算 n 项和，A 作为终止条件

class Solution {
    public int sumNums(int n) {
        boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}

2. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

思路：

题中所给树是一颗二叉搜索树，不难推出，两个结点 p、q 的最近公共祖先的值必定夹在 p、q 的值之间

递归搜索即可，递归终止条件：$root.val > p.val\ and\ root.val < q.val$

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) 
            return lowestCommonAncestor(root.left, p, q);
        else if (root.val < p.val && root.val < q.val) 
            return lowestCommonAncestor(root.right, p, q);
        return root;  
    }
}

3. 剑指 Offer 68 - II. 二叉树的最近公共祖先

思路：

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

作者：jyd
链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 若当前节点为空或当前结点为 p、q 中的一个，则返回当前结点
        if(root == null || root == p || root == q) return root;
        // 递归搜索当前结点的左右子树，看 p、q 结点是否在当前结点的左右子树中
        // 最先遇到哪个就返回哪个
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 递归得到的左(右)子节点为空，说明当前节点的左(右)子节点的子节点中不含 p、q
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}

第 1 天 栈与队列

1. 剑指 Offer 09. 用两个栈实现队列

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

第 2 天 链表

1. 剑指 Offer 06. 从尾到头打印链表

2. 剑指 Offer 24. 反转链表

3. 剑指 Offer 35. 复杂链表的复制

第 3 天 字符串

1. 剑指 Offer 05. 替换空格

2. 剑指 Offer 58 - II. 左旋转字符串

第 4 天 查找算法（简单）

1. 剑指 Offer 03. 数组中重复的数字

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

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

第 5 天 查找算法（中等）

1. 剑指 Offer 04. 二维数组中的查找

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

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

第 6 天 搜索与回溯算法（树的层序遍历）

1. 剑指 Offer 32 - I. 从上到下打印二叉树

2. 剑指 Offer 32 - II. 从上到下打印二叉树 II

3. 剑指 Offer 32 - II. 从上到下打印二叉树 II

第 7 天 搜索与回溯（树的递归）

1. 剑指 Offer 26. 树的子结构

2. 剑指 Offer 27. 二叉树的镜像

3. 剑指 Offer 28. 对称的二叉树

第 8 天 动态规划(简单)

1. 剑指 Offer 10- I. 斐波那契数列

2. 剑指 Offer 10- II. 青蛙跳台阶问题🚩

3. 剑指 Offer 63. 股票的最大利润

第 9 天 动态规划（中等）

1. 剑指 Offer 42. 连续子数组的最大和

2. 剑指 Offer 47. 礼物的最大价值

第 11 天 双指针

1. 剑指 Offer 18. 删除链表的节点

2.剑指 Offer 22. 链表中倒数第k个节点

第 12 天 双指针

1. 剑指 Offer 25. 合并两个排序的链表

2. 剑指 Offer 52. 两个链表的第一个公共节点

第 13 天 双指针

1. 剑指 Offer 21. 调整数组顺序使奇数位于

2. 剑指 Offer 57. 和为s的两个数字

3. 剑指 Offer 58 - I. 翻转单词顺序

第 14 天 搜索与回溯算法

1. 剑指 Offer 12. 矩阵中的路径🚩

2. 剑指 Offer 13. 机器人的运动范围

第 15 天 搜索与回溯算法

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

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

3. 剑指 Offer 54. 二叉搜索树的第k大节点

第 16 天 排序

1. 剑指 Offer 45. 把数组排成最小的数

2. 剑指 Offer 61. 扑克牌中的顺子

第 17 天 排序

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

第 18 天 搜索与回溯算法

1. 剑指 Offer 55 - I. 二叉树的深度

2. 剑指 Offer 55 - II. 平衡二叉树

第 19 天 搜索与回溯算法

1. 剑指 Offer 64. 求1+2+…+n

2. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

3. 剑指 Offer 68 - II. 二叉树的最近公共祖先

第 1 天栈与队列

第 2 天链表

第 3 天字符串

第 4 天查找算法（简单）

第 5 天查找算法（中等）

第 6 天搜索与回溯算法（树的层序遍历）

第 7 天搜索与回溯（树的递归）

第 8 天动态规划(简单)

第 9 天动态规划（中等）

第 11 天双指针

第 12 天双指针

第 13 天双指针

第 14 天搜索与回溯算法

第 15 天搜索与回溯算法

第 16 天排序

第 17 天排序

第 18 天搜索与回溯算法

第 19 天搜索与回溯算法