算法刷题记录——LeetCode篇(2) [第101~200题](持续更新)

(优先整理热门100及面试150，不定期持续更新，欢迎关注)

---

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false 

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

进阶：
你可以运用递归和迭代两种方法解决这个问题吗？

方法一：递归法

• 定义辅助函数 isMirror，比较两棵树是否镜像对称。
• 镜像条件：根节点值相同，左子树与右子树镜像对称，右子树与左子树镜像对称。

代码实现(Java)：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }
  
    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return (left.val == right.val) 
            && isMirror(left.left, right.right) 
            && isMirror(left.right, right.left);
    }
}

方法二：迭代法

• 使用队列成对存储需要比较的节点（左子树左节点与右子树右节点，左子树右节点与右子树左节点）。
• 成对取出节点比较值，若结构或值不匹配则直接返回 false。

代码实现(Java)：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

复杂度分析

1. 递归法：

   • 时间复杂度：O(n)，每个节点访问一次。
   • 空间复杂度：O(h)，递归栈深度与树高度相关。

2. 迭代法：

   • 时间复杂度：O(n)，每个节点访问一次。
   • 空间复杂度：O(n)，队列最多存储一层节点。

---

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

方法一：迭代法（队列实现）

• 使用队列按层存储节点，每次处理一层所有节点。
• 将当前层节点的子节点按顺序入队，保证层级顺序。

代码实现(Java)：

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

方法二：递归法（DFS）

• 通过递归深度优先遍历，记录当前节点层级。
• 根据层级动态扩展结果列表，保证节点值按层收集。

代码实现(Java)：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        traverse(root, 0, result);
        return result;
    }
  
    private void traverse(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) return;
      
        if (result.size() == level) {
            result.add(new ArrayList<>());
        }
        result.get(level).add(node.val);
      
        traverse(node.left, level + 1, result);
        traverse(node.right, level + 1, result);
    }
}

复杂度分析

1. 迭代法：

   • 时间复杂度：O(n)，每个节点进出队列一次。
   • 空间复杂度：O(n)，队列存储最多 n/2 个节点（完全二叉树）。

2. 递归法：

   • 时间复杂度：O(n)，每个节点访问一次。
   • 空间复杂度：O(h)，递归栈深度与树高相关，最坏情况 O(n)。

---

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, 10^4] 区间内
• -100 <= Node.val <= 100

方法一：递归法

自顶向下分解问题，当前树的最大深度等于左右子树最大深度的较大值加一。

代码实现(Java)：

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

方法二：广度优先搜索（BFS）

逐层遍历树，每遍历完一层深度加一，最终深度即为最大深度。

代码实现(Java)：

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

方法三：深度优先搜索（DFS）迭代法

显式使用栈保存节点和当前深度，通过前序遍历更新最大深度。

代码实现(Java)：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> stack = new LinkedList<>();
        Deque<Integer> depthStack = new LinkedList<>();
        stack.push(root);
        depthStack.push(1);
        int max = 0;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int currentDepth = depthStack.pop();
            max = Math.max(max, currentDepth);
            if (node.right != null) {
                stack.push(node.right);
                depthStack.push(currentDepth + 1);
            }
            if (node.left != null) {
                stack.push(node.left);
                depthStack.push(currentDepth + 1);
            }
        }
        return max;
    }
}

---

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均无重复元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

方法：递归分治+哈希优化

1. 核心思想：

   • 前序遍历首元素为根节点；
   • 中序遍历中根节点左侧为左子树，右侧为右子树；
   • 通过递归分治思想逐层构建子树。

2. 关键步骤：

   • 哈希表加速：预存中序遍历值到索引的映射，实现O(1)时间定位根节点；
   • 子树分割：
     • 左子树节点数 = 根节点中序位置 - 中序起始位置；
     • 前序左子树范围：preStart+1 至 preStart+leftSize；
     • 前序右子树范围：preStart+leftSize+1 至 preEnd。

3. 边界处理：

   • 空数组直接返回null；
   • 单节点直接返回根节点；
   • 完全左/右斜树通过leftSize正确分割区间。

代码实现(Java)：

class Solution {
    private Map<Integer, Integer> indexMap;
    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return buildSubtree(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildSubtree(int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd) return null;
      
        // 前序首元素为当前根节点
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
      
        // 获取中序中根节点位置
        int rootInIndex = indexMap.get(rootVal);
        int leftSize = rootInIndex - inStart;  // 左子树节点数
      
        // 递归构建左右子树
        root.left = buildSubtree(preStart + 1, preStart + leftSize, inStart, rootInIndex - 1);
        root.right = buildSubtree(preStart + leftSize + 1, preEnd, rootInIndex + 1, inEnd);
      
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n)，每个节点处理一次；
• 空间复杂度：O(n)，哈希表存储n个元素，递归栈深度平均O(logn)。

---

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]

