网吧装修设计公司_徐州网架加工_可以发布推广引流的悬赏平台_深圳网络推广培训中心

Leetcode: 0071-0080题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

71. 简化路径

题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

• 一个点 '.' 表示当前目录本身。
• 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
• 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
• 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

 

示例 1：

输出："/home"

解释：

应删除尾随斜杠。

示例 2：

输出："/home/foo"

解释：

多个连续的斜杠被单个斜杠替换。

示例 3：

输出："/home/user/Pictures"

解释：

两个点 ".." 表示上一级目录（父目录）。

示例 4：

输出："/"

解释：

不可能从根目录上升一级目录。

示例 5：

输出："/.../b/d"

解释：

"..." 在这个问题中是一个合法的目录名。

 

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，'.'，'/' 或 '_' 组成。
• path 是一个有效的 Unix 风格绝对路径。

难度：中等

标签：栈,字符串

解法

方法一：栈

我们先将路径按照 '/' 分割成若干个子串，然后遍历每个子串，根据子串的内容进行如下操作：

• 若子串为空，或者为 '.'，则不做任何操作，因为 '.' 表示当前目录；
• 若子串为 '..'，则需要将栈顶元素弹出，因为 '..' 表示上一级目录；
• 若子串为其他字符串，则将该子串入栈，因为该子串表示当前目录的子目录。

最后，我们将栈中的所有元素按照从栈底到栈顶的顺序拼接成字符串，即为简化后的规范路径。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为路径的长度。

Python3

class Solution:def simplifyPath(self, path: str) -> str:stk = []for s in path.split('/'):if not s or s == '.':continueif s == '..':if stk:stk.pop()else:stk.append(s)return '/' + '/'.join(stk)

Java

class Solution {public String simplifyPath(String path) {Deque<String> stk = new ArrayDeque<>();for (String s : path.split("/")) {if ("".equals(s) || ".".equals(s)) {continue;}if ("..".equals(s)) {stk.pollLast();} else {stk.offerLast(s);}}return "/" + String.join("/", stk);}
}

C++

class Solution {
public:string simplifyPath(string path) {deque<string> stk;stringstream ss(path);string t;while (getline(ss, t, '/')) {if (t == "" || t == ".") {continue;}if (t == "..") {if (!stk.empty()) {stk.pop_back();}} else {stk.push_back(t);}}if (stk.empty()) {return "/";}string ans;for (auto& s : stk) {ans += "/" + s;}return ans;}
};

---

72. 编辑距离

题目描述

给你两个单词 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 由小写英文字母组成

难度：中等

标签：字符串,动态规划

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示将 $word1$ 的前 $i$ 个字符转换成 $word2$ 的前 $j$ 个字符所使用的最少操作数。初始时 $f[i][0]=i$, $f[0][j]=j$。其中 $i\in [1,m],j\in [0,n]$。

考虑 $f[i][j]$：

• 如果 $word1[i-1]=word2[j-1]$，那么我们只需要考虑将 $word1$ 的前 $i-1$ 个字符转换成 $word2$ 的前 $j-1$ 个字符所使用的最少操作数，因此 $f[i][j]=f[i-1][j-1]$；
• 否则，我们可以考虑插入、删除、替换操作，那么 $f[i][j]=\min (f[i-1][j],f[i][j-1],f[i-1][j-1])+1$。

综上，我们可以得到状态转移方程：

$$f[i][j]=\{\begin{array}{ll}i,& \text{if }j=0\\ j,& \text{if }i=0\\ f[i-1][j-1],& \text{if }word1[i-1]=word2[j-1]\\ \min (f[i-1][j],f[i][j-1],f[i-1][j-1])+1,& \text{otherwise}\end{array}$$

最后，我们返回 $f[m][n]$ 即可。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是 $word1$ 和 $word2$ 的长度。

Python3

class Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)f = [[0] * (n + 1) for _ in range(m + 1)]for j in range(1, n + 1):f[0][j] = jfor i, a in enumerate(word1, 1):f[i][0] = ifor j, b in enumerate(word2, 1):if a == b:f[i][j] = f[i - 1][j - 1]else:f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1return f[m][n]

