《LeetCode 热题 100》整整 100 题量大管饱题解套餐下

技术文档

由于网站博文篇幅长度有限制，《LeetCode 热题 100》整整 100 题量大管饱题解套餐一篇博文放不下拆分成上中下三篇。

《LeetCode 热题 100》整整 100 题量大管饱题解套餐上篇链接
《LeetCode 热题 100》整整 100 题量大管饱题解套餐中篇链接
《LeetCode 热题 100》整整 100 题量大管饱题解套餐下篇链接

Q67、寻找旋转排序数组中的最小值

1、题目描述

已知一个长度为 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 次旋转

2、解题思路

二分查找法

基本情况处理：处理单元素数组的情况
二分查找 ：
- 比较中间元素与右边界元素
- 如果中间元素大于右边界元素，最小值在右半区
- 否则最小值在左半区或当前中间位置
指针调整：根据比较结果调整左右指针

3、代码实现

C++

class Solution {public: int findMin(vector& nums) { int n = nums.size(); if (n == 1) { return nums[0]; // 单元素数组直接返回 } int left = 0, right = n - 1; while (left  nums[right]) { // 最小值在右半区见 left = mid + 1; } else { // 最小值在左半区见或 mid 位置 right = mid; } } return nums[left]; // 循环结束时 left == right, 指向最小值 }};

Java

class Solution { public int findMin(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; } int left = 0, right = n - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { left = mid + 1; } else { right = mid; } } return nums[left]; }}

Python

class Solution: def findMin(self, nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] left, right = 0, n - 1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]

4、复杂度分析

时间复杂度：O(log n)，标准的二分查找复杂度
空间复杂度：O(1)，只使用了常数空间

Q68、寻找两个正序数组的中位数

1、题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

2、解题思路

方法一：合并后查找（不符合时间复杂度要求）

合并数组：将两个有序数组合并成一个新的有序数组
查找中位数 ：
- 如果合并后数组长度为奇数，直接返回中间元素
- 如果长度为偶数，返回中间两个元素的平均值

缺点：时间复杂度为O(m+n)，不符合题目要求

方法二：二分查找（满足时间复杂度要求）

问题转化：将中位数问题转化为寻找第k小元素的问题
二分策略 ：
- 每次比较两个数组的第k/2个元素
- 排除较小元素所在数组的前k/2个元素
- 递归查找剩下的元素
边界处理 ：
- 一个数组为空时，直接在另一个数组中查找
- k=1时，直接比较两个数组的第一个元素

3、代码实现

C++

class Solution {public: double findMedianSortedArrays(vector& nums1, vector& nums2) { int m = nums1.size(), n = nums2.size(); int total = m + n; if (total % 2 == 1) { return findKthElement(nums1, nums2, (total + 1) / 2); } else { int left = findKthElement(nums1, nums2, total / 2); int right = findKthElement(nums1, nums2, total / 2 + 1); return (left + right) / 2.0; } }private: int findKthElement(const vector& nums1, const vector& nums2, int k) { int m = nums1.size(), n = nums2.size(); int index1 = 0, index2 = 0; while (true) { // 边界情况处理 if (index1 == m) { return nums2[index2 + k - 1]; } if (index2 == n) { return nums1[index1 + k - 1]; } if (k == 1) { return min(nums1[index1], nums2[index2]); } // 正常情况处理 int newIndex1 = min(index1 + k / 2 - 1, m - 1); int newIndex2 = min(index2 + k / 2 - 1, n - 1); int pivot1 = nums1[newIndex1]; int pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= (newIndex1 - index1 + 1); index1 = newIndex1 + 1; } else { k -= (newIndex2 - index2 + 1); index2 = newIndex2 + 1; } } }};

Java

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int total = m + n; if (total % 2 == 1) { return findKthElement(nums1, nums2, (total + 1) / 2); } else { double left = findKthElement(nums1, nums2, total / 2); double right = findKthElement(nums1, nums2, total / 2 + 1); return (left + right) / 2.0; } } private int findKthElement(int[] nums1, int[] nums2, int k) { int m = nums1.length, n = nums2.length; int index1 = 0, index2 = 0; while (true) { if (index1 == m) { return nums2[index2 + k - 1]; } if (index2 == n) { return nums1[index1 + k - 1]; } if (k == 1) { return Math.min(nums1[index1], nums2[index2]); } int half = k / 2; int newIndex1 = Math.min(index1 + half - 1, m - 1); int newIndex2 = Math.min(index2 + half - 1, n - 1); int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= (newIndex1 - index1 + 1); index1 = newIndex1 + 1; } else { k -= (newIndex2 - index2 + 1); index2 = newIndex2 + 1; } } }}

Python

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: def findKthElement(k: int) -> int: index1, index2 = 0, 0 while True: if index1 == m:  return nums2[index2 + k - 1] if index2 == n:  return nums1[index1 + k - 1] if k == 1:  return min(nums1[index1], nums2[index2]) half = k // 2 new_index1 = min(index1 + half - 1, m - 1) new_index2 = min(index2 + half - 1, n - 1) pivot1, pivot2 = nums1[new_index1], nums2[new_index2] if pivot1 <= pivot2:  k -= new_index1 - index1 + 1  index1 = new_index1 + 1 else:  k -= new_index2 - index2 + 1  index2 = new_index2 + 1 m, n = len(nums1), len(nums2) total = m + n if total % 2 == 1: return findKthElement((total + 1) // 2) else: left = findKthElement(total // 2) right = findKthElement(total // 2 + 1) return (left + right) / 2

4、复杂度分析

时间复杂度：O(log(m+n))，每次递归将问题规模减半
空间复杂度：O(1)，只使用了常数空间

12、栈

Q69、有效的括号

1、题目描述

给定一个只包括 \'(\'，\')\'，\'{\'，\'}\'，\'[\'，\']\' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

示例 5：

**输入：**s = “([)]”

**输出：**false

提示：

1 <= s.length <= 104

s 仅由括号 \'()[]{}\' 组成

2、解题思路

栈的应用

初始化栈：用于存储遇到的左括号
遍历字符串 ：
- 遇到左括号时压入栈
- 遇到右括号时检查栈顶元素是否匹配
匹配检查 ：
- 栈为空或不匹配则返回false
- 匹配则弹出栈顶元素
最终检查：遍历完成后栈应为空

3、代码实现

C++