解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 按严格递增顺序排列

方法一：递归法（中序遍历）

1. 选择中间节点：每次取有序数组的中间元素作为根节点。当数组长度为偶数时，可以选择中间偏左或偏右的节点；
2. 递归构建子树：将中间元素左侧的子数组构建为左子树，右侧的子数组构建为右子树；
3. 树平衡性保证：由于每次均匀分割数组，左右子树节点数差不超过1，自然形成平衡二叉搜索树。

代码实现(Java)：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }
  
    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;
        // 计算中间索引（防止整数溢出）
        int mid = left + (right - left) / 2;
        // 选择中间偏右的节点：mid = left + (right - left + 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：O(logn)，递归栈深度与树高相关。此方法保证平衡，故树高保持 logn。

---

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶：
你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

方法一：迭代先序遍历（显式栈）

利用栈模拟先序遍历，维护前驱节点prev，实时修改指针建立链表。

• 核心思想：利用栈按「根→右→左」顺序压入节点，确保弹出顺序为「根→左→右」。
• 指针调整：维护前驱节点prev，每次将prev的right指向当前节点，并清空left指针。
• 空间优化：栈的深度为树高，平均空间复杂度为O(log n)。

代码实现(Java)：

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode prev = null;
      
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            // 将前驱节点的right指向当前节点，left置空
            if (prev != null) {
                prev.right = current;
                prev.left = null;
            }
            prev = current;
            // 先压入右子节点，再压入左子节点（栈的LIFO特性）
            if (current.right != null) stack.push(current.right);
            if (current.left != null) stack.push(current.left);
        }
    }
}

方法二：递归后序遍历（连接左右子树）

递归处理左右子树，将左子树连接到右子树之前，并更新末尾节点。

• 核心思想：将左子树末尾连接到右子树头部，再让根节点指向左子树。
• 末尾处理：返回展开后的最后一个节点，避免每次遍历链表末尾，时间复杂度优化至O(n)。
• 逻辑简化：通过后序遍历自底向上处理，确保左子树完全展开后再处理根节点。

代码实现(Java)：

public class Solution {
    public void flatten(TreeNode root) {
        flattenHelper(root);
    }
  
    private TreeNode flattenHelper(TreeNode node) {
        if (node == null) return null;
        // 递归处理左右子树，获取展开后的末尾节点
        TreeNode leftTail = flattenHelper(node.left);
        TreeNode rightTail = flattenHelper(node.right);
      
        // 将左子树插入到当前节点与右子树之间
        if (node.left != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        // 返回当前子树展开后的最后一个节点
        return (rightTail != null) ? rightTail : 
               (leftTail != null) ? leftTail : node;
    }
}

复杂度分析

• 时间复杂度：两种方法均为 O(n)，每个节点被访问一次。
• 空间复杂度：
  • 迭代法：O(h)，h为树高，最坏情况（链表结构）为O(n)。
  • 递归法：O(h)，递归栈深度为树高。

对比总结

• 迭代法：适合大规模数据或树结构较深时，避免递归栈溢出。
• 递归法：代码简洁，适合对代码可读性要求高，且无栈溢出风险的场景。

---

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6

解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42

解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3*10^4]
• -1000 <= Node.val <= 1000

方法：递归法（后序遍历）

通过后序遍历计算每个节点的最大贡献值，并更新全局最大路径和。

• 每个节点计算其左右子树的最大贡献值（若贡献为负则取0）。
• 当前节点的总路径和为 自身值 + 左贡献 + 右贡献，更新全局最大值。
• 返回当前节点能为父节点提供的单边最大贡献（即 自身值 + max(左贡献, 右贡献)）。

代码实现(Java)：

class Solution {
    private int maxSum = Integer.MIN_VALUE;
  
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
  
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
      
        // 计算左右子树的贡献值，负数则舍弃
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
      
        // 当前节点作为路径中间节点的总路径和
        int currentPathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentPathSum);
      
        // 返回当前节点能提供的最大单边贡献（给父节点使用）
        return node.val + Math.max(leftGain, rightGain);
    }
}

复杂度分析

• 时间复杂度：O(n)，所有节点仅访问一次。
• 空间复杂度：O(h)，递归栈深度（h为树的高度，最坏情况下为O(n)）。

