Leetcode: 0031-0040题速览

Leetcode: 0031-0040题速览

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

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

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

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

难度：中等

标签：数组,双指针

解法

方法一：两次遍历

我们先从后往前遍历数组 $nums$，找到第一个满足 $nums[i]<nums[i+1]$ 的位置 $i$，那么 $nums[i]$ 就是我们需要交换的元素，而 $nums[i+1]$ 到 $nums[n-1]$ 的元素是一个降序序列。

接下来，我们再从后往前遍历数组 $nums$，找到第一个满足 $nums[j]>nums[i]$ 的位置 $j$，然后我们交换 $nums[i]$ 和 $nums[j]$。最后，我们将 $nums[i+1]$ 到 $nums[n-1]$ 的元素反转，即可得到下一个排列。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $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. 最长有效括号

题目描述

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

 

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：

输入：s = “”
输出：0

 

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

难度：困难

标签：栈,字符串,动态规划

解法

方法一：动态规划

我们定义 $f[i]$ 表示以 $s[i-1]$ 结尾的最长有效括号的长度，那么答案就是 $\underset{i=1}{\overset{n}{\max }}f[i]$。

• 如果 $s[i-1]$ 是左括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度一定为 $0$，因此 $f[i]=0$。
• 如果 $s[i-1]$ 是右括号，有以下两种情况：
  • 如果 $s[i-2]$ 是左括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度为 $f[i-2]+2$。
  • 如果 $s[i-2]$ 是右括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度为 $f[i-1]+2$，但是还需要考虑 $s[i-f[i-1]-2]$ 是否是左括号，如果是左括号，那么以 $s[i-1]$ 结尾的最长有效括号的长度为 $f[i-1]+2+f[i-f[i-1]-2]$。

因此，我们可以得到状态转移方程：

$$\{\begin{array}{ll}f[i]=0,& \text{if }s[i-1]{=}^{\prime }{(}^{\prime },\\ f[i]=f[i-2]+2,& \text{if }s[i-1]{=}^{\prime }{)}^{\prime }\text{ and }s[i-2]{=}^{\prime }{(}^{\prime },\\ f[i]=f[i-1]+2+f[i-f[i-1]-2],& \text{if }s[i-1]{=}^{\prime }{)}^{\prime }\text{ and }s[i-2]{=}^{\prime }{)}^{\prime }\text{ and }s[i-f[i-1]-2]{=}^{\prime }{(}^{\prime },\end{array}$$

最后返回 $\underset{i=1}{\overset{n}{\max }}f[i]$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(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] + 2else:j = i - f[i - 1] - 1if 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

难度：中等

标签：数组,二分查找

解法

方法一：二分查找

我们使用二分，将数组分割成 $[left,..mid]$, $[mid+1,..right]$ 两部分，这时候可以发现，其中有一部分一定是有序的。

因此，我们可以根据有序的那一部分，判断 $target$ 是否在这一部分中：

• 若 $[0,..mid]$ 范围内的元素构成有序数组：
  • 若满足 $nums[0]\le target\le nums[mid]$，那么我们搜索范围可以缩小为 $[left,..mid]$；
  • 否则，在 $[mid+1,..right]$ 中查找；
• 若 $[mid+1,n-1]$ 范围内的元素构成有序数组：
  • 若满足 $nums[mid]<target\le nums[n-1]$，那么我们搜索范围可以缩小为 $[mid+1,..right]$；
  • 否则，在 $[left,..mid]$ 中查找。

二分查找终止条件是 $left\ge right$，若结束后发现 $nums[left]$ 与 $target$ 不等，说明数组中不存在值为 $target$ 的元素，返回 $-1$，否则返回下标 $left$。

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

Python3

class Solution:def search(self, nums: List[int], target: int) -> int:n = len(nums)left, right = 0, n - 1while left < right:mid = (left + right) >> 1if nums[0] <= nums[mid]:if nums[0] <= target <= nums[mid]:right = midelse:left = mid + 1else:if nums[mid] < target <= nums[n - 1]:left = mid + 1else:right = midreturn 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;elseleft = mid + 1;} else {if (nums[mid] < target && target <= nums[n - 1])left = mid + 1;elseright = 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(1)$。其中 $n$ 是数组 $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;
}

做二分题目时，可以按照以下套路：

1. 写出循环条件 $left<right$；
2. 循环体内，不妨先写 $mid=\lfloor \frac{left+right}{2}\rfloor$；
3. 根据具体题目，实现 $check()$ 函数（有时很简单的逻辑，可以不定义 $check$），想一下究竟要用 $right=mid$（模板 $1$） 还是 $left=mid$（模板 $2$）；
   - 如果 $right=mid$，那么写出 else 语句 $left=mid+1$，并且不需要更改 mid 的计算，即保持 $mid=\lfloor \frac{left+right}{2}\rfloor$；
   - 如果 $left=mid$，那么写出 else 语句 $right=mid-1$，并且在 $mid$ 计算时补充 +1，即 $mid=\lfloor \frac{left+right+1}{2}\rfloor$；
4. 循环结束时， $left$ 与 $right$ 相等。

注意，这两个模板的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处的位置。 对于可能无解的情况，只要判断二分结束后的 $left$ 或者 $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