Java

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] f = new int[m + 1][n + 1];for (int j = 1; j <= n; ++j) {f[0][j] = j;}for (int i = 1; i <= m; ++i) {f[i][0] = i;for (int j = 1; j <= n; ++j) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {f[i][j] = f[i - 1][j - 1];} else {f[i][j] = Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;}}}return f[m][n];}
}

C++

class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();int f[m + 1][n + 1];for (int j = 0; j <= n; ++j) {f[0][j] = j;}for (int i = 1; i <= m; ++i) {f[i][0] = i;for (int j = 1; j <= n; ++j) {if (word1[i - 1] == word2[j - 1]) {f[i][j] = f[i - 1][j - 1];} else {f[i][j] = min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;}}}return f[m][n];}
};

---

73. 矩阵置零

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

 

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

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

 

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

 

进阶：

• 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

难度：中等

标签：数组,哈希表,矩阵

解法

方法一：数组标记

我们分别用数组 rows 和 cols 标记待清零的行和列。

然后再遍历一遍矩阵，将 rows 和 cols 中标记的行和列对应的元素清零。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

Python3

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:m, n = len(matrix), len(matrix[0])rows = [0] * mcols = [0] * nfor i, row in enumerate(matrix):for j, v in enumerate(row):if v == 0:rows[i] = cols[j] = 1for i in range(m):for j in range(n):if rows[i] or cols[j]:matrix[i][j] = 0

Java

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean[] rows = new boolean[m];boolean[] cols = new boolean[n];for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (matrix[i][j] == 0) {rows[i] = true;cols[j] = true;}}}for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (rows[i] || cols[j]) {matrix[i][j] = 0;}}}}
}

C++

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<bool> rows(m);vector<bool> cols(n);for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (!matrix[i][j]) {rows[i] = 1;cols[j] = 1;}}}for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (rows[i] || cols[j]) {matrix[i][j] = 0;}}}}
};

---

74. 搜索二维矩阵

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

 

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

难度：中等

标签：数组,二分查找,矩阵

解法

方法一：二分查找

我们将二维矩阵逻辑展开，然后二分查找即可。

时间复杂度 $O(\log (m\times n))$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$。

Python3

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:m, n = len(matrix), len(matrix[0])left, right = 0, m * n - 1while left < right:mid = (left + right) >> 1x, y = divmod(mid, n)if matrix[x][y] >= target:right = midelse:left = mid + 1return matrix[left // n][left % n] == target

Java

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int left = 0, right = m * n - 1;while (left < right) {int mid = (left + right) >> 1;int x = mid / n, y = mid % n;if (matrix[x][y] >= target) {right = mid;} else {left = mid + 1;}}return matrix[left / n][left % n] == target;}
}

C++

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int left = 0, right = m * n - 1;while (left < right) {int mid = left + right >> 1;int x = mid / n, y = mid % n;if (matrix[x][y] >= target) {right = mid;} else {left = mid + 1;}}return matrix[left / n][left % n] == target;}
};

---

75. 颜色分类

题目描述

给定一个包含红色、白色和蓝色、共 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

 

进阶：

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

难度：中等

标签：数组,双指针,排序

解法

方法一：三指针

我们定义三个指针 $i$, $j$ 和 $k$，其中指针 $i$ 用于指向数组中元素值为 $0$ 的最右边界，指针 $j$ 用于指向数组中元素值为 $2$ 的最左边界，初始时 $i=-1$, $j=n$。指针 $k$ 用于指向当前遍历的元素，初始时 $k=0$。

当 $k<j$ 时，我们执行如下操作：