---

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

方法：动态规划预处理 + 回溯法

通过动态规划预处理所有回文子串信息，再利用回溯法生成所有可能的分割方案，有效避免重复计算。

1. 动态规划预处理：构建二维数组 dp[i][j]，表示子串 s[i...j] 是否为回文。通过从后向前遍历，确保计算 dp[i][j] 时 dp[i+1][j-1] 已确定。
2. 回溯法生成方案：从起始位置 start 开始，枚举所有可能的结束位置 end。若 s[start...end] 是回文，则将其加入路径，并递归处理剩余子串 s[end+1...]，回溯时移除最后添加的子串。

代码实现(Java)：

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.isEmpty()) return res;
      
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        char[] arr = s.toCharArray();
      
        // 预处理回文判断矩阵
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (arr[i] == arr[j]) {
                    dp[i][j] = (j - i == 1) || dp[i + 1][j - 1];
                }
            }
        }
      
        backtrack(s, 0, new ArrayList<>(), res, dp);
        return res;
    }

    private void backtrack(String s, int start, List<String> path, 
                           List<List<String>> res, boolean[][] dp) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
      
        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, res, dp);
                path.remove(path.size() - 1);
            }
        }
    }
}

复杂度分析

时间复杂度： 预处理阶段 O(n²)，回溯阶段最坏情况 O(n·2ⁿ)；综合时间复杂度为 O(n·2ⁿ)，其中 n 为字符串长度。
空间复杂度： 预处理矩阵 O(n²)，递归栈深度 O(n)；综合空间复杂度 O(n²)。

---

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• Node.random 为 null 或指向链表中的节点

方法一：哈希表映射法

通过哈希表建立原节点与复制节点的映射关系。第一次遍历创建所有新节点，第二次遍历设置指针，通过哈希表快速定位对应的复制节点。

1. 创建节点映射：遍历原链表，创建每个节点的复制节点并存入哈希表。
2. 设置指针：再次遍历原链表，通过哈希表获取复制节点，设置其next和random指针。

代码实现(Java)：

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node curr = head;
        // 创建所有新节点
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }
        // 设置指针
        curr = head;
        while (curr != null) {
            Node clone = map.get(curr);
            clone.next = map.get(curr.next);
            clone.random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }
}

复杂度分析

• 时间复杂度：O(n)，两次线性遍历。
• 空间复杂度：O(n)，哈希表存储所有节点映射。

方法二：原地复制拆分法

不借助额外空间，通过三次遍历完成复制。第一次复制节点并插入原链表，第二次设置random指针，第三次拆分恢复原链表并构建新链表。

1. 复制插入节点：将每个复制节点插入原节点之后，形成交替链表。
2. 设置random指针：利用原节点的位置关系，设置复制节点的random。
3. 拆分链表：恢复原链表的next，同时构建复制链表。

代码实现(Java)：

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        // 插入复制节点
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }
        // 设置random指针
        curr = head;
        while (curr != null) {
            Node clone = curr.next;
            clone.random = (curr.random != null) ? curr.random.next : null;
            curr = clone.next;
        }
        // 拆分链表
        Node newHead = head.next;
        curr = head;
        while (curr != null) {
            Node clone = curr.next;
            curr.next = clone.next; // 恢复原链表
            if (clone.next != null) {
                clone.next = clone.next.next; // 构建新链表
            }
            curr = curr.next;
        }
        return newHead;
    }
}

复杂度分析

• 时间复杂度：O(n)，三次线性遍历。
• 空间复杂度：O(1)，仅使用常量额外空间。

对比总结

方法	优点	缺点	适用场景
哈希表映射法	逻辑清晰，实现简单	需要O(n)额外空间	常规场景，快速实现
原地复制拆分法	空间效率高，无需额外存储	修改原链表结构	空间敏感，允许修改原链表

---

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true

解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true

解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串互不相同

方法：动态规划

使用动态规划数组 dp[i] 表示字符串前 i 个字符能否被字典中的单词拆分。通过遍历字符串的每个位置，并检查所有可能的子串是否存在于字典中，逐步填充 dp 数组。

1. 字典预处理：将字典存入 HashSet 实现 O(1) 时间查询，同时记录字典中最长单词长度 maxLen，减少不必要的子串检查。
2. 动态规划填充：
   • 初始化：dp[0] = true 表示空字符串可拆分。
   • 遍历每个位置i：从 1 到 n（字符串长度），检查所有可能的拆分点 j。
   • 剪枝优化：start = Math.max(0, i - maxLen) 确保仅检查长度不超过 maxLen 的子串，避免全量遍历。
   • 状态转移：若 dp[j] 为 true 且子串 s.substring(j, i) 存在于字典中，则 dp[i] = true。