class Solution {public: bool isValid(string s) { stack st; unordered_map pairs = {{\')\', \'(\'}, {\']\', \'[\'}, {\'}\', \'{\'}}; for (char c : s) { // 当前字符是右括号 if (pairs.count(c)) { if (st.empty() || st.top() != pairs[c]) {  return false; } st.pop(); } // 当前字符是左括号 else { st.push(c); } } return st.empty(); }};

Java

class Solution { public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); Map<Character, Character> pairs = new HashMap<>(); pairs.put(\')\', \'(\'); pairs.put(\']\', \'[\'); pairs.put(\'}\', \'{\'); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (pairs.containsKey(c)) { // 右括号 if (stack.isEmpty() || stack.peek() != pairs.get(c)) {  return false; } stack.pop(); } else { // 左括号 stack.push(c); } } return stack.isEmpty(); }}

Python

class Solution: def isValid(self, s: str) -> bool: stack = [] pairs = {\')\': \'(\', \']\': \'[\', \'}\': \'{\'} for char in s: if char in pairs: # 右括号 if not stack or stack[-1] != pairs[char]:  return False stack.pop() else: # 左括号 stack.append(char) return not stack

4、复杂度分析

时间复杂度：O(n)，只需要遍历一次字符串
空间复杂度：O(n)，最坏情况下需要存储所有左括号

Q70、最小栈

1、题目描述

设计一个支持 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.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

2、解题思路

双栈法

主栈：存储所有压入的元素
辅助栈：存储当前主栈中的最小元素
操作规则 ：
- push: 主栈压入元素，辅助栈仅在元素≤当前最小值时压入
- pop: 主栈弹出元素，仅在弹出的元素等于辅助栈顶时辅助栈弹出
- top: 直接返回主栈顶元素
- getMin: 直接返回辅助栈顶元素

3、代码实现

C++

class MinStack {private: stack mainStack; // 主站存储所有元素 stack minStack; // 辅助栈存储最小元素public: // 构造函数 MinStack() {} void push(int val) { mainStack.push(val); // 压入主栈 // 如果辅助栈为空或新元素 <= 当前元素, 压入辅助栈 if (minStack.empty() || val <= minStack.top()) { minStack.push(val); } } void pop() { // 如果主栈栈顶元素等于辅助元素, 弹出辅助栈 if (mainStack.top() == minStack.top()) { minStack.pop(); } mainStack.pop(); // 弹出主栈顶 } int top() { return mainStack.top(); // 返回主栈栈顶元素 } int getMin() { return minStack.top(); // 返回辅助栈栈顶元素 (当前最小值) }};

Java

class MinStack { private Stack<Integer> mainStack; private Stack<Integer> minStack; public MinStack() { mainStack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { mainStack.push(val); if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } public void pop() { if (mainStack.peek().equals(minStack.peek())) { minStack.pop(); } mainStack.pop(); } public int top() { return mainStack.peek(); } public int getMin() { return minStack.peek(); }}

Python

class MinStack: def __init__(self): self.main_stack = [] # 主栈 self.min_stack = [] # 辅助栈 def push(self, val: int) -> None: self.main_stack.append(val) # 如果辅助栈为空或新元素≤当前最小值，压入辅助栈 if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self) -> None: # 如果主栈顶元素等于辅助栈顶元素，弹出辅助栈顶 if self.main_stack[-1] == self.min_stack[-1]: self.min_stack.pop() self.main_stack.pop() def top(self) -> int: return self.main_stack[-1] # 返回主栈顶元素 def getMin(self) -> int: return self.min_stack[-1] # 返回辅助栈顶元素(当前最小值)

4、复杂度分析

时间复杂度：所有操作均为O(1)
空间复杂度：O(n)，最坏情况下需要存储所有元素

Q71、字符串解码

1、题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = \"3[a]2[bc]\"输出：\"aaabcbc\"
示例 2：
输入：s = \"3[a2[c]]\"输出：\"accaccacc\"
示例 3：
输入：s = \"2[abc]3[cd]ef\"输出：\"abcabccdcdcdef\"
示例 4：
输入：s = \"abc3[cd]xyz\"输出：\"abccdcdcdxyz\"
提示：

1 <= s.length <= 30

s 由小写英文字母、数字和方括号 \'[]\' 组成

s 保证是一个有效的输入。

s 中所有整数的取值范围为 [1, 300]

2、解题思路

方法一：递归解析

递归处理：遇到数字时解析数字，然后递归处理方括号内的字符串
字符处理：遇到字母直接拼接
递归终止：遇到右括号或字符串结束

方法二：栈辅助处理

数字栈：存储遇到的重复次数k
字符串栈：存储当前层的字符串
处理流程 ：
- 遇到数字：解析完整数字压入数字栈
- 遇到左括号：将当前字符串压入字符串栈，开始新的字符串收集
- 遇到右括号：弹出数字栈顶k，重复当前字符串k次，与栈顶字符串拼接
- 遇到字母：直接拼接到当前字符串

3、代码实现

C++

// 方法1: 递归class Solution {private: string src; size_t ptr; // 解析数字 int getDigits() { int ret = 0; while (ptr < src.size() && isdigit(src[ptr])) { ret = ret * 10 + src[ptr++] - \'0\'; } return ret; } string getString() { if (ptr == src.size() || src[ptr] == \']\') { return \"\"; // 终止条件 } char cur = src[ptr]; string ret; // 数字情况 if (isdigit(cur)) { int repTime = getDigits(); // 获取重复次数 ++ptr;  // 跳过 \'[\' string str = getString(); // 递归获取括号内字符串 ++ptr;  // 跳过 \']\' while (repTime--) { ret += str; // 重复拼接 } } // 字母情况 else if (isalpha(cur)) { ret = string(1, src[ptr++]); } return ret + getString(); // 拼接后续字符串 }public: string decodeString(string s) { src = s; ptr = 0; return getString(); }};

// 方法2: 栈辅助法class Solution {public: string decodeString(string s) { stack nums; // 存储重复次数 stack st; // 存储字符串 st.push(\"\"); // 初始空字符串 int i = 0, n = s.size(); while (i < n) { // 处理数字 if (isdigit(s[i])) { int num = 0; while (i < n && isdigit(s[i])) {  num = num * 10 + (s[i++] - \'0\'); } nums.push(num); } // 遇到左括号 else if (s[i] == \'[\') { i++; st.push(\"\"); // 开始新字符串 } // 遇到右括号 else if (s[i] == \']\') { string tmp = st.top(); st.pop(); int k = nums.top(); nums.pop(); string repeated; while (k--) {  repeated += tmp; } st.top() += repeated; // 于上层字符串拼接 i++; } // 处理字母 else { string tmp; while (i < n && isalpha(s[i])) {  tmp += s[i++]; } st.top() += tmp; } } return st.top(); }};

Java

class Solution { public String decodeString(String s) { Deque<Integer> numStack = new ArrayDeque<>(); Deque<StringBuilder> strStack = new ArrayDeque<>(); StringBuilder current = new StringBuilder(); int num = 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num = num * 10 + (c - \'0\'); } else if (c == \'[\') { numStack.push(num); strStack.push(current); current = new StringBuilder(); num = 0; } else if (c == \']\') { int k = numStack.pop(); StringBuilder temp = strStack.pop(); for (int i = 0; i < k; i++) {  temp.append(current); } current = temp; } else { current.append(c); } } return current.toString(); }}

Python

class Solution: def decodeString(self, s: str) -> str: stack = [] current_str = \"\" current_num = 0 for char in s: if char.isdigit(): current_num = current_num * 10 + int(char) elif char == \'[\': stack.append((current_str, current_num)) current_str = \"\" current_num = 0 elif char == \']\': prev_str, num = stack.pop() current_str = prev_str + current_str * num else: current_str += char return current_str

4、复杂度分析

时间复杂度：O(n)，n为解码后字符串长度
空间复杂度：O(n)，最坏情况下需要存储所有字符

Q72、每日温度

1、题目描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]输出: [1,1,0]
提示：

1 <= temperatures.length <= 105

30 <= temperatures[i] <= 100

2、解题思路

方法一：单调栈法

单调递减栈：维护一个存储下标的栈，栈中的元素对应的温度是单调递减的
遍历数组 ：
- 当当前温度大于栈顶温度时，计算天数差并更新结果
- 将当前下标压入栈中
处理剩余元素：遍历结束后栈中剩余元素对应的天数差为0

方法二：从后向前遍历法

记录位置：使用数组记录每个温度最后一次出现的下标
逆向遍历 ：
- 对于每个温度，查找比它高的温度中最近出现的位置
- 计算天数差并更新结果
- 更新当前温度的位置

3、代码实现

C++

// 方法1: 单调栈法class Solution {public: vector dailyTemperatures(vector& temperatures) { int n = temperatures.size(); vector answer(n, 0); // 初始化结果数组, 默认值为 0 stack s; // 单调递减栈, 存储下标 for (int i = 0; i  temperatures[s.top()]) { int prevIndex = s.top();  // 获取之前温度的下标 answer[prevIndex] = i - prevIndex; // 计算天数差 s.pop(); // 弹出已处理的温度 } s.push(i); // 将当前温度下标压入栈 } return answer; }};

// 方法2: 从后向前遍历法class Solution {public: vector dailyTemperatures(vector& temperatures) { int n = temperatures.size(); vector answer(n, 0); // 初始化结果数组 vector next(101, INT_MAX); // 记录每个温度最后出现的位置 for (int i = n - 1; i >= 0; --i) { int warmerIndex = INT_MAX; // 初始化更高温度的最小下标 // 查找比当前温度高的最近温度 for (int t = temperatures[i] + 1; t <= 100; ++t) { warmerIndex = min(warmerIndex, next[t]); } // 如果找到更高温度, 则计算天数差 if (warmerIndex != INT_MAX) { answer[i] = warmerIndex - i; } // 更新当前温度的位置 next[temperatures[i]] = i; } return answer; }};

Java

class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prevIndex = stack.pop(); answer[prevIndex] = i - prevIndex; } stack.push(i); } return answer; }}

Python

class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) answer = [0] * n stack = [] for i in range(n): while stack and temperatures[i] > temperatures[stack[-1]]: prev_index = stack.pop() answer[prev_index] = i - prev_index stack.append(i)  return answer

4、复杂度分析

时间复杂度：O(n)，每个元素最多被压入和弹出栈一次
空间复杂度：O(n)，最坏情况下需要存储所有元素的下标

Q73、柱状图中最大的矩形

1、题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]输出： 4
提示：

1 <= heights.length <=105

0 <= heights[i] <= 104

2、解题思路

方法一：单调栈法（两次遍历）

确定左右边界 ：
- 使用单调递增栈分别从左到右和从右到左遍历
- 对于每个柱子，找到它左右两边第一个比它矮的柱子
计算面积 ：
- 对于每个柱子，宽度 = 右边界 - 左边界 - 1
- 面积 = 高度 × 宽度
- 取所有面积中的最大值

方法二：单调栈法（一次遍历优化）

同时确定左右边界 ：
- 在单调栈中，当遇到比栈顶矮的柱子时，可以确定栈顶柱子的右边界
- 左边界即为栈顶下一个元素
计算面积 ：
- 与方法一类似，但只需要一次遍历

3、代码实现

C++

class Solution {public: int largestRectangleArea(vector& heights) { int n = heights.size(); vector left(n), right(n); // 存储每个柱子的左右边界 stack s; // 从左到右遍历, 确定左边界 for (int i = 0; i = heights[i]) { s.pop(); // 弹出比当前柱子高的柱子 } left[i] = s.empty() ? -1 : s.top(); // 左边界 s.push(i); } s = stack(); // 清空栈 // 从右到左遍历, 确定右边界 for (int i = n - 1; i >= 0; --i) { while (!s.empty() && heights[s.top()] >= heights[i]) { s.pop(); // 弹出比当前柱子高的柱子 } right[i] = s.empty() ? n : s.top(); // 右边界 s.push(i); } int maxArea = 0; // 计算每个柱子能构成的最大面积 for (int i = 0; i < n; ++i) { maxArea = max(maxArea, (right[i] - left[i] - 1) * heights[i]); } return maxArea; }};

class Solution {public: int largestRectangleArea(vector& heights) { int n = heights.size(); vector left(n), right(n, n); // 初始化右边界 stack s; for (int i = 0; i = heights[i]) { right[s.top()] = i; // 当前柱子是栈顶柱子的右边界 s.pop(); } left[i] = s.empty() ? -1 : s.top(); // 左边界 s.push(i); } int maxArea = 0; for (int i = 0; i < n; ++i) { maxArea = max(maxArea, (right[i] - left[i] - 1) * heights[i]); } return maxArea; }};

Java

class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(right, n); Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) { right[stack.pop()] = i; } left[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } int maxArea = 0; for (int i = 0; i < n; i++) { maxArea = Math.max(maxArea, (right[i] - left[i] - 1) * heights[i]); } return maxArea; }}

Python

class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) left, right = [0] * n, [n] * n stack = [] for i in range(n): while stack and heights[stack[-1]] >= heights[i]: right[stack.pop()] = i left[i] = stack[-1] if stack else -1 stack.append(i) max_area = 0 for i in range(n): max_area = max(max_area, (right[i] - left[i] - 1) * heights[i]) return max_area

4、复杂度分析

时间复杂度：O(n)，每个元素最多被压入和弹出栈一次
空间复杂度：O(n)，需要存储左右边界信息

13、堆

Q74、数组中的第K个最大元素

1、题目描述

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: [3,2,1,5,6,4], k = 2输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4输出: 4
提示：

1 <= k <= nums.length <= 105

-104 <= nums[i] <= 104

2、解题思路

方法一：排序法

直接排序：将数组降序排序后取第k-1个元素
复杂度：时间复杂度O(nlogn)，不满足题目要求的O(n)

方法二：最大堆

构建最大堆：将所有元素放入最大堆
弹出k-1次：弹出k-1个最大元素后，堆顶即为第k大元素
复杂度：建堆O(n)，弹出O(klogn)，最坏O(nlogn)

方法三：最小堆

维护大小为k的最小堆：只保留最大的k个元素
遍历更新堆：遇到比堆顶大的元素时替换
复杂度：O(nlogk)，适合k远小于n的情况

方法四：快速选择（快速排序变种）

随机选择基准：类似快速排序的partition过程
递归选择：根据基准位置决定继续处理左/右部分
复杂度：平均O(n)，最坏O(n^2)但通过随机化避免

3、代码实现

C++

// 方法1: 快速选择class Solution {public: int findKthLargest(vector& nums, int k) { srand(time(nullptr)); // 初始化随机种子 return quickSelect(nums, 0, nums.size() - 1, k); }private: int partition(vector& nums, int left, int right) { int pivot = nums[right]; // 选择最右元素作为基准 int i = left; for (int j = left; j  pivot) { swap(nums[i++], nums[j]); } } swap(nums[i], nums[right]); // 将基准放到正确位置 return i; } int quickSelect(vector& nums, int left, int right, int k) { if (left == right) { return nums[left]; } // 随机选择基准避免最坏情况 int pivotIndex = left + rand() % (right - left + 1); swap(nums[pivotIndex], nums[right]); int pos = partition(nums, left, right); if (pos == k - 1) { return nums[pos]; } else if (pos < k - 1) { return quickSelect(nums, pos + 1, right, k); } else { return quickSelect(nums, left, pos - 1, k); } }};

// 方法2: 最小堆class Solution {public: int findKthLargest(vector& nums, int k) { priority_queue<int, vector, greater> minHeap; for (int num : nums) { if (minHeap.size()  minHeap.top()) { minHeap.pop(); minHeap.push(num); } } return minHeap.top(); }};

4、复杂度分析

快速选择：平均时间复杂度O(n)，空间复杂度O(1)
堆方法：时间复杂度O(nlogk)或O(nlogn)，空间复杂度O(n)或O(k)

Q75、前 K 个高频元素

1、题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]
示例 2:
输入: nums = [1], k = 1输出: [1]
提示：

1 <= nums.length <= 105

k 的取值范围是 [1, 数组中不相同的元素的个数]

题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**进阶：**你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

2、解题思路

方法一：最小堆（优先队列）

统计频率：使用哈希表统计每个元素的出现频率
维护大小为k的最小堆：
- 当堆大小等于k时，比较当前元素频率与堆顶频率
- 如果当前频率更高，则替换堆顶元素
收集结果：最后堆中元素即为前k高频元素

方法二：快速选择（快速排序变种）

统计频率：同样使用哈希表统计频率
将频率转为数组：将哈希表转为pair数组
快速选择 ：
- 随机选择基准进行分区
- 根据基准位置决定处理左/右部分
- 收集前k高频元素

3、代码实现

C++

// 方法1: 最小堆class Solution {public: vector topKFrequent(vector& nums, int k) { // 1. 统计频率 unordered_map freqMap; for (int num : nums) { freqMap[num]++; } // 2. 定义最小堆比较函数 auto cmp = [](const pair& a, const pair& b) { return a.second > b.second; // 按频率升序排序 }; // 3. 维护大小为 k 的最小堆 priority_queue<pair, vector<pair>, decltype(cmp)> minHeap(cmp); for (const auto& entry : freqMap) { if (minHeap.size()  minHeap.top().second) { minHeap.pop(); minHeap.push(entry); } } // 4. 收集结果 vector result; while (!minHeap.empty()) { result.push_back(minHeap.top().first); minHeap.pop(); } return result; }};

// 方法2: 快速选择class Solution {public: vector topKFrequent(vector& nums, int k) { // 1. 统计频率 unordered_map freqMap; for (int num : nums) { freqMap[num]++; } // 2. 转为 vector vector<pair> elements(freqMap.begin(), freqMap.end()); // 3. 快速选择前 k 大元素 quickSelect(elements, 0, elements.size() - 1, k - 1); // 4. 收集结果 vector result; for (int i = 0; i < k; ++i) { result.push_back(elements[i].first); } return result; }private: void quickSelect(vector<pair>& elements, int left, int right, int k) { if (left >= right) { return; } // 随机选择基准 int pivotIndex = left + rand() % (right - left + 1); swap(elements[pivotIndex], elements[left]); int pivot = elements[left].second; int i = left, j = right; // 分区操作 while (i < j) { while (i < j && elements[j].second <= pivot) { --j; } while (i = pivot) { ++i; } if (i < j) { swap(elements[i], elements[j]); } } swap(elements[left], elements[i]); // 递归处理 if (i  k) { quickSelect(elements, left, i - 1, k); } }};

Java

class Solution { public int[] topKFrequent(int[] nums, int k) { // 统计频率 Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } // 最小堆 PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue()); // 维护大小为k的堆 for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) { if (minHeap.size() < k) { minHeap.offer(entry); } else if (entry.getValue() > minHeap.peek().getValue()) { minHeap.poll(); minHeap.offer(entry); } } // 收集结果 int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = minHeap.poll().getKey(); } return result; }}

Python

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # 统计频率 freq = defaultdict(int) for num in nums: freq[num] += 1 # 维护大小为k的最小堆 heap = [] for num, count in freq.items(): if len(heap) < k: heapq.heappush(heap, (count, num)) else: if count > heap[0][0]:  heapq.heappop(heap)  heapq.heappush(heap, (count, num)) # 收集结果 return [num for (count, num) in heap]

4、复杂度分析

最小堆：时间复杂度O(nlogk)，空间复杂度O(n)
快速选择：平均时间复杂度O(n)，最坏O(n^2)，空间复杂度O(n)

Q76、数据流的中位数

1、题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入[\"MedianFinder\", \"addNum\", \"addNum\", \"findMedian\", \"addNum\", \"findMedian\"][[], [1], [2], [], [3], []]输出[null, null, null, 1.5, null, 2.0]解释MedianFinder medianFinder = new MedianFinder();medianFinder.addNum(1); // arr = [1]medianFinder.addNum(2); // arr = [1, 2]medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)medianFinder.addNum(3); // arr[1, 2, 3]medianFinder.findMedian(); // return 2.0

提示:

-105 <= num <= 105
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 104 次调用 addNum 和 findMedian

2、解题思路

方法一：双堆法

大根堆和小根堆 ：
- 大根堆存储较小的一半数字
- 小根堆存储较大的一半数字
平衡两个堆 ：
- 保持大根堆的大小等于或比小根堆大1
- 添加数字时根据大小关系决定放入哪个堆
获取中位数 ：
- 如果两堆大小相等，取两堆顶的平均值
- 否则取大根堆的堆顶

方法二：有序集合法

维护一个有序集合 ：
- 使用multiset保持元素有序
维护两个指针 ：
- left和right始终指向中间的一个或两个元素
插入时调整指针：
- 根据插入元素的位置调整指针位置
获取中位数 ：
- 取left和right指向元素的平均值

3、代码实现

C++

// 方法1: 双堆法class MedianFinder {private: priority_queue maxHeap; // 存储较小的一半, 大根堆 priority_queue<int, vector, greater> minHeap; // 存储较大的一半, 小根堆public: MedianFinder() {} void addNum(int num) { if (maxHeap.empty() || num  minHeap.size() + 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } else if (minHeap.size() > maxHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double findMedian() { if (maxHeap.size() == minHeap.size()) { return (maxHeap.top() + minHeap.top()) / 2.0; } else { return maxHeap.top(); } }};

// 方法2: 有序集合法class MedianFinder {private: multiset data; multiset::iterator left, right;public: MedianFinder() : left(data.end()), right(data.end()) {} void addNum(int num) { const size_t n = data.size(); data.insert(num); if (!n) { left = right = data.begin(); } // 之前是奇数个数 else if (n % 2 == 1) { if (num  *left && num = *right) { left++; } else { right--; left = right; } } } double findMedian() { return (*left + *right) / 2.0; }};

Java

class MedianFinder { private PriorityQueue<Integer> maxHeap; // 存储较小的一半 private PriorityQueue<Integer> minHeap; // 存储较大的一半 public MedianFinder() { maxHeap = new PriorityQueue<>((a, b) -> b - a); minHeap = new PriorityQueue<>(); } public void addNum(int num) { if (maxHeap.isEmpty() || num <= maxHeap.peek()) { maxHeap.offer(num); } else { minHeap.offer(num); } // 平衡两个堆的大小 if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (maxHeap.peek() + minHeap.peek()) / 2.0; } else { return maxHeap.peek(); } }}

Python

class MedianFinder: def __init__(self): self.max_heap = [] # 存储较小的一半，使用负数模拟大根堆 self.min_heap = [] # 存储较大的一半 def addNum(self, num: int) -> None: if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # 平衡两个堆的大小 if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def findMedian(self) -> float: if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2 else: return -self.max_heap[0]

4、复杂度分析

双堆法：
- addNum: O(logn)
- findMedian: O(1)
有序集合法：
- addNum: O(logn)
- findMedian: O(1)

14、贪心算法

Q77、买卖股票的最佳时机

1、题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

2、解题思路

方法：一次遍历

维护最低价格：记录遍历过程中遇到的最低价格
计算当前利润：当前价格减去最低价格
更新最大利润：比较当前利润和历史最大利润
最终结果：返回最大利润

3、代码实现

C++

class Solution {public: int maxProfit(vector& prices) { int minPrice = INT_MAX; // 初始化最低价格为最大整数 int maxProfit = 0; // 初始化最大利润为 0 for (int price : prices) { // 如果当前价格比最低价格低, 更新最低价格 if (price  maxProfit) { maxProfit = price - minPrice; } } return maxProfit; }};

Java

class Solution { public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { if (price < minPrice) { minPrice = price; } else if (price - minPrice > maxProfit) { maxProfit = price - minPrice; } } return maxProfit; }}

Python

class Solution: def maxProfit(self, prices: List[int]) -> int: min_price = float(\'inf\') max_profit = 0 for price in prices: if price < min_price: min_price = price elif price - min_price > max_profit: max_profit = price - min_price return max_profit

4、复杂度分析

时间复杂度：O(n)，只需要遍历一次数组
空间复杂度：O(1)，只使用了常数个变量

Q78、跳跃游戏

1、题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

2、解题思路

方法：贪心算法

维护最大可达位置：记录当前能跳到的最远位置
遍历数组 ：
- 如果当前位置超过了最大可达位置，说明无法到达当前位置及其后续位置
- 否则更新最大可达位置
判断终点可达：如果最大可达位置包含最后一个位置，则返回true

3、代码实现

C++

class Solution {public: bool canJump(vector& nums) { int maxReach = 0; // 当前能达到的最远位置 int n = nums.size(); for (int i = 0; i  maxReach) { return false; } // 更新能到达的最远位置 maxReach = max(maxReach, i + nums[i]); // 如果能到达或者最后一个位置 if (maxReach >= n - 1) { return true; } } return true; }};

Java

class Solution { public boolean canJump(int[] nums) { int maxReach = 0; int n = nums.length; for (int i = 0; i < n; i++) { if (i > maxReach) { return false; } maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= n - 1) { return true; } } return true; }}

Python

class Solution: def canJump(self, nums: List[int]) -> bool: max_reach = 0 n = len(nums) for i in range(n): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) if max_reach >= n - 1: return True return True

4、复杂度分析

时间复杂度：O(n)，只需要遍历一次数组
空间复杂度：O(1)，只使用了常数个变量

Q79、跳跃游戏 II

1、题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

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

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

2、解题思路

方法一：贪心算法（边界扩展）

维护边界：记录当前跳跃能到达的边界
遍历数组 ：
- 在当前位置到边界范围内，寻找能跳到的最远位置
- 到达边界时，增加跳跃次数并更新边界
终止条件：边界到达或超过数组末尾

方法二：贪心算法（优化版）

维护两个指针：当前跳跃的边界和能到达的最远位置
遍历数组：
- 更新能到达的最远位置
- 到达边界时增加跳跃次数并更新边界
提前终止：当边界已经到达数组末尾时停止

3、代码实现

C++

class Solution {public: int jump(vector& nums) { int jumps = 0; int start = 0; int end = 1; while (end < nums.size()) { int maxPos = 0; // 在当前范围内寻找能跳到的最远位置 for (int i = start; i < end; ++i) { maxPos = max(maxPos, i + nums[i]); } start = end; // 下一次起跳范围的起点 end = maxPos + 1; // 下一次起跳范围的终点 jumps++; // 跳跃次数增加 } return jumps; }};

class Solution {public: int jump(vector& nums) { int jumps = 0; int end = 0; // 当前跳跃能到达的边界 int maxPos = 0; // 能到达的最远位置 for (int i = 0; i < nums.size() - 1; ++i) { // 更新能到达的最远位置 maxPos = max(maxPos, i + nums[i]); // 到达边界, 增加跳跃次数并更新边界 if (i == end) { end = maxPos; jumps++; } } return jumps; }};

Java

class Solution { public int jump(int[] nums) { int jumps = 0; int end = 0; int maxPos = 0; for (int i = 0; i < nums.length - 1; i++) { maxPos = Math.max(maxPos, i + nums[i]); if (i == end) { end = maxPos; jumps++; } } return jumps; }}

Python

class Solution: def jump(self, nums: List[int]) -> int: jumps = 0 end = 0 max_pos = 0 for i in range(len(nums) - 1): max_pos = max(max_pos, i + nums[i]) if i == end: end = max_pos jumps += 1 return jumps

4、复杂度分析

时间复杂度：O(n)，只需要遍历一次数组
空间复杂度：O(1)，只使用了常数个变量

Q80、划分字母区间

1、题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 \"ababcc\" 能够被分为 [\"abab\", \"cc\"]，但类似 [\"aba\", \"bcc\"] 或 [\"ab\", \"ab\", \"cc\"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = \"ababcbacadefegdehijhklij\"输出：[9,7,8]解释：划分结果为 \"ababcbaca\"、\"defegde\"、\"hijhklij\" 。每个字母最多出现在一个片段中。像 \"ababcbacadefegde\", \"hijhklij\" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = \"eccbbbbdec\"输出：[10]

提示：

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

2、解题思路

方法：贪心算法

记录最后出现位置：先遍历字符串，记录每个字符最后一次出现的位置
维护当前片段的边界 ：
- 遍历字符串，不断更新当前片段的结束边界
- 当遍历到当前片段的边界时，记录片段长度
- 开始新的片段

3、代码实现

C++

class Solution {public: vector partitionLabels(string s) { int last[26] = {0}; // 存储每个字母最后出现的位置 int length = s.size(); // 第一次遍历: 记录每个字母最后出现的位置 for (int i = 0; i < length; ++i) { last[s[i] - \'a\'] = i; } vector result; int start = 0, end = 0; // 第二次遍历: 划分片段 for (int i = 0; i < length; ++i) { // 更新当前片段的结束边界 end = max(end, last[s[i] - \'a\']); // 到达当前片段的结束边界 if (i == end) { // 记录当前片段的长度 result.push_back(end - start + 1); // 开始新的片段 start = end + 1; } } return result; }};

Java

class Solution { public List<Integer> partitionLabels(String s) { int[] last = new int[26]; int length = s.length(); // 记录每个字母最后出现的位置 for (int i = 0; i < length; i++) { last[s.charAt(i) - \'a\'] = i; } List<Integer> result = new ArrayList<>(); int start = 0, end = 0; for (int i = 0; i < length; i++) { // 更新当前片段的结束边界 end = Math.max(end, last[s.charAt(i) - \'a\']); // 到达当前片段的结束边界 if (i == end) { // 记录当前片段的长度 result.add(end - start + 1); // 开始新的片段 start = end + 1; } } return result; }}

Python

class Solution: def partitionLabels(self, s: str) -> List[int]: last = [0] * 26 for idx, ch in enumerate(s): last[ord(ch) - ord(\"a\")] = idx result = [] start = end = 0 for idx, ch in enumerate(s): end = max(end, last[ord(ch) - ord(\"a\")]) if idx == end: result.append(end - start + 1) start = end + 1 return result

4、复杂度分析

时间复杂度：O(n)，需要两次遍历字符串
空间复杂度：O(1)，使用固定大小的数组存储字符的最后位置

15、动态规划

Q81、爬楼梯

1、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

示例 2：

输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

提示：

1 <= n <= 45

2、解题思路

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

状态转移方程：f(n) = f(n-1) + f(n-2)
空间优化：只需要保存前两个状态，空间复杂度从O(n)降低到O(1)
边界条件：f(0)=1, f(1)=1

方法二：动态规划（标准版）

定义dp数组：dp[i]表示爬到第i阶的方法数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
初始化：dp[0] = dp[1] = 1

3、代码实现

C++

class Solution {public: int climbStairs(int n) { int p = 0, q = 0, r = 1; // p 代表 f(n-2), q 代表 f(n-1), r 代表 f(n) for (int i = 1; i <= n; ++i) { p = q; // 更新 f(n-2) 为上一轮的 f(n-1) q = r; // 更新 f(n-1) 为上一轮的 f(n); r = p + q; // 计算当前的 f(n) = f(n-1) + f(n-2) } return r; }};

class Solution {public: int climbStairs(int n) { if (n == 1) { return 1; // 边界条件 } vector dp(n + 1); // dp 数组 dp[0] = 1; // 初始状态: 0 阶有 1 种方法 (不爬) dp[1] = 1; // 初始状态: 1 阶有 1 种方法 for (int i = 2; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程 } return dp[n]; }};

Java

class Solution { public int climbStairs(int n) { int p = 0, q = 0, r = 1; for (int i = 1; i <= n; ++i) { p = q; q = r; r = p + q; } return r; }}

Python

class Solution: def climbStairs(self, n: int) -> int: p, q, r = 0, 0, 1 for _ in range(n): p, q = q, r r = p + q return r

4、复杂度分析

时间复杂度：O(n)，需要一次遍历
空间复杂度：
- 方法一：O(1)
- 方法二：O(n)

Q82、杨辉三角

1、题目描述

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

《LeetCode 热题 100》整整 100 题量大管饱题解套餐下

示例 1:
输入: numRows = 5输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1输出: [[1]]
提示:

1 <= numRows <= 30

2、解题思路

方法：动态生成

初始化：创建一个二维数组来存储结果
填充每一行 ：
- 每行的第一个和最后一个元素都是1
- 中间元素等于上一行同列和前一个列元素之和
边界处理：处理第一行和第二行的特殊情况

3、代码实现

C++

class Solution {public: vector<vector> generate(int numRows) { vector<vector> triangle(numRows); // 创建结果二维数组 for (int i = 0; i < numRows; ++i) { triangle[i].resize(i + 1);  // 每行有 i+1 个元素 triangle[i][0] = triangle[i][i] = 1; // 首尾元素为 1 // 计算中间元素 for (int j = 1; j < i; ++j) { triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]; } } return triangle; }};

Java

class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> triangle = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List<Integer> row = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) {  row.add(1); // 首尾元素为1 } else {  // 中间元素等于上一行的j-1和j位置元素之和  row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j)); } } triangle.add(row); } return triangle; }}

Python

class Solution: def generate(self, numRows: int) -> List[List[int]]: triangle = [] for row_num in range(numRows): row = [None for _ in range(row_num + 1)] row[0], row[-1] = 1, 1 # 首尾元素为1 for j in range(1, len(row) - 1): row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j] triangle.append(row) return triangle

4、复杂度分析

时间复杂度：O(n²)，需要填充n(n+1)/2个元素
空间复杂度：O(n²)，存储整个杨辉三角

Q83、打家劫舍

1、题目描述

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

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

示例 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

2、解题思路

方法一：动态规划（标准版）

定义状态：dp[i]表示偷窃到第i个房屋时能获得的最大金额
状态转移方程 ：
- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始化 ：
- dp[0] = nums[0]
- dp[1] = max(nums[0], nums[1])

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

优化空间：只需要保存前两个状态，空间复杂度从O(n)降到O(1)
维护两个变量：
- first表示dp[i-2]
- second表示dp[i-1]

3、代码实现

C++

class Solution {public: int rob(vector& nums) { if (nums.empty()) { return 0; // 空数组返回 0 } int n = nums.size(); if (n == 1) { return nums[0]; // 只有一个房屋直接返回 } vector dp(n, 0); // dp 数组 dp[0] = nums[0];  // 初始化状态: 只偷第 0 间 dp[1] = max(nums[0], nums[1]); // 初始化状态: 偷第 0 间或第 1 间 for (int i = 2; i < n; ++i) { // 状态转移: 要么偷当前房屋 + 前两间的最大值, // 要么不偷当前房屋取前一间的值 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[n - 1]; // 返回最后一个状态 }};

class Solution {public: int rob(vector& nums) { if (nums.empty()) { return 0; } int n = nums.size(); if (n == 1) { return nums[0]; } int first = nums[0]; // 相当于 dp[i-2] int second = max(nums[0], nums[1]); // 相当于 dp[i-1] for (int i = 2; i < n; ++i) { int tmp = second; second = max(first + nums[i], second); // 更新当前最大值 first = tmp; // 更新前一个值 } return second; }};

Java

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

Python

class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) if n == 1: return nums[0] first, second = nums[0], max(nums[0], nums[1]) for i in range(2, n): first, second = second, max(first + nums[i], second) return second

4、复杂度分析

时间复杂度：O(n)，需要遍历整个数组一次
空间复杂度：
- 方法一：O(n)
- 方法二：O(1)

Q84、完全平方数

1、题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
输入：n = 12输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13输出：2解释：13 = 4 + 9
提示：

1 <= n <= 104

2、解题思路

方法一：动态规划（标准版）

定义状态：dp[i]表示和为i的完全平方数的最少数量
状态转移方程 ：
- dp[i] = min(dp[i], dp[i - jj] + 1) 对所有jj ≤ i
初始化 ：
- dp[0] = 0
- 其他初始化为INT_MAX或较大值

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

优化空间：使用一维数组代替二维数组
逆向遍历：确保每个平方数只被使用一次

方法三：数学方法（四平方和定理）

四平方和定理：任何自然数都可以表示为最多4个平方数的和
特殊情况处理 ：
- 如果n是平方数，返回1
- 如果n满足特定形式，返回4
- 否则尝试返回2或3

3、代码实现

C++

class Solution {public: int numSquares(int n) { int m = sqrt(n); vector<vector> dp(m + 1, vector(n + 1)); for (int j = 1; j <= n; ++j) { dp[0][j] = INT_MAX / 2; } for (int i = 1; i <= m; ++i) { for (int j = 0; j = i * i) {  dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1); } } } return dp[m][n]; }};

class Solution {public: int numSquares(int n) { vector dp(n + 1, INT_MAX); // dp 数组初始化为最大值 dp[0] = 0;// 和为 0 需要 0 个平方数 // 计算每个 i 的最小平方数 for (int i = 1; i <= n; ++i) { // 遍历所有可能的平方数 for (int j = 1; j * j <= i; ++j) { dp[i] = min(dp[i], dp[i - j * j] + 1); // 状态转移方程 } } return dp[n]; }};

Java

class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j * j <= i; ++j) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; }}

Python

class Solution: def numSquares(self, n: int) -> int: dp = [float(\'inf\')] * (n + 1) dp[0] = 0 for i in range(1, n + 1): j = 1 while j * j <= i: dp[i] = min(dp[i], dp[i - j * j] + 1) j += 1 return dp[n]

4、复杂度分析

时间复杂度：O(n√n)，需要计算√n次内循环
空间复杂度：O(n)，存储dp数组

Q85、零钱兑换

1、题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3输出：-1
示例 3：
输入：coins = [1], amount = 0输出：0
提示：

1 <= coins.length <= 12

1 <= coins[i] <= 231 - 1

0 <= amount <= 104

2、解题思路

方法一：动态规划（二维数组）

定义状态：dp[i][j]表示使用前i种硬币凑成金额j的最少数量
状态转移方程 ：
- 不使用当前硬币：dp[i][j] = dp[i-1][j]
- 使用当前硬币：dp[i][j] = min(dp[i][j], dp[i][j-coins[i-1]] + 1)
初始化 ：
- dp[0][j] = ∞（无法用0种硬币凑出任何金额）
- dp[i][0] = 0（金额0需要0个硬币）

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

优化空间：使用一维数组代替二维数组
正向遍历：因为硬币可以无限使用，所以从前向后更新

方法三：动态规划（另一种实现）

初始化：dp数组初始化为MAX=amount+1
状态转移：对于每个金额i，尝试使用所有硬币

3、代码实现

C++

// 方法1: 二维数组class Solution {public: int coinChange(vector& coins, int amount) { int n = coins.size(); vector<vector> dp(n + 1, vector(amount + 1, 0)); // 初始化: 使用 0 种硬币无法凑出任何金额 (除 0 外) for (int j = 1; j <= amount; ++j) { dp[0][j] = INT_MAX / 2; // 防止溢出 } for (int i = 1; i <= n; ++i) { for (int j = 0; j = coins[i - 1]) {  dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1); } } } return dp[n][amount] >= INT_MAX / 2 ? -1 : dp[n][amount]; }};

// 方法2: 空间优化class Solution {public: int coinChange(vector& coins, int amount) { vector dp(amount + 1, INT_MAX / 2); dp[0] = 0; // 金额 0 需要 0 个硬币 for (int coin : coins) { for (int j = coin; j = INT_MAX / 2 ? -1 : dp[amount]; }};

Java

class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); // 初始化为不可能的大值 dp[0] = 0; for (int coin : coins) { for (int j = coin; j <= amount; j++) { dp[j] = Math.min(dp[j], dp[j - coin] + 1); } } return dp[amount] > amount ? -1 : dp[amount]; }}

Python

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float(\'inf\')] * (amount + 1) dp[0] = 0 for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j - coin] + 1) return dp[amount] if dp[amount] != float(\'inf\') else -1

4、复杂度分析

时间复杂度：O(n*amount)，其中n是硬币种类数
空间复杂度：
- 方法一：O(n*amount)
- 方法二/三：O(amount)

Q86、单词拆分

1、题目描述

给你一个字符串 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 中的所有字符串 互不相同

2、解题思路

动态规划方法

定义状态：dp[i]表示字符串s的前i个字符能否被拆分成字典中的单词
状态转移方程 ：
- dp[i] = true 如果存在j < i，使得dp[j]为true且s[j…i-1]在字典中
初始化 ：
- dp[0] = true（空字符串默认可以被拆分）
优化：
- 使用哈希集合存储字典以便快速查找
- 反向遍历可以减少不必要的检查

3、代码实现

C++

class Solution {public: bool wordBreak(string s, vector& wordDict) { unordered_set dict(wordDict.begin(), wordDict.end()); // 将字典存入哈希集合 int n = s.length(); vector dp(n + 1, false); // dp 数组, dp[i] 表示前 i 个字符是否被拆分 dp[0] = true;  // 空字符串可以被拆分 // 遍历每个字符位置 for (int i = 1; i <= n; ++i) { // 检查所有可能的分割点 for (int j = 0; j < i; ++j) { // 如果前 j 个可拆分且 j 到 i 在字典中 if (dp[j] && dict.count(s.substr(j, i - j))) {  dp[i] = true;  break; // 找到一个有效分割即可 } } } return dp[n]; // 返回整个字符串能否被拆分 }};

Java

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<>(wordDict); // 字典存入哈希集合 int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; // 空字符串 for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && dict.contains(s.substring(j, i))) {  dp[i] = true;  break; } } } return dp[n]; }}

Python

word_set = set(wordDict) # 转换为集合提高查找效率 n = len(s) dp = [False] * (n + 1) dp[0] = True # 空字符串 for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set:  dp[i] = True  break return dp[n]

4、复杂度分析

时间复杂度：O(n²)，其中n是字符串长度
空间复杂度：O(n)，用于存储dp数组

Q87、最长递增子序列

1、题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]输出：1
提示：

1 <= nums.length <= 2500

-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

2、解题思路

方法一：动态规划（O(n²)）

定义状态：dp[i]表示以nums[i]结尾的最长递增子序列长度
状态转移 ：
- 对于每个i，遍历所有j < i
- 如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)
初始化：所有dp[i]初始化为1
结果：dp数组中的最大值

方法二：动态规划+二分查找（O(n log n)）

维护数组：dp数组存储当前可能的最长递增子序列
遍历元素 ：
- 当前元素大于dp末尾元素：直接追加
- 否则：用二分查找找到第一个不小于当前元素的位置并替换
结果：dp数组的长度即为答案

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int lengthOfLIS(vector& nums) { int n = nums.size(); vector dp(n, 1); // dp[i] 表示以 nums[i] 结尾的 LIS 长度 int max_len = 1; // 至少为 1 for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) {  dp[i] = max(dp[i], dp[j] + 1); } } max_len = max(max_len, dp[i]); } return max_len; }};

// 方法2: 贪心 + 二分查找class Solution {public: int lengthOfLIS(vector& nums) { vector dp; // 维护的可能 LIS 序列 for (int num : nums) { // 查找第一个不小于 num 的位置 auto it = lower_bound(dp.begin(), dp.end(), num); if (it == dp.end()) { dp.push_back(num); // num 比所有都大, 直接追加 } else { *it = num; // 替换第一个不小于 num 的元素 } } return dp.size(); }};

Java

class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) {  dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; }}

class Solution { public int lengthOfLIS(int[] nums) { List dp = new ArrayList(); for (int num : nums) { int pos = binarySearch(dp, num); if (pos == dp.size()) { dp.add(num); } else { dp.set(pos, num); } } return dp.size(); } private int binarySearch(List list, int target) { int left = 0, right = list.size(); while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) < target) { left = mid + 1; } else { right = mid; } } return left; }}

Python

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) dp = [1] * n max_len = 1 for i in range(1, n): for j in range(i): if nums[j] < nums[i]:  dp[i] = max(dp[i], dp[j] + 1) max_len = max(max_len, dp[i]) return max_len

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [] for num in nums: idx = bisect.bisect_left(dp, num) if idx == len(dp): dp.append(num) else: dp[idx] = num return len(dp)

4、复杂度分析

方法一：时间复杂度O(n²)，空间复杂度O(n)
方法二：时间复杂度O(n log n)，空间复杂度O(n)

Q88、乘积最大子数组

1、题目描述

给你一个整数数组 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 * 104

-10 <= nums[i] <= 10

nums 的任何子数组的乘积都保证是一个 32-位 整数

2、解题思路

动态规划方法

由于乘积可能由正数乘以正数或负数乘以负数得到，因此需要同时记录最大乘积和最小乘积。

定义状态：
- f[i]：以nums[i-1]结尾的子数组的最大乘积
- g[i]：以nums[i-1]结尾的子数组的最小乘积
状态转移方程：
- f[i] = max(nums[i-1], f[i-1]*nums[i-1], g[i-1]*nums[i-1])
- g[i] = min(nums[i-1], f[i-1]*nums[i-1], g[i-1]*nums[i-1])
初始化：
- f[0] = g[0] = 1（空数组的乘积为1）
- ret初始化为INT_MIN
结果：遍历过程中记录的最大f[i]值

3、代码实现

C++

class Solution {public: int maxProduct(vector& nums) { int n = nums.size(); vector f(n + 1), g(n + 1); // f[i] 表示以 nums[i-1] 结尾的最大乘积, g[i] 表示最小乘积 f[0] = g[0] = 1; int ret = INT_MIN; for (int i = 1; i <= n; ++i) { int x = nums[i - 1]; int y = f[i - 1] * x; int z = g[i - 1] * x; f[i] = max(x, max(y, z)); g[i] = min(x, min(y, z)); ret = max(ret, f[i]); } return ret; }};

class Solution {public: int maxProduct(vector& nums) { int maxProd = nums[0], minProd = nums[0], ret = nums[0]; for (int i = 1; i < nums.size(); ++i) { int x = nums[i]; int y = maxProd * x; int z = minProd * x; maxProd = max(x, max(y, z)); minProd = min(x, min(y, z)); ret = max(ret, maxProd); } return ret; }};

Java

class Solution { public int maxProduct(int[] nums) { int maxProd = nums[0], minProd = nums[0], ret = nums[0]; for (int i = 1; i < nums.length; i++) { int x = nums[i]; int y = maxProd * x; int z = minProd * x; maxProd = Math.max(x, Math.max(y, z)); minProd = Math.min(x, Math.min(y, z)); ret = Math.max(ret, maxProd); } return ret; }}

Python

class Solution: def maxProduct(self, nums: List[int]) -> int: max_prod = min_prod = result = nums[0] for num in nums[1:]: x = num y = max_prod * x z = min_prod * x max_prod = max(x, y, z) min_prod = min(x, y, z) result = max(result, max_prod) return result

4、复杂度分析

时间复杂度：O(n)，只需一次遍历数组
空间复杂度：O(n)，使用两个数组存储状态

Q89、分割等和子集

1、题目描述

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

2、解题思路

动态规划方法（0-1背包问题变种）

问题转化：判断是否存在子集的和等于总和的一半
步骤：
- 计算数组总和sum
- 如果sum为奇数，直接返回false
- 目标是找到若干元素使其和为sum/2
- 使用动态规划求解0-1背包问题

动态规划状态定义

二维数组版本 ：
- dp[i][j]：前i个元素是否能凑出和为j
- 状态转移方程：
  - dp[i][j] = dp[i-1][j]（不选第i个元素）
  - 或dp[i-1][j-nums[i-1]]（选第i个元素）
空间优化版本 ：
- 使用一维数组，从后向前更新

3、代码实现

C++

// 方法1: dp二维数组class Solution {public: bool canPartition(vector& nums) { int n = nums.size(); if (n < 2) { return false; // 至少需要两个元素才能分割 } int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2 != 0) { return false; // 总和为奇数直接返回 false } int half = sum / 2; vector<vector> dp(n + 1, vector(half + 1, false)); // 初始条件: 和为 0 总是可以达成 (不选任何元素) for (int i = 0; i <= n; ++i) { dp[i][0] = true; } for (int i = 1; i <= n; ++i) { for (int j = 1; j = nums[i - 1]) {  dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]]; // 选当前元素 } } } return dp[n][half]; }};

// 方法2: dp一维数组class Solution {public: bool canPartition(vector& nums) { int n = nums.size(); if (n < 2) { return false; } int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2 != 0) { return false; } int half = sum / 2; vector dp(half + 1, false); dp[0] = true; // 初始条件 for (int i = 0; i = nums[i]; --j) { dp[j] = dp[j] || dp[j - nums[i]]; } } return dp[half]; }};

Java

class Solution { public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) { return false; } int sum = 0; for (int num : nums) { sum += num; } if (sum % 2 != 0) { return false; } int half = sum / 2; boolean[] dp = new boolean[half + 1]; dp[0] = true; for (int num : nums) { for (int j = half; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; } } return dp[half]; }}

Python

class Solution: def canPartition(self, nums: List[int]) -> bool: n = len(nums) if n < 2: return False total = sum(nums) if total % 2 != 0: return False half = total // 2 dp = [False] * (half + 1) dp[0] = True for num in nums: for j in range(half, num - 1, -1): dp[j] = dp[j] or dp[j - num] return dp[half]

4、复杂度分析

时间复杂度：O(n×sum)，其中sum是数组总和的一半
空间复杂度：二维版本O(n×sum)，一维版本O(sum)

Q90、最长有效括号

1、题目描述

给你一个只包含 \'(\' 和 \')\' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = \"(()\"输出：2解释：最长有效括号子串是 \"()\"
示例 2：
输入：s = \")()())\"输出：4解释：最长有效括号子串是 \"()()\"
示例 3：
输入：s = \"\"输出：0
提示：

0 <= s.length <= 3 * 104

s[i] 为 \'(\' 或 \')\'

2、解题思路

方法一：动态规划

定义状态：dp[i]表示以s[i]结尾的最长有效括号子串长度
状态转移 ：
- s[i]=‘)‘且s[i-1]=’(’：dp[i] = dp[i-2] + 2
- s[i]=‘)‘且s[i-1]=’)’：检查前面是否有匹配的’(’
初始化：dp数组初始化为0
结果：dp数组中的最大值

方法二：栈

使用栈：栈底始终保存最后一个不能匹配的’)\'的位置
遍历字符串 ：
- ‘(’：压栈
- ‘)’：弹出栈顶，计算当前有效长度
结果：记录过程中的最大长度

方法三：双向遍历

从左到右：统计左右括号数量，相等时更新最大值
从右到左：同上，处理左括号多的情况
结果：两次遍历中的最大值

3、代码实现

C++

// 方法1: 动态规划class Solution {public: int longestValidParentheses(string s) { int n = s.size(), max_len = 0; vector dp(n, 0); // dp[i] 表示以 s[i] 结尾的最长有效括号长度 for (int i = 1; i = 2 ? dp[i - 2] : 0) + 2; } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == \'(\') {  // 形如 \"...((...))\"  dp[i] = dp[i - 1] + ((i - dp[i - 1] - 2) >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2; } max_len = max(max_len, dp[i]); } } return max_len; }};

// 方法2: 栈方法class Solution {public: int longestValidParentheses(string s) { stack stk; stk.push(-1); // 初始基准位置 int max_len = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] == \'(\') { stk.push(i); } else { stk.pop(); if (stk.empty()) {  stk.push(i); // 更新基准位置 } else {  max_len = max(max_len, i - stk.top()); } } } return max_len; }};

// 方法3: 双向遍历class Solution {public: int longestValidParentheses(string s) { int left = 0, right = 0, max_len = 0; // 从左到右遍历 for (char c : s) { if (c == \'(\') { left++; } else { right++; } if (left == right) { max_len = max(max_len, 2 * right); } else if (right > left) { left = right = 0; } } left = right = 0; // 从右向左遍历 for (int i = s.size() - 1; i >= 0; --i) { if (s[i] == \'(\') { left++; } else { right++; } if (left == right) { max_len = max(max_len, 2 * left); } else if (left > right) { left = right = 0; } } return max_len; }};

Java

class Solution { public int longestValidParentheses(String s) { Stack<Integer> stack = new Stack<>(); stack.push(-1); int maxLen = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == \'(\') { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) {  stack.push(i); } else {  maxLen = Math.max(maxLen, i - stack.peek()); } } } return maxLen; }}

Python

class Solution: def longestValidParentheses(self, s: str) -> int: left = right = max_len = 0 # Left to right pass for c in s: if c == \'(\': left += 1 else: right += 1 if left == right: max_len = max(max_len, 2 * right) elif right > left: left = right = 0 left = right = 0 # Right to left pass for c in reversed(s): if c == \'(\': left += 1 else: right += 1 if left == right: max_len = max(max_len, 2 * left) elif left > right: left = right = 0 return max_len

4、复杂度分析

动态规划：时间复杂度O(n)，空间复杂度O(n)
栈方法：时间复杂度O(n)，空间复杂度O(n)
双向遍历：时间复杂度O(n)，空间复杂度O(1)

16、多维动态规划

Q91、不同路径

1、题目描述

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

《LeetCode 热题 100》整整 100 题量大管饱题解套餐下

输入：m = 3, n = 7输出：28

示例 2：

输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3输出：28

示例 4：

输入：m = 3, n = 3输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

2、解题思路

方法一：动态规划

定义状态：dp[i][j]表示到达(i,j)格子的路径数
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化：第一行和第一列都为1（只有一条路径）
结果：dp[m-1][n-1]

方法二：记忆化递归

递归关系：f(i,j) = f(i-1,j) + f(i,j-1)
终止条件：i=1或j=1时返回1
记忆化：存储已计算结果避免重复计算

3、代码实现

C++

// 方法1: 动态规划二维数组class Solution {public: int uniquePaths(int m, int n) { vector<vector> dp(m, vector(n, 1)); // 初始化所有值为 1 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; }};

// 方法2: 动态规划一维数组class Solution {public: int uniquePaths(int m, int n) { vector dp(n, 1); // 只需要一维数组 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { dp[j] += dp[j - 1]; // 更新当前格子的路径数 } } return dp[n - 1]; }};

// 方法3: 记忆化递归class Solution {public: int uniquePaths(int m, int n) { vector<vector> memo(m + 1, vector(n + 1, 0)); // 记忆化数组 return dfs(m, n, memo); } int dfs(int i, int j, vector<vector>& memo) { if (i == 0 || j == 0) { return 0; // 边界条件 } if (i == 1 && j == 1) { return 1; // 起点 } if (memo[i][j] != 0) { return memo[i][j]; // 已经计算过了 } memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo); return memo[i][j]; }};

Java

class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; // 初始化第一行和第一列 for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int j = 0; j < n; j++) { dp[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; }}

Python

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j - 1] return dp[-1]

4、复杂度分析

动态规划：时间复杂度O(m×n)，空间复杂度O(m×n)
记忆化递归：时间复杂度O(m×n)，空间复杂度O(m×n)

Q92、最小路径和

1、题目描述

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]输出：12
提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 200

0 <= grid[i][j] <= 200

2、解题思路

动态规划方法

定义状态：dp[i][j]表示从(0,0)到(i,j)的最小路径和
状态转移方程 ：
- dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
初始化：
- dp[0][0] = grid[0][0]
- 第一行：只能从左向右移动
- 第一列：只能从上向下移动
结果：dp[m-1][n-1]

3、代码实现

C++

// 方法1: 动态规划 二维数组class Solution {public: int minPathSum(vector<vector>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector> dp(m, vector(n)); // 初始化起点 dp[0][0] = grid[0][0]; // 初始化第一列 for (int i = 1; i < m; ++i) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } // 初始化第一行 for (int j = 1; j < n; ++j) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } // 填充 dp 表 for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[m - 1][n - 1]; }};

// 方法2: 动态规划 一维数组class Solution {public: int minPathSum(vector<vector>& grid) { int m = grid.size(); int n = grid[0].size(); vector dp(n); // 初始化第一行 dp[0] = grid[0][0]; for (int j = 1; j < n; ++j) { dp[j] = dp[j - 1] + grid[0][j]; } // 逐行计算 for (int i = 1; i < m; ++i) { // 每行的第一个元素只能从上方来 dp[0] += grid[i][0]; for (int j = 1; j < n; ++j) { dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]; } } return dp[n - 1]; }};

Java

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

Python

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) dp = [0] * n # 初始化第一行 dp[0] = grid[0][0] for j in range(1, n): dp[j] = dp[j - 1] + grid[0][j] # 逐行计算 for i in range(1, m): # 每行的第一个元素只能从上方来 dp[0] += grid[i][0] for j in range(1, n): dp[j] = min(dp[j], dp[j - 1]) + grid[i][j] return dp[-1]

4、复杂度分析

时间复杂度：O(m×n)
空间复杂度：O(m×n)（可优化为O(n)）

Q93、最长回文子串

1、题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = \"babad\"输出：\"bab\"解释：\"aba\" 同样是符合题意的答案。
示例 2：
输入：s = \"cbbd\"输出：\"bb\"
提示：

1 <= s.length <= 1000

s 仅由数字和英文字母组成

2、解题思路

方法一：动态规划

定义状态：dp[i][j]表示s[i…j]是否为回文串
状态转移方程 ：
- dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
初始化：
- 单个字符都是回文串：dp[i][i] = true
- 两个相同字符构成回文串：dp[i][i+1] = (s[i] == s[i+1])
结果：记录最长的回文子串

方法二：中心扩展算法

中心思想：以每个字符为中心向两边扩展寻找回文串
两种情况：
- 奇数长度回文：以单个字符为中心
- 偶数长度回文：以两个相同字符为中心
结果：记录扩展过程中找到的最长回文串

3、代码实现

C++

// 方法1: 动态规划法class Solution {public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) { return s; } vector<vector> dp(n, vector(n, false)); int maxLen = 1, start = 0; // 单个字符都是回文 for (int i = 0; i < n; ++i) { dp[i][i] = true; } // 检查长度为 2 的字串 for (int i = 0; i < n - 1; ++i) { if (s[i] == s[i + 1]) { dp[i][i + 1] = true; start = i; maxLen = 2; } } // 检查长度大于 2 的子串 for (int len = 3; len <= n; ++len) { for (int i = 0; i  maxLen) { start = i; maxLen = len;  } } } } return s.substr(start, maxLen); }};

// 方法2: 中心扩展法class Solution {public: string longestPalindrome(string s) { if (s.empty()) { return \"\"; } int start = 0, maxLen = 1; int n = s.size(); for (int i = 0; i  maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substr(start, maxLen); }private: int expandAroundCenter(const string& s, int left, int right) { while (left >= 0 && right < s.size() && s[left] == s[right]) { left--; right++; } return right - left - 1; // 计算回文长度 }};

Java

class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) { return \"\"; } int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }}

Python

class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] max_len = 1 start = 0 # 单个字符都是回文 for i in range(n): dp[i][i] = True # 检查长度为2的子串 for i in range(n - 1): if s[i] == s[i + 1]: dp[i][i + 1] = True start = i max_len = 2 # 检查长度大于2的子串 for length in range(3, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j] and dp[i + 1][j - 1]:  dp[i][j] = True  if length > max_len: start = i max_len = length return s[start:start + max_len]

4、复杂度分析

动态规划：时间复杂度O(n²)，空间复杂度O(n²)
中心扩展：时间复杂度O(n²)，空间复杂度O(1)

Q94、最长公共子序列

1、题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，\"ace\" 是 \"abcde\" 的子序列，但 \"aec\" 不是 \"abcde\" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = \"abcde\", text2 = \"ace\" 输出：3 解释：最长公共子序列是 \"ace\" ，它的长度为 3 。

示例 2：

输入：text1 = \"abc\", text2 = \"abc\"输出：3解释：最长公共子序列是 \"abc\" ，它的长度为 3 。

示例 3：

输入：text1 = \"abc\", text2 = \"def\"输出：0解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

2、解题思路

动态规划方法

定义状态：dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度
状态转移方程 ：
- 当text1[i-1] == text2[j-1]时：dp[i][j] = dp[i-1][j-1] + 1
- 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化 ：
- dp[0][j] = 0（空字符串与任何字符串的LCS为0）
- dp[i][0] = 0（同上）
结果：dp[m][n]（m和n分别为text1和text2的长度）

3、代码实现

《LeetCode 热题 100》整整 100 题量大管饱题解套餐下

C++

// 方法1: 动态规划 二维数组class Solution {public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i - 1] == text2[j - 1]) {  dp[i][j] = dp[i - 1][j - 1] + 1; } else {  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }};

// 方法1: 动态规划 一维数组class Solution {public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); vector prev(n + 1, 0), curr(n + 1, 0); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (text1[i - 1] == text2[j - 1]) {  curr[j] = prev[j - 1] + 1; } else {  curr[j] = max(prev[j], curr[j - 1]); } } swap(prev, curr); } return prev[n]; }};

Java

class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(); int n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) {  dp[i][j] = dp[i - 1][j - 1] + 1; } else {  dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }}

Python

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) prev = [0] * (n + 1) for i in range(1, m + 1): curr = [0] * (n + 1) for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]:  curr[j] = prev[j - 1] + 1 else:  curr[j] = max(prev[j], curr[j - 1]) prev = curr return prev[n]

4、复杂度分析

时间复杂度：O(m×n)，其中m和n是两个字符串的长度
空间复杂度：O(m×n)（可优化为O(min(m,n))）

Q95、编辑距离

1、题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = \"horse\", word2 = \"ros\"输出：3解释：horse -> rorse (将 \'h\' 替换为 \'r\')rorse -> rose (删除 \'r\')rose -> ros (删除 \'e\')

示例 2：

输入：word1 = \"intention\", word2 = \"execution\"输出：5解释：intention -> inention (删除 \'t\')inention -> enention (将 \'i\' 替换为 \'e\')enention -> exention (将 \'n\' 替换为 \'x\')exention -> exection (将 \'n\' 替换为 \'c\')exection -> execution (插入 \'u\')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

2、解题思路

动态规划方法

定义状态：dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符所需的最小操作数
状态转移方程 ：
- 当 word1[i-1] == word2[j-1] 时：dp[i][j] = dp[i-1][j-1]（无需操作）
- 否则：dp[i][j] = min(
  dp[i][j-1] + 1, // 插入
  dp[i-1][j] + 1, // 删除
  dp[i-1][j-1] + 1 // 替换
  )
初始化 ：
- dp[i][0] = i（删除所有字符）
- dp[0][j] = j（插入所有字符）
结果：dp[m][n]（m和n分别为word1和word2的长度）

3、代码实现

《LeetCode 热题 100》整整 100 题量大管饱题解套餐下

C++

// 方法1: 动态规划 二维数组class Solution {public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector<vector> dp(m + 1, vector(n + 1, 0)); // 初始化: 空字符串转换 操作2: 删除一个字符 for (int i = 0; i <= m; ++i) { dp[i][0] = i; } for (int j = 0; j <= n; ++j) { dp[0][j] = j; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) {  dp[i][j] = dp[i - 1][j - 1]; } else {  dp[i][j] = 1 + min({  dp[i][j - 1], // 插入  dp[i - 1][j], // 删除  dp[i - 1][j - 1] // 替换 }); } } } return dp[m][n]; }};

// 方法2: 动态规划 一维数组class Solution {public: int minDistance(string word1, string word2) { int m = word1.size(); int n = word2.size(); vector prev(n + 1), curr(n + 1); // 初始化第一行 for (int j = 0; j <= n; ++j) { prev[j] = j; } for (int i = 1; i <= m; ++i) { curr[0] = i; // 初始化第一列 for (int j = 1; j <= n; ++j) { if (word1[i - 1] == word2[j - 1]) {  curr[j] = prev[j - 1]; } else {  curr[j] = 1 + min({ prev[j], // 删除 curr[j - 1], // 插入 prev[j - 1] // 替换 }); } } swap(prev, curr); } return prev[n]; }};

Java

class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m + 1][n + 1]; // 初始化 for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][j] = j; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) {  dp[i][j] = dp[i - 1][j - 1]; } else {  dp[i][j] = 1 + Math.min( dp[i - 1][j], // 删除 Math.min(  dp[i][j - 1], // 插入  dp[i - 1][j - 1] // 替换 )); } } } return dp[m][n]; }}

Python

class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) prev = [j for j in range(n + 1)] for i in range(1, m + 1): curr = [0] * (n + 1) curr[0] = i for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]:  curr[j] = prev[j - 1] else:  curr[j] = 1 + min( prev[j], # 删除 curr[j - 1], # 插入 prev[j - 1] # 替换  ) prev = curr return prev[n]

4、复杂度分析

时间复杂度：O(m×n)
空间复杂度：O(m×n)（可优化为O(min(m,n))）

17、技巧

Q96、只出现一次的数字

1、题目描述

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

**输出：**1

示例 2 ：

**输入：**nums = [4,1,2,1,2]

**输出：**4

示例 3 ：

**输入：**nums = [1]

**输出：**1

提示：

1 <= nums.length <= 3 * 104

-3 * 104 <= nums[i] <= 3 * 104

除了某个元素只出现一次以外，其余每个元素均出现两次。

2、解题思路

位运算方法（异或）

异或运算特性 ：
- a ^ a = 0
- a ^ 0 = a
- 异或运算满足交换律和结合律
核心思想 ：
- 将数组中所有元素进行异或运算
- 出现两次的数字会相互抵消变为0
- 最终结果就是只出现一次的数字

3、代码实现

C++

class Solution {public: int singleNumber(vector& nums) { int result = 0; // 遍历数组, 对所有元素进行异或运算 for (int num : nums) { result ^= num; } return result; }};

Java

class Solution { public int singleNumber(int[] nums) { int result = 0; for (int num : nums) { result ^= num; } return result; }}

Python

class Solution: def singleNumber(self, nums: List[int]) -> int: result = 0 for num in nums: result ^= num return result

4、复杂度分析

时间复杂度：O(n)，只需要遍历一次数组
空间复杂度：O(1)，只使用了常数个额外空间

Q97、多数元素

1、题目描述

给定一个大小为 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 * 104

-109 <= nums[i] <= 109

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

2、解题思路

哈希表统计法

思路：使用哈希表统计每个元素的出现次数，找到出现次数超过n/2的元素
复杂度：
- 时间复杂度：O(n)
- 空间复杂度：O(n)

排序法

思路：排序后，多数元素必定位于中间位置
复杂度：
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)或O(n)（取决于排序实现）

随机化法

思路：随机选取元素验证是否为多数元素
复杂度：
- 时间复杂度：平均O(n)，最坏O(∞)
- 空间复杂度：O(1)

摩尔投票法（最优解）

思路：利用多数元素数量超过一半的特点，通过计数方式找出候选元素
复杂度：
- 时间复杂度：O(n)
- 空间复杂度：O(1)

3、代码实现

C++

// 方法1: 哈希表法class Solution {public: int majorityElement(vector& nums) { unordered_map counts; for (int num : nums) { counts[num]++; if (counts[num] > nums.size() / 2) { return num; } } return -1; // 题目保证有解, 实际并不会执行到这里 }};

// 方法2: 排序法class Solution {public: int majorityElement(vector& nums) { sort(nums.begin(), nums.end()); return nums[nums.size() / 2]; }};

// 方法3: 摩尔投票法class Solution {public: int majorityElement(vector& nums) { int candidate = nums[0]; int count = 1; for (int i = 1; i < nums.size(); ++i) { if (count == 0) { candidate = nums[i]; count = 1; } else if (nums[i] == candidate) { count++; } else { count--; } } return candidate; }};

Java

class Solution { public int majorityElement(int[] nums) { int candidate = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (count == 0) { candidate = nums[i]; count = 1; } else if (nums[i] == candidate) { count++; } else { count--; } } return candidate; }}

Python

class Solution: def majorityElement(self, nums: List[int]) -> int: candidate = nums[0] count = 1 for num in nums[1:]: if count == 0: candidate = num count = 1 elif num == candidate: count += 1 else: count -= 1 return candidate

Q98、颜色分类

1、题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0]输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]输出：[0,1,2]
提示：

n == nums.length

1 <= n <= 300

nums[i] 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

2、解题思路

三指针/分区法（最优解）

初始化三个指针：
- left：指向最后一个0的右边位置（初始为-1）
- right：指向第一个2的左边位置（初始为n）
- i：当前遍历指针（初始为0）
遍历规则：
- 遇到0：与left的下一个位置交换，left和i都右移
- 遇到1：跳过，i右移
- 遇到2：与right的前一个位置交换，right左移（i不移动，因为交换来的元素需要检查）
终止条件：当i与right相遇

3、代码实现

C++

// 方法1: 双指针法class Solution {public: void sortColors(vector& nums) { int n = nums.size(); int left = -1; // 指向最后一个 0 的右边位置 int right = n; // 指向第一个 2 的右边位置 int i = 0; // 当前遍历指针 while (i < right) { if (nums[i] == 0) { // 将 0 交换到左侧区域 swap(nums[++left], nums[i++]); } else if (nums[i] == 1) { // 1 位于中间区域, 直接跳过 ++i; } else { // 将 2 交换到右侧区域 swap(nums[--right], nums[i]); // i 不增加, 因为交换来的元素需要重新检查 } } }};

// 方法2: 计数排序法 (两趟扫描)public: void sortColors(vector& nums) { int count[3] = {0}; for (int num : nums) { count[num]++; } int index = 0; for (int i = 0; i  0) { nums[index++] = i; } } }};

Java

class Solution { public void sortColors(int[] nums) { int left = -1; // 最后一个0的右边位置 int right = nums.length; // 第一个2的左边位置 int i = 0; // 当前指针 while (i < right) { if (nums[i] == 0) { swap(nums, ++left, i++); } else if (nums[i] == 1) { i++; } else { swap(nums, --right, i); } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}

Python

class Solution: def sortColors(self, nums: List[int]) -> None: \"\"\" Do not return anything, modify nums in-place instead. \"\"\" left, right = -1, len(nums) i = 0 while i < right: if nums[i] == 0: left += 1 nums[left], nums[i] = nums[i], nums[left] i += 1 elif nums[i] == 1: i += 1 else: right -= 1 nums[right], nums[i] = nums[i], nums[right]

4、复杂度分析

时间复杂度：O(n)，仅需一次遍历
空间复杂度：O(1)，仅使用常数个额外空间

Q99、下一个排列

1、题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须** 原地 **修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]输出：[1,5,1]
提示：

1 <= nums.length <= 100

0 <= nums[i] <= 100

2、解题思路

算法步骤

从后向前查找第一个下降点：
- 找到第一个满足nums[i] < nums[i+1]的索引i
- 如果找不到，说明数组是降序排列，直接反转整个数组
从后向前查找第一个大于nums[i]的元素：
- 找到第一个满足nums[j] > nums[i]的索引j
交换nums[i]和nums[j]：
- 交换这两个元素
反转i+1到末尾的部分：
- 将i+1到末尾的部分反转，使其变为升序

3、代码实现

C++

class Solution {public: void nextPermutation(vector& nums) { int n = nums.size(); // 1. 从后向前查找第一个下降点 int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { --i; } if (i >= 0) { // 2. 从后向前查找第一个大于 nums[i] 的元素 int j = n - 1; while (j >= 0 && nums[j] <= nums[i]) { --j; } // 3. 交换 nums[i] 和 nums[j] swap(nums[i], nums[j]); } // 4. 反转 i+1 到末尾的部分 reverse(nums.begin() + i + 1, nums.end()); }};

Java

class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; // 1. 查找第一个下降点 while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = nums.length - 1; // 2. 查找第一个大于nums[i]的元素 while (j >= 0 && nums[j] <= nums[i]) { j--; } // 3. 交换元素 swap(nums, i, j); } // 4. 反转i+1到末尾的部分 reverse(nums, i + 1); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private void reverse(int[] nums, int start) { int end = nums.length - 1; while (start < end) { swap(nums, start, end); start++; end--; } }}

Python

class Solution: def nextPermutation(self, nums: List[int]) -> None: \"\"\" Do not return anything, modify nums in-place instead. \"\"\" n = len(nums) # 1. 查找第一个下降点 i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: j = n - 1 # 2. 查找第一个大于nums[i]的元素 while j >= 0 and nums[j] <= nums[i]: j -= 1 # 3. 交换元素 nums[i], nums[j] = nums[j], nums[i] # 4. 反转i+1到末尾的部分 left, right = i + 1, n - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1

4、复杂度分析

时间复杂度：O(n)，最多扫描两次数组和一次部分反转
空间复杂度：O(1)，仅使用常数空间

Q100、寻找重复数

1、题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：
输入：nums = [1,3,4,2,2]输出：2
示例 2：
输入：nums = [3,1,3,4,2]输出：3
示例 3 :
输入：nums = [3,3,3,3,3]输出：3
提示：

1 <= n <= 105

nums.length == n + 1

1 <= nums[i] <= n

nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?

你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

2、解题思路

1. 二分查找法（最优解）

核心思想：利用鸽巢原理，在数值范围[1, n]内进行二分查找
步骤：
1. 初始化搜索范围 left=1, right=n
2. 计算中间值 mid
3. 统计数组中 ≤mid 的元素个数 cnt
4. 如果 cnt>mid，说明重复数在左半区，否则在右半区
5. 重复直到找到重复数

2. 快慢指针法（Floyd判圈算法）

核心思想：将数组视为链表，使用快慢指针找环的入口
步骤：
1. 初始化快慢指针为nums[0]
2. 快指针每次走两步，慢指针每次走一步
3. 当快慢指针相遇时，重置慢指针
4. 两个指针每次各走一步，再次相遇点即为重复数

3、代码实现

C++

// 方法1: 二分查找法class Solution {public: int findDuplicate(vector& nums) { int n = nums.size(); int left = 1, right = n - 1, res = -1; while (left <= right) { int mid = left + (right - left) / 2; int cnt = 0; // 统计小于 mid 的元素个数 for (int num : nums) { if (num <= mid) {  ++cnt; } } // 根据鸽巢原理判断重复数所在区间 if (cnt <= mid) { left = mid + 1; } else { right = mid - 1; res = mid; // 记录可能的结果 } } return res; }};

// 方法2: 快慢指针class Solution {public: int findDuplicate(vector& nums) { // 初始化快慢指针 int slow = nums[0], fast = nums[0]; // 第一阶段: 找到相遇点 do { slow = nums[slow]; // 走一步 fast = nums[nums[fast]]; // 走两步 } while (slow != fast); // 第二阶段: 找到环入口 (重复数) slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }};

Java

class Solution { public int findDuplicate(int[] nums) { int left = 1, right = nums.length - 1, res = -1; while (left <= right) { int mid = left + (right - left) / 2; int cnt = 0; for (int num : nums) { if (num <= mid) {  cnt++; } } if (cnt <= mid) { left = mid + 1; } else { right = mid - 1; res = mid; } } return res; }}

class Solution { public int findDuplicate(int[] nums) { int slow = nums[0], fast = nums[0]; // 找到相遇点 do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // 找到环入口 slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }}

Python

class Solution: def findDuplicate(self, nums: List[int]) -> int: left, right = 1, len(nums) - 1 res = -1 while left <= right: mid = (left + right) // 2 cnt = sum(1 for num in nums if num <= mid) if cnt <= mid: left = mid + 1 else: right = mid - 1 res = mid return res

4、复杂度分析

二分查找法：
- 时间复杂度：O(nlogn)，每次二分需要遍历整个数组
- 空间复杂度：O(1)
快慢指针法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)

《LeetCode 热题 100》整整 100 题量大管饱题解套餐 下

Q67、寻找旋转排序数组中的最小值

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q68、寻找两个正序数组的中位数

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

12、栈

Q69、有效的括号

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q70、最小栈

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q71、字符串解码

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q72、每日温度

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q73、柱状图中最大的矩形

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

13、堆

Q74、数组中的第K个最大元素

1、题目描述

2、解题思路

3、代码实现

C++

4、复杂度分析

Q75、前 K 个高频元素

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q76、数据流的中位数

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

《LeetCode 热题 100》整整 100 题量大管饱题解套餐下