• 若 $nums[k]=0$，则将其与 $nums[i+1]$ 交换，然后 $i$ 和 $k$ 都加 $1$；
• 若 $nums[k]=2$，则将其与 $nums[j-1]$ 交换，然后 $j$ 减 $1$；
• 若 $nums[k]=1$，则 $k$ 加 $1$。

遍历结束后，数组中的元素就被分成了 $[0,i]$, $[i+1,j-1]$ 和 $[j,n-1]$ 三个部分。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。只需要遍历一遍数组即可。空间复杂度 $O(1)$。

Python3

class Solution:def sortColors(self, nums: List[int]) -> None:i, j, k = -1, len(nums), 0while k < j:if nums[k] == 0:i += 1nums[i], nums[k] = nums[k], nums[i]k += 1elif nums[k] == 2:j -= 1nums[j], nums[k] = nums[k], nums[j]else:k += 1

Java

class Solution {public void sortColors(int[] nums) {int i = -1, j = nums.length, k = 0;while (k < j) {if (nums[k] == 0) {swap(nums, ++i, k++);} else if (nums[k] == 2) {swap(nums, --j, k);} else {++k;}}}private void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

C++

class Solution {
public:void sortColors(vector<int>& nums) {int i = -1, j = nums.size(), k = 0;while (k < j) {if (nums[k] == 0) {swap(nums[++i], nums[k++]);} else if (nums[k] == 2) {swap(nums[--j], nums[k]);} else {++k;}}}
};

---

76. 最小覆盖子串

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

 

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

 

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

 

提示：

• ^{m == s.length}
• ^{n == t.length}
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

 

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

难度：困难

标签：哈希表,字符串,滑动窗口

解法

方法一：计数 + 双指针

我们用一个哈希表或数组 $need$ 统计字符串 $t$ 中每个字符出现的次数，用另一个哈希表或数组 $window$ 统计滑动窗口中每个字符出现的次数。另外，定义两个指针 $j$ 和 $i$ 分别指向窗口的左右边界，变量 $cnt$ 表示窗口中已经包含了 $t$ 中的多少个字符，变量 $k$ 和 $mi$ 分别表示最小覆盖子串的起始位置和长度。

我们从左到右遍历字符串 $s$，对于当前遍历到的字符 $s[i]$：

我们将其加入窗口中，即 $window[s[i]]=window[s[i]]+1$，如果此时 $need[s[i]]\ge window[s[i]]$，则说明 $s[i]$ 是一个「必要的字符」，我们将 $cnt$ 加一。如果 $cnt$ 等于 $t$ 的长度，说明此时窗口中已经包含了 $t$ 中的所有字符，我们就可以尝试更新最小覆盖子串的起始位置和长度了。如果 $i-j+1<mi$，说明当前窗口表示的子串更短，我们就更新 $mi=i-j+1$ 和 $k=j$。然后，我们尝试移动左边界 $j$，如果此时 $need[s[j]]\ge window[s[j]]$，则说明 $s[j]$ 是一个「必要的字符」，移动左边界时会把 $s[j]$ 这个字符从窗口中移除，因此我们需要将 $cnt$ 减一，然后更新 $window[s[j]]=window[s[j]]-1$，并将 $j$ 右移一位。如果 $cnt$ 与 $t$ 的长度不相等，说明此时窗口中还没有包含 $t$ 中的所有字符，我们就不需要移动左边界了，直接将 $i$ 右移一位，继续遍历即可。

遍历结束，如果没有找到最小覆盖子串，返回空字符串，否则返回 $s[k:k+mi]$ 即可。

时间复杂度 $O(m+n)$，空间复杂度 $O(C)$。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度；而 $C$ 是字符集的大小，本题中 $C=128$。

Python3

class Solution:def minWindow(self, s: str, t: str) -> str:need = Counter(t)window = Counter()cnt, j, k, mi = 0, 0, -1, inffor i, c in enumerate(s):window[c] += 1if need[c] >= window[c]:cnt += 1while cnt == len(t):if i - j + 1 < mi:mi = i - j + 1k = jif need[s[j]] >= window[s[j]]:cnt -= 1window[s[j]] -= 1j += 1return '' if k < 0 else s[k : k + mi]

Java

class Solution {public String minWindow(String s, String t) {int[] need = new int[128];int[] window = new int[128];int m = s.length(), n = t.length();for (int i = 0; i < n; ++i) {++need[t.charAt(i)];}int cnt = 0, j = 0, k = -1, mi = 1 << 30;for (int i = 0; i < m; ++i) {++window[s.charAt(i)];if (need[s.charAt(i)] >= window[s.charAt(i)]) {++cnt;}while (cnt == n) {if (i - j + 1 < mi) {mi = i - j + 1;k = j;}if (need[s.charAt(j)] >= window[s.charAt(j)]) {--cnt;}--window[s.charAt(j++)];}}return k < 0 ? "" : s.substring(k, k + mi);}
}

C++

class Solution {
public:string minWindow(string s, string t) {int need[128]{};int window[128]{};int m = s.size(), n = t.size();for (char& c : t) {++need[c];}int cnt = 0, j = 0, k = -1, mi = 1 << 30;for (int i = 0; i < m; ++i) {++window[s[i]];if (need[s[i]] >= window[s[i]]) {++cnt;}while (cnt == n) {if (i - j + 1 < mi) {mi = i - j + 1;k = j;}if (need[s[j]] >= window[s[j]]) {--cnt;}--window[s[j++]];}}return k < 0 ? "" : s.substr(k, mi);}
};

---

77. 组合

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

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

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

难度：中等

标签：回溯

解法

方法一：回溯（两种方式）

我们设计一个函数 $dfs(i)$，表示从数字 $i$ 开始搜索，当前搜索路径为 $t$，答案为 $ans$。

函数 $dfs(i)$ 的执行逻辑如下：

• 如果当前搜索路径 $t$ 的长度等于 $k$，则将当前搜索路径加入答案，然后返回。
• 如果 $i>n$，则说明搜索已经结束，返回。
• 否则，我们可以选择将数字 $i$ 加入搜索路径 $t$，然后继续搜索，即执行 $dfs(i+1)$，然后将数字 $i$ 从搜索路径 $t$ 中移除；或者不将数字 $i$ 加入搜索路径 $t$，直接执行 $dfs(i+1)$。

以上做法实际上是枚举当前数字选或者不选，然后递归地搜索下一个数字。我们也可以枚举下一个要选择的数字 $j$，其中 $i\le j\le n$，如果下一个要选择的数字是 $j$，那么我们将数字 $j$ 加入搜索路径 $t$，然后继续搜索，即执行 $dfs(j+1)$，接着将数字 $j$ 从搜索路径 $t$ 中移除。

在主函数中，我们从数字 $1$ 开始搜索，即执行 $dfs(1)$。

时间复杂度 $(C_n^k\times k)$，空间复杂度 $O(k)$。其中 $C_n^k$ 表示组合数。

相似题目：

• 39. 组合总和
• 40. 组合总和 II
• 216. 组合总和 III

Python3

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:def dfs(i: int):if len(t) == k:ans.append(t[:])returnif i > n:returnt.append(i)dfs(i + 1)t.pop()dfs(i + 1)ans = []t = []dfs(1)return ans

Java

class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> t = new ArrayList<>();private int n;private int k;public List<List<Integer>> combine(int n, int k) {this.n = n;this.k = k;dfs(1);return ans;}private void dfs(int i) {if (t.size() == k) {ans.add(new ArrayList<>(t));return;}if (i > n) {return;}t.add(i);dfs(i + 1);t.remove(t.size() - 1);dfs(i + 1);}
}