代码实现(Java)：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 空字符串默认可以拆分
      
        for (int i = 1; i <= n; i++) {
            // 仅检查长度不超过 maxLen 的子串
            int start = Math.max(0, i - maxLen);
            for (int j = start; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

复杂度分析

• 时间复杂度：预处理字典：O(M)，其中 M 为字典总字符数；动态规划循环：O(n * maxLen)；总时间复杂度：O(M + n * maxLen)，其中 n 是字符串长度，maxLen 是字典中最长单词长度。
• 空间复杂度：HashSet 存储字典：O(K)；dp 数组：O(n)；总空间复杂度：O(K + n)，K 为字典中不同单词的个数。

---

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false

解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个有效索引

进阶：
你能用 O(1)（常量）内存解决此问题吗？

方法一：快慢指针（Floyd判圈算法）

使用两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。如果链表中有环，快指针最终会追上慢指针；如果快指针到达链表末尾（遇到null），则说明链表无环。

1. 初始化快慢指针都指向头节点。
2. 快指针每次移动两步，慢指针每次移动一步。
3. 如果快慢指针相遇，说明有环；若快指针遍历到链表末尾，说明无环。

代码实现(Java)：

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

方法二：哈希表

遍历链表，用哈希表记录已访问过的节点。如果遇到重复节点，说明存在环；否则遍历完成无环。

1. 创建哈希表存储访问过的节点。
2. 遍历链表，检查当前节点是否已存在于哈希表中。
3. 存在则返回true，否则将节点加入哈希表。
4. 遍历结束返回false。

代码实现(Java)：

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        while (head != null) {
            if (visited.contains(head)) {
                return true;
            }
            visited.add(head);
            head = head.next;
        }
        return false;
    }
}

复杂度分析

• 快慢指针法：时间复杂度O(n)，空间复杂度O(1)。通过双指针的追赶机制高效检测环。
• 哈希表法：时间复杂度O(n)，空间复杂度O(n)。利用哈希表的唯一性记录访问过的节点，实现简单但空间占用较高。

---

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null

解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 10^4] 内
• -10^5 <= Node.val <= 10^5
• pos 的值为 -1 或者链表中的一个有效索引

方法一：快慢指针（Floyd判圈算法）

判断是否有环：快慢指针相遇说明有环；寻找环入口：相遇后，将其中一个指针重置到头节点，两指针以相同速度前进，再次相遇的节点即为环入口。

1. 快指针每次走两步，慢指针每次走一步，找到相遇点。
2. 初始化两个指针分别从头节点和相遇点出发，同步移动直至相遇。

代码实现(Java)：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        boolean hasCycle = false;
        // 判断是否存在环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) return null;
        // 寻找环入口
        ListNode ptr1 = head, ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }
}

方法二：哈希表

遍历链表并记录访问过的节点，第一个重复的节点即为环入口。

1. 使用哈希表存储已访问的节点。
2. 遍历链表，若当前节点已存在于哈希表，则返回该节点；否则继续遍历。

代码实现(Java)：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode node = head;
        while (node != null) {
            if (visited.contains(node)) {
                return node;
            }
            visited.add(node);
            node = node.next;
        }
        return null;
    }
}

复杂度分析

• 快慢指针法：时间复杂度O(n)，空间复杂度O(1)。通过数学推导找到环入口，高效且节省内存。
• 哈希表法：时间复杂度O(n)，空间复杂度O(n)。实现简单，但需要额外空间存储节点，适用于空间不敏感的场景。

---

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

LRUCache(int capacity);
// 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key);
// 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value);
// 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
// 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释:

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2*10^5 次 get 和 put

方法：哈希表结合双向链表

LRU缓存机制要求快速定位元素是否存在，并维护元素的访问顺序。利用哈希表实现O(1)时间的查找，双向链表维护访问顺序，最近访问的节点置于链表头部，尾部则为最久未使用的节点。

1. 数据结构设计：
   • 双向链表节点包含键、值、前驱和后继指针。
   • 哈希表存储键到链表节点的映射。
2. 初始化：
   • 创建虚拟头尾节点，形成空链表。
3. get操作：
   • 若键存在，将对应节点移至链表头部并返回值；否则返回-1。
4. put操作：
   • 若键存在，更新值并将节点移至头部。
   • 若不存在，创建新节点并添加到头部及哈希表中。若容量超限，删除尾部节点并更新哈希表。
