vs可以做网站吗花生壳域名还免费吗

当前位置： 首页 > news >正文

vs可以做网站吗,花生壳域名还免费吗,中国制造网介绍,站多多 福州网站建设目录 1. 螺旋矩阵2. 划分字母区间3. 子集 II 1. 螺旋矩阵 #x1f517; 原题链接#xff1a;54. 螺旋矩阵 类似于BFS那样使用方向数组即可。 class Solution { public:vectorint spiralOrder(vectorvectorint matrix) {int m matrix.size(), … 目录 1. 螺旋矩阵2. 划分字母区间3. 子集 II 1. 螺旋矩阵 原题链接54. 螺旋矩阵 类似于BFS那样使用方向数组即可。 class Solution { public:vectorint spiralOrder(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();int dx[] {-1, 0, 1, 0}, dy[] {0, 1, 0, -1};vectorint 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 8 8说明第一个区间至少是 [ 0 , 8 ] [0,8] [0,8]。我们依次枚举该区间的每一个字符并用字符最后一次出现的下标来更新区间的右端点这样一来我们就可以得到不可分割的第一个区间。事实上第一个区间就是 [ 0 , 8 ] [0,8] [0,8]。 现在从下标为 9 9 9 的地方开始该下标对应的字符是 d该字符最后一次出现的下标为 14 14 14说明第二个区间至少是 [ 9 , 14 ] [9,14] [9,14]但注意到这个区间中有一个字符 e所以我们必须扩充区间来把所有的 e 都包含进来最终得到第二个区间为 [ 9 , 15 ] [9,15] [9,15]。 类似可得到第三个区间 [ 16 , 23 ] [16,23] [16,23]。 最终答案就是 [ 8 − 0 1 , 15 − 9 1 , 23 − 16 1 ] [ 9 , 7 , 8 ] [8-01,15-91,23-161][9,7,8] [8−01,15−91,23−161][9,7,8]。 class Solution { public:vectorint partitionLabels(string s) {unordered_mapchar, int last;for (int i 0; i s.size(); i) last[s[i]] i;vectorint 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 u u 来控制然后再枚举每个位置能够选哪些数。 回顾子集 I我们同样是枚举每个位置然后再枚举这个位置到底是选还是不选。 回顾全排列 II我们的枚举思路和全排列 I相同但是为了避免重复我们固定了相同数字的相对位置。 回到本题为了避免重复我们同样可以先对数组排个序以确保相同的数字相邻然后枚举每个位置对于每个位置枚举这个位置上对应的数可能出现的次数即 [ 0 , k ] , k ≥ 1 [0,k],\,k\geq 1 [0,k],k≥1。当 k 1 k1 k1 时子集 II就退化成了子集 I。 class Solution { public:vectorvectorint ans;vectorint path;vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ans;}void dfs(vectorint 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 u u 层的子节点然后移动到该子节点。当 dfs(nums, u) 执行完后会返回到当前节点。 我们还需要保持dfs的前后状态一致。即执行dfs前的状态是什么样的执行dfs后的状态也应当是什么样的。例如我们通常喜欢在dfs之前修改 path 变量那么在dfs执行之后path 应当恢复成原来的样子这一动作又称「恢复现场」。如果不想恢复现场我们可以将 path 作为dfs函数的参数在调用dfs的时候直接修改实参 path 即可通常当 path 为字符串的时候会用到这种做法。 可能会有读者好奇为什么上述dfs函数中的for循环体中没有在最后执行 path.pop_back() 呢这是因为我们要枚举当前元素选 1 ∼ k − u 1\sim k-u 1∼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(vectorint 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个。 注意到 n u m s [ i ] ∈ [ − 10 , 10 ] nums[i]\in[-10,10] nums[i]∈[−10,10]我们可以从另一种角度来进行dfs class Solution { public:unordered_mapint, int cnt;vectorvectorint ans;vectorint path;vectorvectorint subsetsWithDup(vectorint 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());} };