C++

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;vector<int> t;function<void(int)> dfs = [&](int i) {if (t.size() == k) {ans.emplace_back(t);return;}if (i > n) {return;}t.emplace_back(i);dfs(i + 1);t.pop_back();dfs(i + 1);};dfs(1);return ans;}
};

---

78. 子集

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

 

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

难度：中等

标签：位运算,数组,回溯

解法

方法一：DFS(回溯)

我们设计一个函数 $dfs(i)$，表示从数组的第 $i$ 个元素开始搜索所有子集。函数 $dfs(i)$ 的执行逻辑如下：

• 如果 $i=n$，表示当前已经搜索结束，将当前得到的子集 $t$ 加入答案数组 $ans$ 中，然后返回；
• 否则，我们可以选择不选择当前元素，直接执行 $dfs(i+1)$；也可以选择当前元素，即把当前元素 $nums[i]$ 加入子集 $t$，然后执行 $dfs(i+1)$，注意要在执行 $dfs(i+1)$ 以后再将 $nums[i]$ 从子集 $t$ 中移除（回溯）。

在主函数中，我们调用 $dfs(0)$，即从数组的第一个元素开始搜索所有子集。最后返回答案数组 $ans$ 即可。

时间复杂度 $O(n\times 2^n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。一共有 $2^n$ 个子集，每个子集需要 $O(n)$ 的时间来构造。

Python3

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:def dfs(i: int):if i == len(nums):ans.append(t[:])returndfs(i + 1)t.append(nums[i])dfs(i + 1)t.pop()ans = []t = []dfs(0)return ans

Java

class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> t = new ArrayList<>();private int[] nums;public List<List<Integer>> subsets(int[] nums) {this.nums = nums;dfs(0);return ans;}private void dfs(int i) {if (i == nums.length) {ans.add(new ArrayList<>(t));return;}dfs(i + 1);t.add(nums[i]);dfs(i + 1);t.remove(t.size() - 1);}
}