5. 代码实现关键点：
   • 双向链表操作：通过虚拟头尾节点简化链表操作，确保插入和删除的指针调整正确。
   • 哈希表维护：哈希表与链表同步更新，保证快速访问和空间管理。
   • LRU策略实现：通过链表顺序维护访问时间，头部为最新，尾部为最旧，容量超限时删除尾部节点。

代码实现(Java)：

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node() {}
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, Node> cache;
    private int capacity;
    private int size;
    private Node dummyHead;
    private Node dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        cache = new HashMap<>();
        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                Node tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        }
    }

    private void addToHead(Node node) {
        node.prev = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node tail = dummyTail.prev;
        removeNode(tail);
        return tail;
    }
}

复杂度分析

• 时间复杂度：get和put操作均为O(1)。
• 空间复杂度：O(capacity)，用于存储哈希表和链表节点。

---

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5*10^4] 内
• -10^5 <= Node.val <= 10^5

方法一：归并排序（递归）

采用归并排序算法，通过分治策略将链表不断分割成子链表，直到每个子链表只有一个节点，然后逐步合并有序链表。关键点在于正确分割链表和高效合并两个有序链表。

1. 递归终止条件：链表为空或只有一个节点时直接返回。
2. 寻找中间节点：使用快慢指针法找到链表中点，将链表分为左右两部分。
3. 递归排序：分别对左右子链表进行递归排序。
4. 合并有序链表：将两个已排序的子链表合并成一个有序链表。

代码实现(Java)：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 使用快慢指针找到中间节点
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null; // 将链表断开为两部分
      
        // 递归排序左右两部分
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
      
        // 合并有序链表
        return merge(left, right);
    }
  
    // 合并两个有序链表
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(n log n)，归并排序的典型时间复杂度。
• 空间复杂度：O(log n)，递归调用栈的深度。

方法二：归并排序（迭代）

通过迭代方式实现归并排序，避免递归带来的栈空间开销。每次将链表分成固定大小的块，逐步合并相邻块，直到整个链表有序。

1. 计算链表长度：确定需要合并的次数。
2. 分块合并：每次将链表分割成大小为step的块，合并相邻块。
3. 调整步长：每次合并后步长翻倍，直到步长超过链表长度。

代码实现(Java)：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
      
        // 计算链表长度
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
      
        ListNode dummy = new ListNode(0);
        dummy.next = head;
      
        // 迭代合并，步长从1开始倍增
        for (int step = 1; step < len; step *= 2) {
            ListNode tail = dummy;
            ListNode left = dummy.next;
            while (left != null) {
                ListNode right = split(left, step);
                ListNode next = split(right, step);
                tail = merge(left, right, tail);
                left = next;
            }
        }
        return dummy.next;
    }
  
    // 分割链表，返回分割后的右半部分头节点
    private ListNode split(ListNode head, int step) {
        if (head == null) return null;
        for (int i = 1; head.next != null && i < step; i++) {
            head = head.next;
        }
        ListNode right = head.next;
        head.next = null;
        return right;
    }
  
    // 合并两个链表，并连接到tail后面，返回合并后的新tail
    private ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
        ListNode curr = tail;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        while (curr.next != null) curr = curr.next;
        return curr;
    }
}

复杂度分析

• 时间复杂度：O(n log n)，与递归方法相同。
• 空间复杂度：O(1)，仅使用常量额外空间。

对比总结

方法	优点	缺点	适用场景
递归归并	代码简洁，逻辑清晰	栈空间O(log n)	常规场景，链表较短
迭代归并	无栈溢出风险，空间更优	实现较复杂，指针操作多	链表较长或空间敏感场景

---

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

• 1 <= nums.length <= 2*10^4
• -10 <= nums[i] <= 10
• nums 的任何子数组的乘积都 保证 是一个 32-位 整数

方法：动态规划

使用动态规划维护两个变量 currentMax 和 currentMin，分别表示以当前元素结尾的子数组的最大和最小乘积。通过遍历数组，每一步利用前一步的状态更新当前值，并记录全局最大值。

1. 初始化

   • currentMax 和 currentMin 初始化为第一个元素的值。
   • globalMax 记录全局最大乘积，初始值也为第一个元素。

2. 遍历数组

   • 对于每个元素 num，计算三种可能的乘积：
     • 当前元素本身（可能作为新子数组的起点）。
     • 当前元素乘以前一个最大乘积 currentMax * num。
     • 当前元素乘以前一个最小乘积 currentMin * num（负数可能反转结果）。
   • 更新 currentMax 和 currentMin 为三种情况中的最大值和最小值。