难度：简单

标签：数组,二分查找

解法

方法一：二分查找

由于 $nums$ 数组已经有序，因此我们可以使用二分查找的方法找到目标值 $target$ 的插入位置。

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

Python3

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)while l < r:mid = (l + r) >> 1if nums[mid] >= target:r = midelse:l = mid + 1return 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. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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\times 3$ 的宫格中的数字都不重复。

遍历数独，对于每个数字，判断其所在的行、列 以及 $3\times 3$ 的宫格是否已经出现过该数字，如果是，则返回 false。遍历结束，返回 true。

时间复杂度 $O(C)$，空间复杂度 $O(C)$，其中 $C$ 是数独中的空格数。本题中 $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 == '.':continuenum = int(c) - 1k = i // 3 * 3 + j // 3if row[i][num] or col[j][num] or sub[k][num]:return Falserow[i][num] = Truecol[j][num] = Truesub[k][num] = Truereturn 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. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

 

输入：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^2)$。

Python3

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:def dfs(k):nonlocal okif k == len(t):ok = Truereturni, 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] = Trueboard[i][j] = str(v + 1)dfs(k + 1)row[i][v] = col[j][v] = block[i // 3][j // 3][v] = Falseif ok:returnrow = [[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 = Falsefor i in range(9):for j in range(9):if board[i][j] == '.':t.append((i, j))else:v = int(board[i][j]) - 1row[i][v] = col[j][v] = block[i // 3][j // 3][v] = Truedfs(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：

输出："1211"

解释：

countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"

示例 2：

输出："1"

解释：

这是基本情况。

 

提示：

• 1 <= n <= 30

 

进阶：你能迭代解决该问题吗？

难度：中等

标签：字符串

解法

方法一

Python3

class Solution:def countAndSay(self, n: int) -> str:s = '1'for _ in range(n - 1):i = 0t = []while i < len(s):j = iwhile j < len(s) and s[j] == s[i]:j += 1t.append(str(j - i))t.append(str(s[i]))i = js = ''.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

难度：中等

标签：数组,回溯

解法

方法一：排序 + 剪枝 + 回溯

我们可以先对数组进行排序，方便剪枝。

接下来，我们设计一个函数 $dfs(i,s)$，表示从下标 $i$ 开始搜索，且剩余目标值为 $s$，其中 $i$ 和 $s$ 都是非负整数，当前搜索路径为 $t$，答案为 $ans$。

在函数 $dfs(i,s)$ 中，我们先判断 $s$ 是否为 $0$，如果是，则将当前搜索路径 $t$ 加入答案 $ans$ 中，然后返回。如果 $s<candidates[i]$，说明当前下标及后面的下标的元素都大于剩余目标值 $s$，路径不合法，直接返回。否则，我们从下标 $i$ 开始搜索，搜索的下标范围是 $j\in [i,n)$，其中 $n$ 为数组 $candidates$ 的长度。在搜索的过程中，我们将当前下标的元素加入搜索路径 $t$，递归调用函数 $dfs(j,s-candidates[j])$，递归结束后，将当前下标的元素从搜索路径 $t$ 中移除。

在主函数中，我们只要调用函数 $dfs(0,target)$，即可得到答案。

时间复杂度 $O(2^n\times n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $candidates$ 的长度。由于剪枝，实际的时间复杂度要远小于 $O(2^n\times n)$。

相似题目：

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

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[:])returnif s < candidates[i]:returnfor 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

难度：中等

标签：数组,回溯

解法

方法一：排序 + 剪枝 + 回溯

我们可以先对数组进行排序，方便剪枝以及跳过重复的数字。

接下来，我们设计一个函数 $dfs(i,s)$，表示从下标 $i$ 开始搜索，且剩余目标值为 $s$，其中 $i$ 和 $s$ 都是非负整数，当前搜索路径为 $t$，答案为 $ans$。

在函数 $dfs(i,s)$ 中，我们先判断 $s$ 是否为 $0$，如果是，则将当前搜索路径 $t$ 加入答案 $ans$ 中，然后返回。如果 $i\ge n$，或者 $s<candidates[i]$，说明当前路径不合法，直接返回。否则，我们从下标 $i$ 开始搜索，搜索的下标范围是 $j\in [i,n)$，其中 $n$ 为数组 $candidates$ 的长度。在搜索的过程中，如果 $j>i$ 并且 $candidates[j]=candidates[j-1]$，说明当前数字与上一个数字相同，我们可以跳过当前数字，因为上一个数字已经搜索过了。否则，我们将当前数字加入搜索路径 $t$ 中，然后递归调用函数 $dfs(j+1,s-candidates[j])$，然后将当前数字从搜索路径 $t$ 中移除。

在主函数中，我们只要调用函数 $dfs(0,target)$，即可得到答案。

时间复杂度 $O(2^n\times n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $candidates$ 的长度。由于剪枝，实际的时间复杂度要远小于 $O(2^n\times n)$。

相似题目：

• 39. 组合总和
• 77. 组合
• 216. 组合总和 III

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[:])returnif i >= len(candidates) or s < candidates[i]:returnfor j in range(i, len(candidates)):if j > i and candidates[j] == candidates[j - 1]:continuet.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;}
};

---