C++

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> t;function<void(int)> dfs = [&](int i) -> void {if (i == nums.size()) {ans.push_back(t);return;}dfs(i + 1);t.push_back(nums[i]);dfs(i + 1);t.pop_back();};dfs(0);return ans;}
};

---

79. 单词搜索

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

示例 3：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

难度：中等

标签：数组,字符串,回溯,矩阵

解法

方法一：DFS(回溯)

我们可以枚举网格的每一个位置 $(i,j)$ 作为搜索的起点，然后从起点开始进行深度优先搜索，如果可以搜索到单词的末尾，就说明单词存在，否则说明单词不存在。

因此，我们设计一个函数 $dfs(i,j,k)$，表示从网格的 $(i,j)$ 位置出发，且从单词的第 $k$ 个字符开始搜索，是否能够搜索成功。函数 $dfs(i,j,k)$ 的执行步骤如下：

• 如果 $k=|word|-1$，说明已经搜索到单词的最后一个字符，此时只需要判断网格 $(i,j)$ 位置的字符是否等于 $word[k]$，如果相等则说明单词存在，否则说明单词不存在。无论单词是否存在，都无需继续往下搜索，因此直接返回结果。
• 否则，如果 $word[k]$ 字符不等于网格 $(i,j)$ 位置的字符，说明本次搜索失败，直接返回 false。
• 否则，我们将网格 $(i,j)$ 位置的字符暂存于 $c$ 中，然后将此位置的字符修改为一个特殊字符 '0'，代表此位置的字符已经被使用过，防止之后搜索时重复使用。然后我们从 $(i,j)$ 位置的上、下、左、右四个方向分别出发，去搜索网格中第 $k+1$ 个字符，如果四个方向有任何一个方向搜索成功，就说明搜索成功，否则说明搜索失败，此时我们需要还原网格 $(i,j)$ 位置的字符，即把 $c$ 放回网格 $(i,j)$ 位置（回溯）。

在主函数中，我们枚举网格中的每一个位置 $(i,j)$ 作为起点，如果调用 $dfs(i,j,0)$ 返回 true，就说明单词存在，否则说明单词不存在，返回 false。