3. 更新全局最大值

   • 每次迭代后比较 globalMax 和当前 currentMax，确保记录全局最优解。

代码实现(Java)：

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
      
        int currentMax = nums[0];
        int currentMin = nums[0];
        int globalMax = nums[0];
      
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            // 保存临时值，防止覆盖导致的计算错误
            int tempMax = Math.max(num, Math.max(currentMax * num, currentMin * num));
            int tempMin = Math.min(num, Math.min(currentMax * num, currentMin * num));
          
            currentMax = tempMax;
            currentMin = tempMin;
          
            globalMax = Math.max(globalMax, currentMax);
        }
        return globalMax;
    }
}

复杂度分析

• 时间复杂度：O(n)，只需一次遍历数组。
• 空间复杂度：O(1)，仅用常数空间存储状态变量。

---

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1

解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0

解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11

解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

方法：二分查找法

通过比较中间元素与右边界元素，判断最小值所在区间，逐步缩小搜索范围。

1. 旋转特性分析：旋转后的数组由两个递增子数组组成，最小值位于第二个子数组的首位；
2. 关键比较逻辑：
   • 当nums[mid] > nums[right]时，说明右半部分存在更小元素，收缩左边界；
   • 当nums[mid] <= nums[right]时，说明右半部分有序，最小值可能在左侧或当前mid位置；
3. 终止条件：当左右指针相遇时，指向的位置即为最小值所在。

代码实现(Java)：

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                // 最小值在右半部分
                left = mid + 1;
            } else {
                // 最小值在左半部分（含mid）
                right = mid;
            }
        }
        return nums[left];
    }
}

复杂度分析

• 时间复杂度O(log n)，每次循环将搜索范围减半。
• 空间复杂度O(1)，仅需常数级额外空间。

---

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

MinStack();
// 初始化堆栈对象。
void push(int val);
// 将元素val推入堆栈。
void pop();
// 删除堆栈顶部的元素。
int top();
// 获取堆栈顶部的元素。
int getMin();
// 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3*10^4 次

方法：双栈同步维护法

使用主栈存储元素，辅助栈同步存储对应状态下的最小值，实现所有操作O(1)时间复杂度。

1. 双栈同步机制：

   • 主栈dataStack正常执行栈操作；
   • 辅助栈minStack存储对应主栈状态时的最小值；
   • 每次push操作同步更新两个栈，保证栈高度一致。

2. 最小值维护策略：

   • 当新元素入栈时，minStack压入min(新元素, 当前minStack栈顶)；
   • 当元素出栈时，双栈同步弹出保持状态一致。

代码实现(Java)：

class MinStack {
    private Deque<Integer> dataStack;   // 主栈存储元素
    private Deque<Integer> minStack;    // 辅助栈存储最小值

    public MinStack() {
        dataStack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        dataStack.push(val);
        // 维护最小值：如果辅助栈为空直接压入，否则取当前值与栈顶较小值
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

复杂度分析

• 时间复杂度：push、pop、top、getMin操作均为O(1)。
• 空间复杂度：O(n)，每个元素对应存储一个最小值记录。

---

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5*10^4
• -10^9 <= nums[i] <= 10^9

进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

---

188. 买卖股票的最佳时机 IV

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2

解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7

解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

方法一：动态规划（通用解法）

使用三维状态压缩的动态规划，将状态定义为 dp[j][0] 和 dp[j][1]，分别表示完成 j 次交易后不持有股票和持有股票的最大利润。通过逆序处理交易次数避免状态覆盖问题，并增加无效状态判断。

代码实现(Java)：

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k == 0 || n < 2) return 0;
      
