Leetcode: 0031-0040题速览
研一在读备战就业,制此集合便于空闲时间浏览,有任何疑惑问题欢迎讨论,共同进步
目录
- Leetcode: 0031-0040题速览
-
- [31. 下一个排列](https://leetcode.cn/problems/next-permutation)
- [32. 最长有效括号](https://leetcode.cn/problems/longest-valid-parentheses)
- [33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array)
- [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array)
- [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position)
- [36. 有效的数独](https://leetcode.cn/problems/valid-sudoku)
- [37. 解数独](https://leetcode.cn/problems/sudoku-solver)
- [38. 外观数列](https://leetcode.cn/problems/count-and-say)
- [39. 组合总和](https://leetcode.cn/problems/combination-sum)
- [40. 组合总和 II](https://leetcode.cn/problems/combination-sum-ii)
31. 下一个排列
题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如,
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
难度:中等
标签:数组,双指针
解法
方法一:两次遍历
我们先从后往前遍历数组 n u m s nums nums,找到第一个满足 n u m s [ i ] < n u m s [ i + 1 ] nums[i] \lt nums[i + 1] nums[i]<nums[i+1] 的位置 i i i,那么 n u m s [ i ] nums[i] nums[i] 就是我们需要交换的元素,而 n u m s [ i + 1 ] nums[i + 1] nums[i+1] 到 n u m s [ n − 1 ] nums[n - 1] nums[n−1] 的元素是一个降序序列。
接下来,我们再从后往前遍历数组 n u m s nums nums,找到第一个满足 n u m s [ j ] > n u m s [ i ] nums[j] \gt nums[i] nums[j]>nums[i] 的位置 j j j,然后我们交换 n u m s [ i ] nums[i] nums[i] 和 n u m s [ j ] nums[j] nums[j]。最后,我们将 n u m s [ i + 1 ] nums[i + 1] nums[i+1] 到 n u m s [ n − 1 ] nums[n - 1] nums[n−1] 的元素反转,即可得到下一个排列。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1)。其中 n n n 为数组的长度。
Python3
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
if ~i:
j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1 :] = nums[i + 1 :][::-1]
Java
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
for (; i >= 0; --i) {
if (nums[i] < nums[i + 1]) {
break;
}
}
if (i >= 0) {
for (int j = n - 1; j > i; --j) {
if (nums[j] > nums[i]) {
swap(nums, i, j);
break;
}
}
}
for (int j = i + 1, k = n - 1; j < k; ++j, --k) {
swap(nums, j, k);
}
}
private void swap(int[] nums, int i, int j) {
int t = nums[j];
nums[j] = nums[i];
nums[i] = t;
}
}
C++
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n - 2;
while (~i && nums[i] >= nums[i + 1]) {
--i;
}
if (~i) {
for (int j = n - 1; j > i; --j) {
if (nums[j] > nums[i]) {
swap(nums[i], nums[j]);
break;
}
}
}
reverse(nums.begin() + i + 1, nums.end());
}
};
32. 最长有效括号
题目描述
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = “(()”
输出:2
解释:最长有效括号子串是 “()”
示例 2:
输入:s = “)()())”
输出:4
解释:最长有效括号子串是 “()()”
示例 3:
输入:s = “”
输出:0
提示:
0 <= s.length <= 3 * 104
s[i]
为'('
或')'
难度:困难
标签:栈,字符串,动态规划
解法
方法一:动态规划
我们定义 f [ i ] f[i] f[i] 表示以 s [ i − 1 ] s[i-1] s[i−1] 结尾的最长有效括号的长度,那么答案就是 max i = 1 n f [ i ] \max\limits_{i=1}^n f[i] i=1maxnf[i]。
- 如果 s [ i − 1 ] s[i-1] s[i−1] 是左括号,那么以 s [ i − 1 ] s[i-1] s[i−1] 结尾的最长有效括号的长度一定为 0 0 0,因此 f [ i ] = 0 f[i] = 0 f[i]=0。
- 如果 s [ i − 1 ] s[i-1] s[i−1] 是右括号,有以下两种情况:
- 如果 s [ i − 2 ] s[i-2] s[i−2] 是左括号,那么以 s [ i − 1 ] s[i-1] s[i−1] 结尾的最长有效括号的长度为 f [ i − 2 ] + 2 f[i-2] + 2 f[i−2]+2。
- 如果 s [ i − 2 ] s[i-2] s[i−2] 是右括号,那么以 s [ i − 1 ] s[i-1] s[i−1] 结尾的最长有效括号的长度为 f [ i − 1 ] + 2 f[i-1] + 2 f[i−1]+2,但是还需要考虑 s [ i − f [ i − 1 ] − 2 ] s[i-f[i-1]-2] s[i−f[i−1]−2] 是否是左括号,如果是左括号,那么以 s [ i − 1 ] s[i-1] s[i−1] 结尾的最长有效括号的长度为 f [ i − 1 ] + 2 + f [ i − f [ i − 1 ] − 2 ] f[i-1] + 2 + f[i-f[i-1]-2] f[i−1]+2+f[i−f[i−1]−2]。
因此,我们可以得到状态转移方程:
{ f [ i ] = 0 , if s [ i − 1 ] = ′ ( ′ , f [ i ] = f [ i − 2 ] + 2 , if s [ i − 1 ] = ′ ) ′ and s [ i − 2 ] = ′ ( ′ , f [ i ] = f [ i − 1 ] + 2 + f [ i − f [ i − 1 ] − 2 ] , if s [ i − 1 ] = ′ ) ′ and s [ i − 2 ] = ′ ) ′ and s [ i − f [ i − 1 ] − 2 ] = ′ ( ′ , \begin{cases} f[i] = 0, & \textit{if } s[i-1] = '(',\\ f[i] = f[i-2] + 2, & \textit{if } s[i-1] = ')' \textit{ and } s[i-2] = '(',\\ f[i] = f[i-1] + 2 + f[i-f[i-1]-2], & \textit{if } s[i-1] = ')' \textit{ and } s[i-2] = ')' \textit{ and } s[i-f[i-1]-2] = '(',\\ \end{cases} ⎩ ⎨ ⎧f[i]=0,f[i]=f[i−2]+2,f[i]=f[i−1]+2+f[i−f[i−1]−2],if s[i−1]=′(′,if s[i−1]=′)′ and s[i−2]=′(′,if s[i−1]=′)′ and s[i−2]=′)′ and s[i−f[i−1]−2]=′(′,
最后返回 max i = 1 n f [ i ] \max\limits_{i=1}^n f[i] i=1maxnf[i] 即可。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为字符串的长度。
Python3
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
f = [0] * (n + 1)
for i, c in enumerate(s, 1):
if c == ")":
if i > 1 and s[i - 2] == "(":
f[i] = f[i - 2] + 2
else:
j = i - f[i - 1] - 1
if j and s[j - 1] == "(":
f[i] = f[i - 1] + 2 + f[j - 1]
return max(f)
Java
class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
int[] f = new int[n + 1];
int ans = 0;
for (int i = 2; i <= n; ++i) {
if (s.charAt(i - 1) == ')') {
if (s.charAt(i - 2) == '(') {
f[i] = f[i - 2] + 2;
} else {
int j = i - f[i - 1] - 1;
if (j > 0 && s.charAt(j - 1) == '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
ans = Math.max(ans, f[i]);
}
}
return ans;
}
}
C++
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int f[n + 1];
memset(f, 0, sizeof(f));
for (int i = 2; i <= n; ++i) {
if (s[i - 1] == ')') {
if (s[i - 2] == '(') {
f[i] = f[i - 2] + 2;
} else {
int j = i - f[i - 1] - 1;
if (j && s[j - 1] == '(') {
f[i] = f[i - 1] + 2 + f[j - 1];
}
}
}
}
return *max_element(f, f + n + 1);
}
};
33. 搜索旋转排序数组
题目描述
整数数组 nums
按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数 target
,如果 nums
中存在这个目标值 target
,则返回它的下标,否则返回 -1
。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2]
, target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2]
, target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
中的每个值都 独一无二- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -104 <= target <= 104
难度:中等
标签:数组,二分查找
解法
方法一:二分查找
我们使用二分,将数组分割成 [ l e f t , . . m i d ] [left,.. mid] [left,..mid], [ m i d + 1 , . . r i g h t ] [mid + 1,.. right] [mid+1,..right] 两部分,这时候可以发现,其中有一部分一定是有序的。
因此,我们可以根据有序的那一部分,判断 t a r g e t target target 是否在这一部分中:
- 若 [ 0 , . . m i d ] [0,.. mid] [0,..mid] 范围内的元素构成有序数组:
- 若满足 n u m s [ 0 ] ≤ t a r g e t ≤ n u m s [ m i d ] nums[0] \leq target \leq nums[mid] nums[0]≤target≤nums[mid],那么我们搜索范围可以缩小为 [ l e f t , . . m i d ] [left,.. mid] [left,..mid];
- 否则,在 [ m i d + 1 , . . r i g h t ] [mid + 1,.. right] [mid+1,..right] 中查找;
- 若 [ m i d + 1 , n − 1 ] [mid + 1, n - 1] [mid+1,n−1] 范围内的元素构成有序数组:
- 若满足 n u m s [ m i d ] < t a r g e t ≤ n u m s [ n − 1 ] nums[mid] \lt target \leq nums[n - 1] nums[mid]<target≤nums[n−1],那么我们搜索范围可以缩小为 [ m i d + 1 , . . r i g h t ] [mid + 1,.. right] [mid+1,..right];
- 否则,在 [ l e f t , . . m i d ] [left,.. mid] [left,..mid] 中查找。
二分查找终止条件是 l e f t ≥ r i g h t left \geq right left≥right,若结束后发现 n u m s [ l e f t ] nums[left] nums[left] 与 t a r g e t target target 不等,说明数组中不存在值为 t a r g e t target target 的元素,返回 − 1 -1 −1,否则返回下标 l e f t left left。
时间复杂度 O ( log n ) O(\log n) O(logn),其中 n n n 是数组 n u m s nums nums 的长度。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left < right:
mid = (left + right) >> 1
if nums[0] <= nums[mid]:
if nums[0] <= target <= nums[mid]:
right = mid
else:
left = mid + 1
else:
if nums[mid] < target <= nums[n - 1]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
Java
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
}
}
C++
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid])
right = mid;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[n - 1])
left = mid + 1;
else
right = mid;
}
}
return nums[left] == target ? left : -1;
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10]
, target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10]
, target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
难度:中等
标签:数组,二分查找
解法
方法一:二分查找
我们可以进行两次二分查找,分别查找出左边界和右边界。
时间复杂度 O ( log n ) O(\log n) O(logn),空间复杂度 O ( 1 ) O(1) O(1)。其中 n n n 是数组 n u m s nums nums 的长度。
以下是二分查找的两个通用模板:
模板 1:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
模板 2:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
做二分题目时,可以按照以下套路:
- 写出循环条件 l e f t < r i g h t left < right left<right;
- 循环体内,不妨先写 m i d = ⌊ l e f t + r i g h t 2 ⌋ mid = \lfloor \frac{left + right}{2} \rfloor mid=⌊2left+right⌋;
- 根据具体题目,实现 c h e c k ( ) check() check() 函数(有时很简单的逻辑,可以不定义 c h e c k check check),想一下究竟要用 r i g h t = m i d right = mid right=mid(模板 1 1 1) 还是 l e f t = m i d left = mid left=mid(模板 2 2 2);
- 如果 r i g h t = m i d right = mid right=mid,那么写出 else 语句 l e f t = m i d + 1 left = mid + 1 left=mid+1,并且不需要更改 mid 的计算,即保持 m i d = ⌊ l e f t + r i g h t 2 ⌋ mid = \lfloor \frac{left + right}{2} \rfloor mid=⌊2left+right⌋;
- 如果 l e f t = m i d left = mid left=mid,那么写出 else 语句 r i g h t = m i d − 1 right = mid - 1 right=mid−1,并且在 m i d mid mid 计算时补充 +1,即 m i d = ⌊ l e f t + r i g h t + 1 2 ⌋ mid = \lfloor \frac{left + right + 1}{2} \rfloor mid=⌊2left+right+1⌋; - 循环结束时, l e f t left left 与 r i g h t right right 相等。
注意,这两个模板的优点是始终保持答案位于二分区间内,二分结束条件对应的值恰好在答案所处的位置。 对于可能无解的情况,只要判断二分结束后的 l e f t left left 或者 r i g h t right right 是否满足题意即可。
Python3
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l = bisect_left(nums, target)
r = bisect_left(nums, target + 1)
return [-1, -1] if l == r else [l, r - 1]
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int l = search(nums, target);
int r = search(nums, target + 1);
return l == r ? new int[] {-1, -1} : new int[] {l, r - 1};
}
private int search(int[] nums, int x) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
C++
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin();
if (l == r) return {-1, -1};
return {l, r - 1};
}
};
35. 搜索插入位置
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
为 无重复元素 的 升序 排列数组-104 <= target <= 104
难度:简单
标签:数组,二分查找
解法
方法一:二分查找
由于 n u m s nums nums 数组已经有序,因此我们可以使用二分查找的方法找到目标值 t a r g e t target target 的插入位置。
时间复杂度 O ( log n ) O(\log n) O(logn),空间复杂度 O ( 1 ) O(1) O(1)。其中 n n n 为数组 n u m s nums nums 的长度。
Python3
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)
while l < r:
mid = (l + r) >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
Java
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = (l + r) >>> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
C++
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
36. 有效的数独
题目描述
请你判断一个 9 x 9
的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)
注意:
- 一个有效的数独(部分已被填充)不一定是可解的。
- 只需要根据以上规则,验证已经填入的数字是否有效即可。
- 空白格用
'.'
表示。
示例 1:
输入:board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出:true
示例 2:
输入:board =
[[“8”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出:false
解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字(1-9
)或者'.'
难度:中等
标签:数组,哈希表,矩阵
解法
方法一:一次遍历
有效的数独满足以下三个条件:
- 每一行中的数字都不重复;
- 每一列中的数字都不重复;
- 每一个 3 × 3 3 \times 3 3×3 的宫格中的数字都不重复。
遍历数独,对于每个数字,判断其所在的行、列 以及 3 × 3 3 \times 3 3×3 的宫格是否已经出现过该数字,如果是,则返回 false
。遍历结束,返回 true
。
时间复杂度 O ( C ) O(C) O(C),空间复杂度 O ( C ) O(C) O(C),其中 C C C 是数独中的空格数。本题中 C = 81 C=81 C=81。
Python3
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = [[False] * 9 for _ in range(9)]
col = [[False] * 9 for _ in range(9)]
sub = [[False] * 9 for _ in range(9)]
for i in range(9):
for j in range(9):
c = board[i][j]
if c == '.':
continue
num = int(c) - 1
k = i // 3 * 3 + j // 3
if row[i][num] or col[j][num] or sub[k][num]:
return False
row[i][num] = True
col[j][num] = True
sub[k][num] = True
return True
Java
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] row = new boolean[9][9];
boolean[][] col = new boolean[9][9];
boolean[][] sub = new boolean[9][9];
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char c = board[i][j];
if (c == '.') {
continue;
}
int num = c - '0' - 1;
int k = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || sub[k][num]) {
return false;
}
row[i][num] = true;
col[j][num] = true;
sub[k][num] = true;
}
}
return true;
}
}
C++
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool>> row(9, vector<bool>(9, false));
vector<vector<bool>> col(9, vector<bool>(9, false));
vector<vector<bool>> sub(9, vector<bool>(9, false));
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char c = board[i][j];
if (c == '.') continue;
int num = c - '0' - 1;
int k = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || sub[k][num]) {
return false;
}
row[i][num] = true;
col[j][num] = true;
sub[k][num] = true;
}
}
return true;
}
};
37. 解数独
题目描述
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.'
表示。
示例 1:
输入:board = [[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”],[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”],[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”],[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”],[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”],[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”],[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”],[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”],[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出:[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字或者'.'
- 题目数据 保证 输入数独仅有一个解
难度:困难
标签:数组,哈希表,回溯,矩阵
解法
方法一:回溯
我们用数组 row
、col
、box
分别记录每一行、每一列、每个 3x3 宫格中数字是否出现过。如果数字 i
在第 r
行、第 c
列、第 b
个 3x3 宫格中出现过,那么 row[r][i]
、col[c][i]
、box[b][i]
都为 true
。
我们遍历 board
的每一个空格,枚举它可以填入的数字 v
,如果 v
在当前行、当前列、当前 3x3 宫格中没有出现过,那么我们就可以尝试填入数字 v
,并继续搜索下一个空格。如果搜索到最后,所有空格填充完毕,那么就说明找到了一个可行解。
时间复杂度 O ( 9 81 ) O(9^{81}) O(981),空间复杂度 O ( 9 2 ) O(9^2) O(92)。
Python3
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def dfs(k):
nonlocal ok
if k == len(t):
ok = True
return
i, j = t[k]
for v in range(9):
if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
board[i][j] = str(v + 1)
dfs(k + 1)
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
if ok:
return
row = [[False] * 9 for _ in range(9)]
col = [[False] * 9 for _ in range(9)]
block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
t = []
ok = False
for i in range(9):
for j in range(9):
if board[i][j] == '.':
t.append((i, j))
else:
v = int(board[i][j]) - 1
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
dfs(0)
Java
class Solution {
private boolean ok;
private char[][] board;
private List<Integer> t = new ArrayList<>();
private boolean[][] row = new boolean[9][9];
private boolean[][] col = new boolean[9][9];
private boolean[][][] block = new boolean[3][3][9];
public void solveSudoku(char[][] board) {
this.board = board;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
t.add(i * 9 + j);
} else {
int v = board[i][j] - '1';
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
}
}
}
dfs(0);
}
private void dfs(int k) {
if (k == t.size()) {
ok = true;
return;
}
int i = t.get(k) / 9, j = t.get(k) % 9;
for (int v = 0; v < 9; ++v) {
if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
board[i][j] = (char) (v + '1');
dfs(k + 1);
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
}
if (ok) {
return;
}
}
}
}
C++
using pii = pair<int, int>;
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
bool row[9][9] = {false};
bool col[9][9] = {false};
bool block[3][3][9] = {false};
bool ok = false;
vector<pii> t;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
t.push_back({i, j});
} else {
int v = board[i][j] - '1';
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
}
}
}
function<void(int k)> dfs = [&](int k) {
if (k == t.size()) {
ok = true;
return;
}
int i = t[k].first, j = t[k].second;
for (int v = 0; v < 9; ++v) {
if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
board[i][j] = v + '1';
dfs(k + 1);
row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
}
if (ok) {
return;
}
}
};
dfs(0);
}
};
38. 外观数列
题目描述
「外观数列」是一个数位字符串序列,由递归公式定义:
countAndSay(1) = "1"
countAndSay(n)
是countAndSay(n-1)
的行程长度编码。
行程长度编码(RLE)是一种字符串压缩方法,其工作原理是通过将连续相同字符(重复两次或更多次)替换为字符重复次数(运行长度)和字符的串联。例如,要压缩字符串 "3322251"
,我们将 "33"
用 "23"
替换,将 "222"
用 "32"
替换,将 "5"
用 "15"
替换并将 "1"
用 "11"
替换。因此压缩后字符串变为 "23321511"
。
给定一个整数 n
,返回 外观数列 的第 n
个元素。
示例 1:
输入:n = 4
输出:"1211"
解释:
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"
示例 2:
输入:n = 1
输出:"1"
解释:
这是基本情况。
提示:
1 <= n <= 30
进阶:你能迭代解决该问题吗?
难度:中等
标签:字符串
解法
方法一
Python3
class Solution:
def countAndSay(self, n: int) -> str:
s = '1'
for _ in range(n - 1):
i = 0
t = []
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
t.append(str(j - i))
t.append(str(s[i]))
i = j
s = ''.join(t)
return s
Java
class Solution {
public String countAndSay(int n) {
String s = "1";
while (--n > 0) {
StringBuilder t = new StringBuilder();
for (int i = 0; i < s.length();) {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) {
++j;
}
t.append((j - i) + "");
t.append(s.charAt(i));
i = j;
}
s = t.toString();
}
return s;
}
}
C++
class Solution {
public:
string countAndSay(int n) {
string s = "1";
while (--n) {
string t = "";
for (int i = 0; i < s.size();) {
int j = i;
while (j < s.size() && s[j] == s[i]) ++j;
t += to_string(j - i);
t += s[i];
i = j;
}
s = t;
}
return s;
}
};
39. 组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
示例 1:
输入:candidates = [2,3,6,7],
target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5],
target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2],
target = 1
输出: []
提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates
的所有元素 互不相同1 <= target <= 40
难度:中等
标签:数组,回溯
解法
方法一:排序 + 剪枝 + 回溯
我们可以先对数组进行排序,方便剪枝。
接下来,我们设计一个函数 d f s ( i , s ) dfs(i, s) dfs(i,s),表示从下标 i i i 开始搜索,且剩余目标值为 s s s,其中 i i i 和 s s s 都是非负整数,当前搜索路径为 t t t,答案为 a n s ans ans。
在函数 d f s ( i , s ) dfs(i, s) dfs(i,s) 中,我们先判断 s s s 是否为 0 0 0,如果是,则将当前搜索路径 t t t 加入答案 a n s ans ans 中,然后返回。如果 s < c a n d i d a t e s [ i ] s \lt candidates[i] s<candidates[i],说明当前下标及后面的下标的元素都大于剩余目标值 s s s,路径不合法,直接返回。否则,我们从下标 i i i 开始搜索,搜索的下标范围是 j ∈ [ i , n ) j \in [i, n) j∈[i,n),其中 n n n 为数组 c a n d i d a t e s candidates candidates 的长度。在搜索的过程中,我们将当前下标的元素加入搜索路径 t t t,递归调用函数 d f s ( j , s − c a n d i d a t e s [ j ] ) dfs(j, s - candidates[j]) dfs(j,s−candidates[j]),递归结束后,将当前下标的元素从搜索路径 t t t 中移除。
在主函数中,我们只要调用函数 d f s ( 0 , t a r g e t ) dfs(0, target) dfs(0,target),即可得到答案。
时间复杂度 O ( 2 n × n ) O(2^n \times n) O(2n×n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为数组 c a n d i d a t e s candidates candidates 的长度。由于剪枝,实际的时间复杂度要远小于 O ( 2 n × n ) O(2^n \times n) O(2n×n)。
相似题目:
Python3
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
ans.append(t[:])
return
if s < candidates[i]:
return
for j in range(i, len(candidates)):
t.append(candidates[j])
dfs(j, s - candidates[j])
t.pop()
candidates.sort()
t = []
ans = []
dfs(0, target)
return ans
Java
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] candidates;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.add(new ArrayList(t));
return;
}
if (s < candidates[i]) {
return;
}
for (int j = i; j < candidates.length; ++j) {
t.add(candidates[j]);
dfs(j, s - candidates[j]);
t.remove(t.size() - 1);
}
}
}
C++
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> t;
function<void(int, int)> dfs = [&](int i, int s) {
if (s == 0) {
ans.emplace_back(t);
return;
}
if (s < candidates[i]) {
return;
}
for (int j = i; j < candidates.size(); ++j) {
t.push_back(candidates[j]);
dfs(j, s - candidates[j]);
t.pop_back();
}
};
dfs(0, target);
return ans;
}
};
40. 组合总和 II
题目描述
给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5]
, target = 8
,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
难度:中等
标签:数组,回溯
解法
方法一:排序 + 剪枝 + 回溯
我们可以先对数组进行排序,方便剪枝以及跳过重复的数字。
接下来,我们设计一个函数 d f s ( i , s ) dfs(i, s) dfs(i,s),表示从下标 i i i 开始搜索,且剩余目标值为 s s s,其中 i i i 和 s s s 都是非负整数,当前搜索路径为 t t t,答案为 a n s ans ans。
在函数 d f s ( i , s ) dfs(i, s) dfs(i,s) 中,我们先判断 s s s 是否为 0 0 0,如果是,则将当前搜索路径 t t t 加入答案 a n s ans ans 中,然后返回。如果 i ≥ n i \geq n i≥n,或者 s < c a n d i d a t e s [ i ] s \lt candidates[i] s<candidates[i],说明当前路径不合法,直接返回。否则,我们从下标 i i i 开始搜索,搜索的下标范围是 j ∈ [ i , n ) j \in [i, n) j∈[i,n),其中 n n n 为数组 c a n d i d a t e s candidates candidates 的长度。在搜索的过程中,如果 j > i j \gt i j>i 并且 c a n d i d a t e s [ j ] = c a n d i d a t e s [ j − 1 ] candidates[j] = candidates[j - 1] candidates[j]=candidates[j−1],说明当前数字与上一个数字相同,我们可以跳过当前数字,因为上一个数字已经搜索过了。否则,我们将当前数字加入搜索路径 t t t 中,然后递归调用函数 d f s ( j + 1 , s − c a n d i d a t e s [ j ] ) dfs(j + 1, s - candidates[j]) dfs(j+1,s−candidates[j]),然后将当前数字从搜索路径 t t t 中移除。
在主函数中,我们只要调用函数 d f s ( 0 , t a r g e t ) dfs(0, target) dfs(0,target),即可得到答案。
时间复杂度 O ( 2 n × n ) O(2^n \times n) O(2n×n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 为数组 c a n d i d a t e s candidates candidates 的长度。由于剪枝,实际的时间复杂度要远小于 O ( 2 n × n ) O(2^n \times n) O(2n×n)。
相似题目:
Python3
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
ans.append(t[:])
return
if i >= len(candidates) or s < candidates[i]:
return
for j in range(i, len(candidates)):
if j > i and candidates[j] == candidates[j - 1]:
continue
t.append(candidates[j])
dfs(j + 1, s - candidates[j])
t.pop()
candidates.sort()
ans = []
t = []
dfs(0, target)
return ans
Java
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] candidates;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.add(new ArrayList<>(t));
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
for (int j = i; j < candidates.length; ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
t.add(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.remove(t.size() - 1);
}
}
}
C++
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> t;
function<void(int, int)> dfs = [&](int i, int s) {
if (s == 0) {
ans.emplace_back(t);
return;
}
if (i >= candidates.size() || s < candidates[i]) {
return;
}
for (int j = i; j < candidates.size(); ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
t.emplace_back(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.pop_back();
}
};
dfs(0, target);
return ans;
}
};