时间复杂度 $O(m\times n\times 3^k)$，空间复杂度 $O(\min (m\times n,k))$。其中 $m$ 和 $n$ 分别是网格的行数和列数；而 $k$ 是字符串 $word$ 的长度。

Python3

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def dfs(i: int, j: int, k: int) -> bool:if k == len(word) - 1:return board[i][j] == word[k]if board[i][j] != word[k]:return Falsec = board[i][j]board[i][j] = "0"for a, b in pairwise((-1, 0, 1, 0, -1)):x, y = i + a, j + bok = 0 <= x < m and 0 <= y < n and board[x][y] != "0"if ok and dfs(x, y, k + 1):return Trueboard[i][j] = creturn Falsem, n = len(board), len(board[0])return any(dfs(i, j, 0) for i in range(m) for j in range(n))

Java

class Solution {private int m;private int n;private String word;private char[][] board;public boolean exist(char[][] board, String word) {m = board.length;n = board[0].length;this.word = word;this.board = board;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (dfs(i, j, 0)) {return true;}}}return false;}private boolean dfs(int i, int j, int k) {if (k == word.length() - 1) {return board[i][j] == word.charAt(k);}if (board[i][j] != word.charAt(k)) {return false;}char c = board[i][j];board[i][j] = '0';int[] dirs = {-1, 0, 1, 0, -1};for (int u = 0; u < 4; ++u) {int x = i + dirs[u], y = j + dirs[u + 1];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' && dfs(x, y, k + 1)) {return true;}}board[i][j] = c;return false;}
}

C++

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {int m = board.size(), n = board[0].size();int dirs[5] = {-1, 0, 1, 0, -1};function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool {if (k == word.size() - 1) {return board[i][j] == word[k];}if (board[i][j] != word[k]) {return false;}char c = board[i][j];board[i][j] = '0';for (int u = 0; u < 4; ++u) {int x = i + dirs[u], y = j + dirs[u + 1];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '0' && dfs(x, y, k + 1)) {return true;}}board[i][j] = c;return false;};for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (dfs(i, j, 0)) {return true;}}}return false;}
};

---

80. 删除有序数组中的重复项 II

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

 

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

 

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

 

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

难度：中等

标签：数组,双指针

解法

方法一：一次遍历

我们用一个变量 $k$ 记录当前已经处理好的数组的长度，初始时 $k=0$，表示空数组。

然后我们从左到右遍历数组，对于遍历到的每个元素 $x$，如果 $k<2$ 或者 $x\ne nums[k-2]$，我们就将 $x$ 放到 $nums[k]$ 的位置，然后 $k$ 自增 $1$。否则，$x$ 与 $nums[k-2]$ 相同，我们直接跳过这个元素。继续遍历，直到遍历完整个数组。

这样，当遍历结束时，$nums$ 中前 $k$ 个元素就是我们要求的答案，且 $k$ 就是答案的长度。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

补充：

原问题要求最多相同的数字最多出现 $2$ 次，我们可以扩展至相同的数字最多保留 $k$ 个。

• 由于相同的数字最多保留 $k$ 个，那么原数组的前 $k$ 个元素我们可以直接保留；
• 对于后面的数字，能够保留的前提是：当前数字 $x$ 与前面已保留的数字的倒数第 $k$ 个元素比较，不同则保留，相同则跳过。

相似题目：

• 26. 删除有序数组中的重复项

Python3

class Solution:def removeDuplicates(self, nums: List[int]) -> int:k = 0for x in nums:if k < 2 or x != nums[k - 2]:nums[k] = xk += 1return k

Java

class Solution {public int removeDuplicates(int[] nums) {int k = 0;for (int x : nums) {if (k < 2 || x != nums[k - 2]) {nums[k++] = x;}}return k;}
}

C++

class Solution {
public:int removeDuplicates(vector<int>& nums) {int k = 0;for (int x : nums) {if (k < 2 || x != nums[k - 2]) {nums[k++] = x;}}return k;}
};

---