        // 处理 k 很大的情况，退化为贪心算法
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }
      
        // 动态规划初始化
        int[][] prevDp = new int[k + 1][2];
        for (int j = 0; j <= k; j++) {
            Arrays.fill(prevDp[j], Integer.MIN_VALUE);
        }
        prevDp[0][0] = 0;          // 0次交易，不持有股票
        prevDp[0][1] = -prices[0]; // 0次交易，持有股票
      
        for (int i = 1; i < n; i++) {
            int[][] currDp = new int[k + 1][2];
            for (int j = 0; j <= k; j++) {
                currDp[j][0] = prevDp[j][0];
                currDp[j][1] = prevDp[j][1];
            }
          
            int price = prices[i];
            // 逆序处理交易次数，避免状态覆盖
            for (int j = k; j >= 1; j--) {
                // 不持有股票：卖出操作
                if (prevDp[j][1] != Integer.MIN_VALUE) {
                    currDp[j][0] = Math.max(currDp[j][0], prevDp[j][1] + price);
                }
                // 持有股票：买入操作（需要前一次交易完成）
                if (prevDp[j - 1][0] != Integer.MIN_VALUE) {
                    currDp[j][1] = Math.max(currDp[j][1], prevDp[j - 1][0] - price);
                }
            }
            // 处理 j=0 的持有状态（允许第一次买入）
            currDp[0][1] = Math.max(prevDp[0][1], -price);
            prevDp = currDp;
        }
      
        // 寻找最大利润（所有交易次数中的最大不持有状态）
        int maxProfit = 0;
        for (int j = 0; j <= k; j++) {
            maxProfit = Math.max(maxProfit, prevDp[j][0]);
        }
        return maxProfit;
    }
}

复杂度分析

• 时间复杂度：O(nk)，每个价格处理 k 次交易状态。
• 空间复杂度：O(k)，使用两个数组交替保存状态。

方法二：状态压缩优化

进一步压缩动态规划空间，使用一维数组代替二维数组。通过逆序遍历交易次数减少空间使用。

代码实现(Java)：

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k == 0 || n < 2) return 0;
      
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }
      
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
      
        for (int price : prices) {
            for (int j = k; j >= 1; j--) {
                buy[j] = Math.max(buy[j], sell[j - 1] - price);
                sell[j] = Math.max(sell[j], buy[j] + price);
            }
        }
        return sell[k];
    }
}

复杂度分析

• 时间复杂度：O(nk)，每个价格处理 k 次交易。
• 空间复杂度：O(k)，仅用两个一维数组。

---

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]

解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

方法一：使用额外数组

1. 计算有效k：通过取模运算将k限制在数组长度范围内。
2. 创建新数组：遍历原数组，将每个元素按轮转后的位置放入新数组。
3. 复制回原数组：将新数组内容覆盖到原数组，完成原地修改。

代码实现(Java)：

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return;
        k = k % n;
        if (k == 0) return;
        int[] newArr = new int[n];
        for (int j = 0; j < n; j++) {
            int originalIndex = (j - k + n) % n;
            newArr[j] = nums[originalIndex];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历数组两次（生成新数组和覆盖原数组）。
• 空间复杂度：O(n)，需要额外数组空间。

方法二：三次反转法

1. 反转整个数组：将数组元素顺序完全颠倒。
2. 反转前k部分：恢复前k个元素的原始顺序。
3. 反转剩余部分：恢复剩余元素的原始顺序，最终得到轮转结果。

代码实现(Java)：

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return;
        k = k % n;
        if (k == 0) return;
        reverse(nums, 0, n - 1);  // 反转整个数组
        reverse(nums, 0, k - 1);  // 反转前k个元素
        reverse(nums, k, n - 1);   // 反转剩余元素
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，三次反转操作各遍历一次数组。
• 空间复杂度：O(1)，原地操作，无需额外空间。

方法三：环状替换

1. 环状替换：将数组视为环形，每个元素直接移动到最终位置。
2. 处理多个环：通过计数确保所有元素都被处理，避免遗漏或重复。

代码实现(Java)：

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return;
        k = k % n;
        if (k == 0) return;
      
        int count = 0;
        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (current != start);
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，每个元素被移动一次。
• 空间复杂度：O(1)，仅用常数变量。

---

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12

解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

方法一：动态规划（空间优化）

使用动态规划，由于每个状态只依赖于前两个状态的值，可以用两个变量保存前两个状态，优化空间复杂度到 O(1)。

1. 处理边界情况（数组长度为0或1）。
2. 初始化前两个状态。
3. 遍历数组，逐个计算当前最大值并更新状态。

代码实现(Java)：

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int prevPrev = nums[0];
        int prev = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int current = Math.max(prev, prevPrev + nums[i]);
            prevPrev = prev;
            prev = current;
        }
        return prev;
    }
}

方法二：动态规划（数组存储）

思路：
定义一个数组 dp，其中 dp[i] 表示偷到第 i 个房屋时的最大金额。状态转移方程为：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

步骤：

1. 处理边界情况。
2. 初始化 dp 数组的前两个元素。
3. 遍历数组，填充 dp 数组。

