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

制作公司主页周口seo推广

制作公司主页,周口seo推广,水利部建设管理与安全中心网站,如何做app网站目录 1. 螺旋矩阵2. 划分字母区间3. 子集 II 1. 螺旋矩阵 &#x1f517; 原题链接&#xff1a;54. 螺旋矩阵 类似于BFS那样使用方向数组即可。 class Solution { public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m matrix.size(), …

目录

  • 1. 螺旋矩阵
  • 2. 划分字母区间
  • 3. 子集 II

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 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-0+1,15-9+1,23-16+1]=[9,7,8] [80+1,159+1,2316+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 u u 来控制),然后再枚举每个位置能够选哪些数。

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

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

回到本题,为了避免重复,我们同样可以先对数组排个序以确保相同的数字相邻,然后枚举每个位置,对于每个位置,枚举这个位置上对应的数可能出现的次数,即 [ 0 , k ] , k ≥ 1 [0,k],\,k\geq 1 [0,k],k1。当 k = 1 k=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 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 1ku 个的情形,如果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个。

注意到 n u m s [ i ] ∈ [ − 10 , 10 ] nums[i]\in[-10,10] nums[i][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());}
};
http://www.ds6.com.cn/news/33854.html

相关文章:

  • 做网站用什么技术好手游推广加盟
  • wordpress 写博客插件seo标题优化分析范文
  • 深圳建设局网站北京seo代理计费
  • 电商网站开发实战视频教程百度刷排名seo
  • 一家做土产网站常见的网络营销方法有哪些
  • 网站建设的职位seo技术助理
  • 淘宝客网站用什么软件做做网络推广一个月的收入
  • 做照明出口的网站有什么推广软件
  • 前端网站开发毕设类型百度seo关键词外包
  • 品牌网站建设4a小蝌蚪网络营销运营策划
  • 在建设局网站上怎么样总监解锁今日军事新闻最新消息
  • 肇庆自助网站建设系统app拉新推广平台
  • 如何查询网站的建设商网络推广怎样做
  • 做网站需要多钱广西seo公司
  • 做网站不推广管用吗竞价推广外包托管
  • vip视频网站怎么做2345网址导航官网下载
  • 济南品牌网站建设定制今日新闻播报
  • 江门做网站重庆seo服务
  • ui在线设计工具四川二级站seo整站优化排名
  • 兼职做网站安全么免费网站排名优化软件
  • 网站未备案什么意思免费创建个人网站
  • 网站导航如何用响应式做河南网络推广那家好
  • 广州seo运营网络优化的内容包括哪些
  • 微动漫怎么制作搜索引擎优化分析
  • 南昌网站建设设计优化设计电子版
  • 上海专业的网站新网站排名优化怎么做
  • 广州企业网站建设报价百度搜索智能精选
  • 宿迁哪里有做网站开发的代写文章兼职
  • 全国网站建设哪家专业网络营销试题库及答案
  • 小学网站模板免费下载上海关键词优化排名软件