【2023】字节跳动 10 日心动计划——第九关

1. 螺旋矩阵

🔗 原题链接：54. 螺旋矩阵

类似于BFS那样使用方向数组即可。

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};vector<int> ans;int x = 0, y = 0, d = 1;ans.push_back(matrix[x][y]);for (int i = 0; i < n * m - 1; i++) {matrix[x][y] = -101;int a = x + dx[d], b = y + dy[d];if (a < 0 || a >= m || b < 0 || b >= n || matrix[a][b] == -101) {d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;ans.push_back(matrix[x][y]);}return ans;}
};

2. 划分字母区间

🔗 原题链接：763. 划分字母区间

这题本质是一个模拟题。

题目中规定了同一个字符不能出现在多个区间中，因此对于一个字符而言，如果它包含于某个区间，那么这个区间应当包含所有这样的字符。例如，如果一个区间包含字符 a，那么这个区间至少是 [a第一次出现的下标, a最后一次出现的下标]。这里为什么要用「至少」？是因为这个区间还会包含其他的字符，我们还需要对其他字符反复应用上述过程直到区间不再更新。

由于题目中的区间是按顺序分割的，因此我们只需要维护每个字符最后一次出现的下标即可。

例如对于字符串 ababcbacadefegdehijhklij，我们先看第一个字符 a，该字符最后一次出现的下标为 $8$，说明第一个区间至少是 $[0,8]$。我们依次枚举该区间的每一个字符，并用字符最后一次出现的下标来更新区间的右端点，这样一来，我们就可以得到不可分割的第一个区间。事实上，第一个区间就是 $[0,8]$。

现在从下标为 $9$ 的地方开始，该下标对应的字符是 d，该字符最后一次出现的下标为 $14$，说明第二个区间至少是 $[9,14]$，但注意到这个区间中有一个字符 e，所以我们必须扩充区间来把所有的 e 都包含进来，最终得到第二个区间为 $[9,15]$。

类似可得到第三个区间 $[16,23]$。

最终答案就是 $[8-0+1,15-9+1,23-16+1]=[9,7,8]$。

class Solution {
public:vector<int> partitionLabels(string s) {unordered_map<char, int> last;for (int i = 0; i < s.size(); i++) last[s[i]] = i;vector<int> res;int start = 0, end = 0;for (int i = 0; i < s.size(); i++) {end = max(end, last[s[i]]);if (i == end) {res.push_back(end - start + 1);start = end = i + 1;}}return res;}
};

3. 子集 II

🔗 原题链接：90. 子集 II

回顾全排列 I，我们是先枚举每个位置（通过 $u$ 来控制），然后再枚举每个位置能够选哪些数。

回顾子集 I，我们同样是枚举每个位置，然后再枚举这个位置到底是选还是不选。

回顾全排列 II，我们的枚举思路和全排列 I相同，但是为了避免重复，我们固定了相同数字的相对位置。

回到本题，为了避免重复，我们同样可以先对数组排个序以确保相同的数字相邻，然后枚举每个位置，对于每个位置，枚举这个位置上对应的数可能出现的次数，即 $[0,k],k\ge 1$。当 $k=1$ 时，子集 II就退化成了子集 I。

class Solution {
public:vector<vector<int>> ans;vector<int> path;vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ans;}void dfs(vector<int>& nums, int u) {if (u == nums.size()) {ans.push_back(path);return;}int k = u;while (k < nums.size() && nums[k] == nums[u]) k++;// 选0个dfs(nums, k);// 选1到k-u个for (int i = 0; i < k - u; i++) {path.push_back(nums[u]);dfs(nums, k);}path.erase(path.end() - (k - u), path.end());}
};

如果把递归过程看作在递归搜索树上游走，那么执行一次 dfs(nums, u) 相当于在当前节点处创建一个第 $u$ 层的子节点，然后移动到该子节点。当 dfs(nums, u) 执行完后，会返回到当前节点。

我们还需要保持dfs的前后状态一致。即执行dfs前的状态是什么样的，执行dfs后的状态也应当是什么样的。例如，我们通常喜欢在dfs之前修改 path 变量，那么在dfs执行之后，path 应当恢复成原来的样子，这一动作又称「恢复现场」。如果不想恢复现场，我们可以将 path 作为dfs函数的参数，在调用dfs的时候直接修改实参 path 即可（通常当 path 为字符串的时候会用到这种做法）。

可能会有读者好奇，为什么上述dfs函数中的for循环体中，没有在最后执行 path.pop_back() 呢？这是因为我们要枚举当前元素选 $1\sim k-u$ 个的情形，如果dfs后执行了 pop_back()，那么回到了当前节点后 path 就是空的，下次再dfs的时候 path 中仍然只有一个元素，这与 path 中应当有两个元素不符，所以我们应当等所有dfs执行完后统一恢复现场。

如果上述的C++代码还不够直观，那么请参考下方的Python实现：

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:def dfs(nums: List[int], u: int, path: List[int]):if u == len(nums):ans.append(path.copy())returnk = uwhile k < len(nums) and nums[k] == nums[u]:k += 1# 选0个dfs(nums, k, path)# 选1~k-u个for i in range(k - u):dfs(nums, k, path + [nums[u]] * (i + 1))nums.sort()ans = []dfs(nums, 0, [])return ans

因为Python可以直接在实参中修改列表，所以我们不需要做恢复现场，代码看起来也更加具有可读性。

注意到在C++中我们可以把选0个和选1~k-u个统一起来，即：

void dfs(vector<int>& nums, int u) {if (u == nums.size()) {ans.push_back(path);return;}int k = u;while (k < nums.size() && nums[k] == nums[u]) k++;for (int i = 0; i < k - u + 1; i++) {dfs(nums, k);path.push_back(nums[u]);}path.erase(path.end() - (k - u + 1), path.end());
}

在for循环中，交换dfs和push_back的顺序，那么第一次循环的时候就代表选0个。

注意到 $nums[i]\in [-10,10]$，我们可以从另一种角度来进行dfs：

class Solution {
public:unordered_map<int, int> cnt;vector<vector<int>> ans;vector<int> path;vector<vector<int>> subsetsWithDup(vector<int>& nums) {for (auto num: nums) cnt[num]++;dfs(-10);return ans;}void dfs(int u) {if (u > 10) {ans.push_back(path);return;}for (int i = 0; i < cnt[u] + 1; i++) {dfs(u + 1);path.push_back(u);}path.erase(path.end() - (cnt[u] + 1), path.end());}
};