代码实现(Java)：

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        if (n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

方法三：记忆化递归

思路：
自顶向下递归，使用记忆化存储已计算的结果，避免重复计算。递归函数返回从当前位置开始能偷到的最大金额。

步骤：

1. 初始化记忆数组。
2. 递归计算每个位置的最大值，保存结果。

代码实现(Java)：

public class Solution {
    public int rob(int[] nums) {
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return robHelper(nums, 0, memo);
    }

    private int robHelper(int[] nums, int start, int[] memo) {
        if (start >= nums.length) return 0;
        if (memo[start] != -1) return memo[start];
        int res = Math.max(robHelper(nums, start + 1, memo), nums[start] + robHelper(nums, start + 2, memo));
        memo[start] = res;
        return res;
    }
}

复杂度分析

• 动态规划（空间优化）： 时间复杂度 O(n)，空间复杂度 O(1)。通过变量滚动更新，节省空间。
• 动态规划（数组存储）： 时间复杂度 O(n)，空间复杂度 O(n)。直观记录每个位置的最高金额。
• 记忆化递归： 时间复杂度 O(n)，空间复杂度 O(n)。递归树深度为 n，记忆化避免重复计算。

---

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

示例 2：

输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]

示例 3：

输入：root = [1,null,3]
输出：[1,3]

示例 4：

输入：root = []
输出：[]

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

方法一：BFS层次遍历法

• 核心思想：进行标准层次遍历，每层遍历结束后，最后一个出队的节点即为该层最右可见节点。
• 实现要点：使用队列进行广度优先遍历，维护当前层节点数，收集每层末尾节点。

代码实现(Java)：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
      
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                // 每层的最后一个节点加入结果集
                if (i == levelSize - 1) result.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

方法二：DFS右优先递归法

• 核心思想：按照「根→右→左」的顺序遍历，每个深度首次访问的节点即为该层最右节点。
• 实现要点：递归时优先处理右子树，利用结果列表长度与深度的关系判断是否首次访问该层。

代码实现(Java)：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }
  
    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) return;
        // 当前深度首次访问的节点即为右视图节点
        if (depth == result.size()) result.add(node.val);
        dfs(node.right, depth + 1, result); // 先右后左确保右优先
        dfs(node.left, depth + 1, result);
    }
}

复杂度分析

1. BFS层次遍历法：

   • 时间复杂度：O(n) ，每个节点入队出队一次；
   • 空间复杂度：O(n) ，队列存储最多n节点。

2. DFS右优先递归法：

   • 时间复杂度：O(n) ，每个节点访问一次；
   • 空间复杂度：O(h) ，递归栈深度为树高h。

对比总结

• 遍历顺序：BFS按层扫描天然适合收集层信息，DFS通过调整访问顺序模拟右视图。
• 空间效率：BFS空间复杂度为最宽层的节点数，DFS为树的高度，对非平衡树更高效。

---

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

方法一：深度优先搜索（DFS）

• 核心思想：从起点出发，尽可能深地探索相邻节点，遇到边界或水域时回溯。
• 实现方式：递归遍历上下左右四个方向，将访问过的陆地标记为水域（'0'）。

代码实现(Java)：

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
  
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '0'; // 标记为已访问
        dfs(grid, i - 1, j); // 上
        dfs(grid, i + 1, j); // 下
        dfs(grid, i, j - 1); // 左
        dfs(grid, i, j + 1); // 右
    }
}

方法二：广度优先搜索（BFS）

• 核心思想：从起点出发，逐层扩展探索相邻节点。
• 实现方式：使用队列存储待处理节点，每次处理一层节点，确保按层序标记所有相连陆地。

代码实现(Java)：

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
  
    private void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        grid[i][j] = '0'; // 标记起点为已访问
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 方向数组
      
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] dir : dirs) {
                int x = curr[0] + dir[0];
                int y = curr[1] + dir[1];
                // 检查边界和是否未访问
                if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1') {
                    grid[x][y] = '0'; // 标记为已访问
                    queue.offer(new int[]{x, y});
                }
            }
        }
    }
}

复杂度分析

1. DFS（深度优先搜索）：

   • 时间复杂度：O(m×n)，每个节点仅访问一次。
   • 空间复杂度：最坏情况下为 O(m×n)（递归栈深度）。

2. BFS（广度优先搜索）：

   • 时间复杂度：O(m×n)，每个节点处理一次。
   • 空间复杂度：O(min(m, n))，队列最坏情况下存储对角线节点。

对比总结

方法	优点	缺点	适用场景
DFS	代码简洁，实现直观	可能栈溢出（深递归时）	小规模网格或树形结构
BFS	无栈溢出风险	需要额外队列空间	大规模网格或要求稳定性

---

(持续更新，未完待续)