Leetcode: 0071-0080题速览
Leetcode: 0071-0080题速览
研一在读备战就业,制此集合便于空闲时间浏览,有任何疑惑问题欢迎讨论,共同进步
目录
- Leetcode: 0071-0080题速览
- [71. 简化路径](https://leetcode.cn/problems/simplify-path)
- [72. 编辑距离](https://leetcode.cn/problems/edit-distance)
- [73. 矩阵置零](https://leetcode.cn/problems/set-matrix-zeroes)
- [74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix)
- [75. 颜色分类](https://leetcode.cn/problems/sort-colors)
- [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring)
- [77. 组合](https://leetcode.cn/problems/combinations)
- [78. 子集](https://leetcode.cn/problems/subsets)
- [79. 单词搜索](https://leetcode.cn/problems/word-search)
- [80. 删除有序数组中的重复项 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii)
71. 简化路径
题目描述
给你一个字符串 path
,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/'
开头),请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下:
- 一个点
'.'
表示当前目录本身。 - 此外,两个点
'..'
表示将目录切换到上一级(指向父目录)。 - 任意多个连续的斜杠(即,
'//'
或'///'
)都被视为单个斜杠'/'
。 - 任何其他格式的点(例如,
'...'
或'....'
)均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式:
- 始终以斜杠
'/'
开头。 - 两个目录名之间必须只有一个斜杠
'/'
。 - 最后一个目录名(如果存在)不能 以
'/'
结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含
'.'
或'..'
)。
返回简化后得到的 规范路径 。
示例 1:
输入:path = "/home/"
输出:"/home"
解释:
应删除尾随斜杠。
示例 2:
输入:path = "/home//foo/"
输出:"/home/foo"
解释:
多个连续的斜杠被单个斜杠替换。
示例 3:
输入:path = "/home/user/Documents/../Pictures"
输出:"/home/user/Pictures"
解释:
两个点 ".."
表示上一级目录(父目录)。
示例 4:
输入:path = "/../"
输出:"/"
解释:
不可能从根目录上升一级目录。
示例 5:
输入:path = "/.../a/../b/c/../d/./"
输出:"/.../b/d"
解释:
"..."
在这个问题中是一个合法的目录名。
提示:
1 <= path.length <= 3000
path
由英文字母,数字,'.'
,'/'
或'_'
组成。path
是一个有效的 Unix 风格绝对路径。
难度:中等
标签:栈,字符串
解法
方法一:栈
我们先将路径按照 '/'
分割成若干个子串,然后遍历每个子串,根据子串的内容进行如下操作:
- 若子串为空,或者为
'.'
,则不做任何操作,因为'.'
表示当前目录; - 若子串为
'..'
,则需要将栈顶元素弹出,因为'..'
表示上一级目录; - 若子串为其他字符串,则将该子串入栈,因为该子串表示当前目录的子目录。
最后,我们将栈中的所有元素按照从栈底到栈顶的顺序拼接成字符串,即为简化后的规范路径。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为路径的长度。
Python3
class Solution:
def simplifyPath(self, path: str) -> str:
stk = []
for s in path.split('/'):
if not s or s == '.':
continue
if 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 ] f[i][j] f[i][j] 表示将 w o r d 1 word1 word1 的前 i i i 个字符转换成 w o r d 2 word2 word2 的前 j j j 个字符所使用的最少操作数。初始时 f [ i ] [ 0 ] = i f[i][0] = i f[i][0]=i, f [ 0 ] [ j ] = j f[0][j] = j f[0][j]=j。其中 i ∈ [ 1 , m ] , j ∈ [ 0 , n ] i \in [1, m], j \in [0, n] i∈[1,m],j∈[0,n]。
考虑 f [ i ] [ j ] f[i][j] f[i][j]:
- 如果 w o r d 1 [ i − 1 ] = w o r d 2 [ j − 1 ] word1[i - 1] = word2[j - 1] word1[i−1]=word2[j−1],那么我们只需要考虑将 w o r d 1 word1 word1 的前 i − 1 i - 1 i−1 个字符转换成 w o r d 2 word2 word2 的前 j − 1 j - 1 j−1 个字符所使用的最少操作数,因此 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j] = f[i - 1][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] = \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1 f[i][j]=min(f[i−1][j],f[i][j−1],f[i−1][j−1])+1。
综上,我们可以得到状态转移方程:
f [ i ] [ j ] = { i , if j = 0 j , if i = 0 f [ i − 1 ] [ j − 1 ] , if w o r d 1 [ i − 1 ] = w o r d 2 [ j − 1 ] min ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] , f [ i − 1 ] [ j − 1 ] ) + 1 , otherwise f[i][j] = \begin{cases} i, & \textit{if } j = 0 \\ j, & \textit{if } i = 0 \\ f[i - 1][j - 1], & \textit{if } word1[i - 1] = word2[j - 1] \\ \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1, & \textit{otherwise} \end{cases} f[i][j]=⎩ ⎨ ⎧i,j,f[i−1][j−1],min(f[i−1][j],f[i][j−1],f[i−1][j−1])+1,if j=0if i=0if word1[i−1]=word2[j−1]otherwise
最后,我们返回 f [ m ] [ n ] f[m][n] f[m][n] 即可。
时间复杂度 O ( m × n ) O(m \times n) O(m×n),空间复杂度 O ( m × n ) O(m \times n) O(m×n)。其中 m m m 和 n n n 分别是 w o r d 1 word1 word1 和 w o r d 2 word2 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] = j
for i, a in enumerate(word1, 1):
f[i][0] = i
for 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]) + 1
return 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 × n ) O(m\times n) O(m×n),空间复杂度 O ( m + n ) O(m+n) O(m+n)。其中 m m m 和 n n n 分别为矩阵的行数和列数。
Python3
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
rows = [0] * m
cols = [0] * n
for i, row in enumerate(matrix):
for j, v in enumerate(row):
if v == 0:
rows[i] = cols[j] = 1
for 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 × n ) ) O(\log (m \times n)) O(log(m×n))。其中 m m m 和 n n n 分别是矩阵的行数和列数。空间复杂度 O ( 1 ) O(1) 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 - 1
while left < right:
mid = (left + right) >> 1
x, y = divmod(mid, n)
if matrix[x][y] >= target:
right = mid
else:
left = mid + 1
return 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 i i, j j j 和 k k k,其中指针 i i i 用于指向数组中元素值为 0 0 0 的最右边界,指针 j j j 用于指向数组中元素值为 2 2 2 的最左边界,初始时 i = − 1 i=-1 i=−1, j = n j=n j=n。指针 k k k 用于指向当前遍历的元素,初始时 k = 0 k=0 k=0。
当 k < j k \lt j k<j 时,我们执行如下操作:
- 若 n u m s [ k ] = 0 nums[k]=0 nums[k]=0,则将其与 n u m s [ i + 1 ] nums[i+1] nums[i+1] 交换,然后 i i i 和 k k k 都加 1 1 1;
- 若 n u m s [ k ] = 2 nums[k]=2 nums[k]=2,则将其与 n u m s [ j − 1 ] nums[j-1] nums[j−1] 交换,然后 j j j 减 1 1 1;
- 若 n u m s [ k ] = 1 nums[k]=1 nums[k]=1,则 k k k 加 1 1 1。
遍历结束后,数组中的元素就被分成了 [ 0 , i ] [0,i] [0,i], [ i + 1 , j − 1 ] [i+1,j-1] [i+1,j−1] 和 [ j , n − 1 ] [j,n-1] [j,n−1] 三个部分。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 是数组的长度。只需要遍历一遍数组即可。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def sortColors(self, nums: List[int]) -> None:
i, j, k = -1, len(nums), 0
while k < j:
if nums[k] == 0:
i += 1
nums[i], nums[k] = nums[k], nums[i]
k += 1
elif nums[k] == 2:
j -= 1
nums[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)
时间内解决此问题的算法吗?
难度:困难
标签:哈希表,字符串,滑动窗口
解法
方法一:计数 + 双指针
我们用一个哈希表或数组 n e e d need need 统计字符串 t t t 中每个字符出现的次数,用另一个哈希表或数组 w i n d o w window window 统计滑动窗口中每个字符出现的次数。另外,定义两个指针 j j j 和 i i i 分别指向窗口的左右边界,变量 c n t cnt cnt 表示窗口中已经包含了 t t t 中的多少个字符,变量 k k k 和 m i mi mi 分别表示最小覆盖子串的起始位置和长度。
我们从左到右遍历字符串 s s s,对于当前遍历到的字符 s [ i ] s[i] s[i]:
我们将其加入窗口中,即 w i n d o w [ s [ i ] ] = w i n d o w [ s [ i ] ] + 1 window[s[i]] = window[s[i]] + 1 window[s[i]]=window[s[i]]+1,如果此时 n e e d [ s [ i ] ] ≥ w i n d o w [ s [ i ] ] need[s[i]] \geq window[s[i]] need[s[i]]≥window[s[i]],则说明 s [ i ] s[i] s[i] 是一个「必要的字符」,我们将 c n t cnt cnt 加一。如果 c n t cnt cnt 等于 t t t 的长度,说明此时窗口中已经包含了 t t t 中的所有字符,我们就可以尝试更新最小覆盖子串的起始位置和长度了。如果 i − j + 1 < m i i - j + 1 \lt mi i−j+1<mi,说明当前窗口表示的子串更短,我们就更新 m i = i − j + 1 mi = i - j + 1 mi=i−j+1 和 k = j k = j k=j。然后,我们尝试移动左边界 j j j,如果此时 n e e d [ s [ j ] ] ≥ w i n d o w [ s [ j ] ] need[s[j]] \geq window[s[j]] need[s[j]]≥window[s[j]],则说明 s [ j ] s[j] s[j] 是一个「必要的字符」,移动左边界时会把 s [ j ] s[j] s[j] 这个字符从窗口中移除,因此我们需要将 c n t cnt cnt 减一,然后更新 w i n d o w [ s [ j ] ] = w i n d o w [ s [ j ] ] − 1 window[s[j]] = window[s[j]] - 1 window[s[j]]=window[s[j]]−1,并将 j j j 右移一位。如果 c n t cnt cnt 与 t t t 的长度不相等,说明此时窗口中还没有包含 t t t 中的所有字符,我们就不需要移动左边界了,直接将 i i i 右移一位,继续遍历即可。
遍历结束,如果没有找到最小覆盖子串,返回空字符串,否则返回 s [ k : k + m i ] s[k:k+mi] s[k:k+mi] 即可。
时间复杂度 O ( m + n ) O(m + n) O(m+n),空间复杂度 O ( C ) O(C) O(C)。其中 m m m 和 n n n 分别是字符串 s s s 和 t t t 的长度;而 C C C 是字符集的大小,本题中 C = 128 C = 128 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, inf
for i, c in enumerate(s):
window[c] += 1
if need[c] >= window[c]:
cnt += 1
while cnt == len(t):
if i - j + 1 < mi:
mi = i - j + 1
k = j
if need[s[j]] >= window[s[j]]:
cnt -= 1
window[s[j]] -= 1
j += 1
return '' 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
难度:中等
标签:回溯
解法
方法一:回溯(两种方式)
我们设计一个函数 d f s ( i ) dfs(i) dfs(i),表示从数字 i i i 开始搜索,当前搜索路径为 t t t,答案为 a n s ans ans。
函数 d f s ( i ) dfs(i) dfs(i) 的执行逻辑如下:
- 如果当前搜索路径 t t t 的长度等于 k k k,则将当前搜索路径加入答案,然后返回。
- 如果 i > n i \gt n i>n,则说明搜索已经结束,返回。
- 否则,我们可以选择将数字 i i i 加入搜索路径 t t t,然后继续搜索,即执行 d f s ( i + 1 ) dfs(i + 1) dfs(i+1),然后将数字 i i i 从搜索路径 t t t 中移除;或者不将数字 i i i 加入搜索路径 t t t,直接执行 d f s ( i + 1 ) dfs(i + 1) dfs(i+1)。
以上做法实际上是枚举当前数字选或者不选,然后递归地搜索下一个数字。我们也可以枚举下一个要选择的数字 j j j,其中 i ≤ j ≤ n i \leq j \leq n i≤j≤n,如果下一个要选择的数字是 j j j,那么我们将数字 j j j 加入搜索路径 t t t,然后继续搜索,即执行 d f s ( j + 1 ) dfs(j + 1) dfs(j+1),接着将数字 j j j 从搜索路径 t t t 中移除。
在主函数中,我们从数字 1 1 1 开始搜索,即执行 d f s ( 1 ) dfs(1) dfs(1)。
时间复杂度 ( C n k × k ) (C_n^k \times k) (Cnk×k),空间复杂度 O ( k ) O(k) O(k)。其中 C n k C_n^k Cnk 表示组合数。
相似题目:
Python3
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(i: int):
if len(t) == k:
ans.append(t[:])
return
if i > n:
return
t.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(回溯)
我们设计一个函数 d f s ( i ) dfs(i) dfs(i),表示从数组的第 i i i 个元素开始搜索所有子集。函数 d f s ( i ) dfs(i) dfs(i) 的执行逻辑如下:
- 如果 i = n i=n i=n,表示当前已经搜索结束,将当前得到的子集 t t t 加入答案数组 a n s ans ans 中,然后返回;
- 否则,我们可以选择不选择当前元素,直接执行 d f s ( i + 1 ) dfs(i+1) dfs(i+1);也可以选择当前元素,即把当前元素 n u m s [ i ] nums[i] nums[i] 加入子集 t t t,然后执行 d f s ( i + 1 ) dfs(i+1) dfs(i+1),注意要在执行 d f s ( i + 1 ) dfs(i+1) dfs(i+1) 以后再将 n u m s [ i ] nums[i] nums[i] 从子集 t t t 中移除(回溯)。
在主函数中,我们调用 d f s ( 0 ) dfs(0) dfs(0),即从数组的第一个元素开始搜索所有子集。最后返回答案数组 a n s ans ans 即可。
时间复杂度 O ( n × 2 n ) O(n\times 2^n) O(n×2n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为数组的长度。一共有 2 n 2^n 2n 个子集,每个子集需要 O ( n ) O(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[:])
return
dfs(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 ) (i, j) (i,j) 作为搜索的起点,然后从起点开始进行深度优先搜索,如果可以搜索到单词的末尾,就说明单词存在,否则说明单词不存在。
因此,我们设计一个函数 d f s ( i , j , k ) dfs(i, j, k) dfs(i,j,k),表示从网格的 ( i , j ) (i, j) (i,j) 位置出发,且从单词的第 k k k 个字符开始搜索,是否能够搜索成功。函数 d f s ( i , j , k ) dfs(i, j, k) dfs(i,j,k) 的执行步骤如下:
- 如果 k = ∣ w o r d ∣ − 1 k = |word|-1 k=∣word∣−1,说明已经搜索到单词的最后一个字符,此时只需要判断网格 ( i , j ) (i, j) (i,j) 位置的字符是否等于 w o r d [ k ] word[k] word[k],如果相等则说明单词存在,否则说明单词不存在。无论单词是否存在,都无需继续往下搜索,因此直接返回结果。
- 否则,如果
w
o
r
d
[
k
]
word[k]
word[k] 字符不等于网格
(
i
,
j
)
(i, j)
(i,j) 位置的字符,说明本次搜索失败,直接返回
false
。 - 否则,我们将网格
(
i
,
j
)
(i, j)
(i,j) 位置的字符暂存于
c
c
c 中,然后将此位置的字符修改为一个特殊字符
'0'
,代表此位置的字符已经被使用过,防止之后搜索时重复使用。然后我们从 ( i , j ) (i, j) (i,j) 位置的上、下、左、右四个方向分别出发,去搜索网格中第 k + 1 k+1 k+1 个字符,如果四个方向有任何一个方向搜索成功,就说明搜索成功,否则说明搜索失败,此时我们需要还原网格 ( i , j ) (i, j) (i,j) 位置的字符,即把 c c c 放回网格 ( i , j ) (i, j) (i,j) 位置(回溯)。
在主函数中,我们枚举网格中的每一个位置
(
i
,
j
)
(i, j)
(i,j) 作为起点,如果调用
d
f
s
(
i
,
j
,
0
)
dfs(i, j, 0)
dfs(i,j,0) 返回 true
,就说明单词存在,否则说明单词不存在,返回 false
。
时间复杂度 O ( m × n × 3 k ) O(m \times n \times 3^k) O(m×n×3k),空间复杂度 O ( min ( m × n , k ) ) O(\min(m \times n, k)) O(min(m×n,k))。其中 m m m 和 n n n 分别是网格的行数和列数;而 k k k 是字符串 w o r d word 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 False
c = board[i][j]
board[i][j] = "0"
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
ok = 0 <= x < m and 0 <= y < n and board[x][y] != "0"
if ok and dfs(x, y, k + 1):
return True
board[i][j] = c
return False
m, 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 k 记录当前已经处理好的数组的长度,初始时 k = 0 k=0 k=0,表示空数组。
然后我们从左到右遍历数组,对于遍历到的每个元素 x x x,如果 k < 2 k \lt 2 k<2 或者 x ≠ n u m s [ k − 2 ] x \neq nums[k-2] x=nums[k−2],我们就将 x x x 放到 n u m s [ k ] nums[k] nums[k] 的位置,然后 k k k 自增 1 1 1。否则, x x x 与 n u m s [ k − 2 ] nums[k-2] nums[k−2] 相同,我们直接跳过这个元素。继续遍历,直到遍历完整个数组。
这样,当遍历结束时, n u m s nums nums 中前 k k k 个元素就是我们要求的答案,且 k k k 就是答案的长度。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1)。其中 n n n 为数组的长度。
补充:
原问题要求最多相同的数字最多出现 2 2 2 次,我们可以扩展至相同的数字最多保留 k k k 个。
- 由于相同的数字最多保留 k k k 个,那么原数组的前 k k k 个元素我们可以直接保留;
- 对于后面的数字,能够保留的前提是:当前数字 x x x 与前面已保留的数字的倒数第 k k k 个元素比较,不同则保留,相同则跳过。
相似题目:
Python3
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 0
for x in nums:
if k < 2 or x != nums[k - 2]:
nums[k] = x
k += 1
return 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;
}
};
原文地址:https://blog.csdn.net/qq_53481114/article/details/142695042
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!