-
代码随想录算法训练营第二天| 97、209、904、76、59
双指针
Leecode977.有序数组的平方
链接：https://leetcode.cn/problems/squares-of-a-sorted-array/description/
为什么这个题也可以用双指针来做？
实际上和题目给的数据格式是密切相关的，因为原数组是有序的，即使是按照平方来重新排序，最大的数也都是在数组的两侧，所以我们设计两个指针：左指针和右指针，分别从左往右和从右往左开始扫描并比较两处的值，较大的值放置在新数组的偏后面的值，这样排序就可以满足题意
若是按照之前的写法从前往后遍历元素并swap，就有些类似于选择排序，并且选择排序肯定也不是O(n)的复杂度啊
class Solution { public: // 类似于排序问题 // 使用的双指针的思路是从两边开始比较，确实比较巧妙，和题目给予的数据格式紧密相关 vector<int> sortedSquares(vector<int>& nums) { //应该还是交换操作 // 还是快慢指针，每次在计算绝对值之后比较，若是快指针处的值小于慢指针处的值，那么就进行交换，这就类似于选择排序 // 众所周知选择排序一次是不太可能完成任务的 int left_index = 0, right_index = nums.size() - 1; vector<int> res(nums.size(),0); int k = nums.size() - 1; while (left_index <= right_index) { if (nums[left_index]*nums[left_index] > nums[right_index]*nums[right_index]) //开始的时候两边都是比较大的元素，因此应该是挑最大的元素放在数组后面 { res[k--] = (nums[left_index] * nums[left_index]); left_index++; } else { res[k--] = (nums[right_index] * nums[right_index]); right_index--; } } return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
滑动窗口
Leecode209. 长度最小的子数组
这道题目经历了漫长的优化过程···
version1
是想用滑动窗口，但是实际上分别枚举了窗口长度和窗口坐标，所以还是暴力，自然就超时了
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int maxlen = nums.size(); int nowlen = 1; while (nowlen <= maxlen) { int sum = 0; for (int i = 0; i<nowlen; i++) sum += nums[i]; if (sum >= target) return nowlen; for (int j = 1; j <= maxlen - nowlen; j++) { sum -= nums[j - 1]; sum += nums[j + nowlen - 1]; if (sum >= target) return nowlen; } nowlen++; } return 0; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
这里有边界条件需要注意：
窗口长度的最大值 = 索引值 + 1
第二层循环因为枚举的也是长度（最小值为1，并且范围就是1~maxlen - nowlen），所以减去的坐标处值的索引要减去1（比方说向前移动一格，要减去nums[1-1]处的值，并且加上nums[j + nowlen - 1]处的值）
version2
优化的思路就是：不是所有情况下都有必要进入第二层循环，只有在满足sum >= tar时才进入第二层循环企图缩减数组的长度，所以大大节约了时间
我们的思路是先进行第一层循环，枚举终点位置，若是判断当前和大于tar，就进入第二层循环。第二层循环中j每次都是从0开始，也就是从头开始尝试能减少多少值
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int len = nums.size(); int minlen = len; int sum = 0; int flag = 0; for (int i = 0; i < len; i++) { //每次进入循环 j 的值就应该被清0 int j = 0; sum += nums[i]; // 只要进去就可以判断 if (sum >= target) { int temp = sum; while (temp >= target) { flag = 1; // 更新长度 minlen = min(minlen, i - j + 1); // 尝试减小数组长度 temp -= nums[j]; // 这里错了，应该单独赋值一个变量用来表示当前的sum，sum的值是不可以在while循环中被改变的 j++; } } } if (flag) return minlen; return 0; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
但是其实没有必要重新刷新j，每次进入循环的时候 i 不需要从0开始，直接延续上一次的结果就OK
所以有了第三步优化：
version3
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; // 滑动窗口数值之和 int i = 0; // 滑动窗口起始位置 int subLength = 0; // 滑动窗口的长度 for (int j = 0; j < nums.size(); j++) { sum += nums[j]; // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件 while (sum >= s) { subLength = (j - i + 1); // 取子序列的长度 result = result < subLength ? result : subLength; sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置） } } // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列 return result == INT32_MAX ? 0 : result; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
Leecode904. 水果成篮
class Solution { public: int totalFruit(vector<int>& fruits) { // 大致思路：还是双指针&滑动窗口问题，开始的时候一个指针枚举最后面的位置，一直往前薅，直到超出了两种水果为止 // 然后开始进入第二层循环，是一个while循环，这个循环保证结束之后篮子里只有两种水果 // 然后第一层循环接着跑 // 需要一个数据结构来存水果的种类，我们使用unorderedmap int size = fruits.size(); unordered_map<int,int> cnt; // 水果的种类其实就是标号，所以第一个int存的是其标号，第二个int存的才是其数量 int left = 0,res = 0; for (int i=0;i<size;i++) { ++cnt[fruits[i]]; // 把对应的水果加进去就OK，会有数量的记录 while(cnt.size() > 2) // 一旦大于2，我们直接吐元素出来 { auto it = cnt.find(fruits[left]); --it->second; if(it->second == 0) cnt.erase(it); ++left; } res = max(res,i - left + 1); } return res; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
Leecode76. 最小覆盖子串
链接：https://leetcode.cn/problems/minimum-window-substring/description/
class Solution { public: unordered_map <char,int>map,match; bool check() { for(auto i : match) { if(map[i.first] < i.second) return false; } return true; } string minWindow(string s, string t) { // 还是可以用哈希表做，首先记录子串中出现的字符和其数量，统计到undered_map中去 // 然后按照顺序统计s串中的元素，如果统计sum(s)串中对应的数量不少于t中元素的数量，那么就是check true // 若是check true，那么就进行第二层循环，往右移动左边的指针，若是一直check true就一直移动，并且随时统计子串的长度 for(auto i : t) {++match[i];} int l = 0; int l_index = 0,len = INT_MAX; // 等于size其实是不合法的，size - 1合法 for(int r = 0;r<int(s.size());r++) { if(match.find(s[r]) != match.end()) ++map[s[r]]; while(check() && l<=r) // 需要l<=r,因为有可能是空串，就会数组越界 { // 先记录，然后缩减长度，只要不满足就退出 // 先更新len，若是len更新，那么我们再更新左索引 if(r - l + 1 < len) { len = r - l + 1; l_index = l; } // 向右移动l if(match.find(s[l]) != match.end()) --map[s[l]]; l++; } } if(len == INT_MAX) return string(); //返回空串的写法 return s.substr(l_index, len); } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
主要就是哈希表的使用比较麻烦一些，官方题解主要是用了两个优化手段
-
先判断当前字符是否在t串中出现过，也就是
if(match.find(s[r]) != match.end())- 1
若是没有出现过，我们再进行增删操作
-
善于用引用操作
for (const auto &c: t) {++ori[c];} for (const auto &p: ori) { if (cnt[p.first] < p.second) { return false; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
记录一下返回空串的写法，之前没有见过
return string()- 1
模拟
Leecode59.螺旋矩阵弍
链接：https://leetcode.cn/problems/spiral-matrix-ii/description/
最简单不过模拟，最易错不过模拟
我们要实现这种结构，可以只判断“不合法”的条件和“需要换向”的条件，因为构造螺旋矩阵的方向就是顺时针，所以我们可以提前设置4种方向，然后依照上述的两种条件进行换向和移动操作，最终可以填满整个数组
- 首先说“不合法”条件：我们定义的数组是n*n的，那么下标自然不能超过n-1。
- “需要换向”的条件：假设初始矩阵上值都为0并且我们所填的每一个值都是正确的，那么覆盖值的操作就一定是错误的，所以如果依照此刻的移动方向会覆盖掉某些值，就“需要换向”
然后梳理代码逻辑：
-
开始的时候有while循环，循环结束条件就是num不超过其最大值（为什么不能是for循环？因为无法保证每次进入循环后都能确保当前方向是正确的）
-
之后开始if判断，显然“不合法”条件的优先级是大于“需要换向”条件的优先级的，所以我们先判断移动后的坐标是否合法：若不合法，就continue；若合法，接着判断目标位置处是否是0，如果是不是0，那么就说明已经填充过值了，需要改变方向，并且continue
-
若是既“合法”也不“需要换向”，那么就在当前位置（注意还没有改变坐标，因为考虑到初始情况下 {0,0}位置也需要填值）填充num，然后改变x或者y
-
需要注意最后的位置，因为最后位置处上下左右往哪走都不合法，所以如果仅仅依靠四个if - else语句会死循环，所以我们在四个判断语句的前面就加上一句判断即可
if (num == n*n) { map[x][y] = n*n; break;}- 1
完整代码：
class Solution { public: vector<vector<int>> generateMatrix(int n) { int index = 0;//有四个值，分别是0,1,2,3，表示向右、下、左、上 int x = 0, y = 0; // 行和列 int num = 1; // 从1开始填充 vector<vector<int>> map(n, vector<int>(n)); while (num <= n*n) { if (num == n*n) { map[x][y] = n*n; break;} if (index == 0) { if (y + 1 >= n) { index++; if (index == 4) index = 0; continue; } if (map[x][y + 1] != 0){ index++; if (index == 4) index = 0; continue; } map[x][y] = num++; y++; } else if (index == 1) { if (x + 1 >= n ) { index++; if (index == 4) index = 0; continue; } if (map[x + 1][y] != 0){ index++; if (index == 4) index = 0; continue; } map[x][y] = num++; x++; } else if (index == 2) { if (y - 1 < 0) { index++; if (index == 4) index = 0; continue; } if (map[x][y - 1] != 0){ index++; if (index == 4) index = 0; continue; } map[x][y] = num++; y--; } else if (index == 3) { if (x - 1 < 0) { index++; if (index == 4) index = 0; continue; } if (map[x - 1][y] != 0){ index++; if (index == 4) index = 0; continue; } map[x][y] = num++; x--; } } return map; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
Leecode54.螺旋矩阵壹
基本上是在59题的基础上随便改改就过了
这里梳理一下修改的点有哪些：
- 首先不一定是一个n*n的矩阵，需要读取给予的矩阵的行和高
- 其次不是往空矩阵中填值，而是读取给予的矩阵的值
- 因此判断结束的条件会有细微变化：上面一题判断结束的条件很简单，只要num == n*n就说明是最后一个元素，但是这个题不行，因为最后读取的元素肯定不是最大的值，那么就通过vector的size决定是不是最后一个元素，读取最后一个元素完毕后直接break
- 上一题我们可以通过“该处有没有被填入值”判断这个格子有没有被走过，但是这次我们是读取矩阵上的值，所以此法失效。我们可以再创建一个二维数组，并且初始值全部为0，在我们读取的过程中给新数组填充上1，类似于上一题的填充操作
vector<int> spiralOrder(vector<vector<int>>& matrix) { int index = 0;//有四个值，分别是0,1,2,3，表示向右、下、左、上 int x = 0, y = 0; // 行和列 int num = 1; // 从1开始填充 int n = matrix.size(); int m = matrix[0].size(); //一定是从第0行读取，不然遇见1*1矩阵会报错 vector<vector<int>> map (n, vector<int>(m)); vector<int> res; // 创建一个和matrix一样size的数组，记录哪些值被读取过 while (res.size() <= n*m) { if (res.size() == n*m - 1) { res.push_back(matrix[x][y]); break; } if (index == 0) { if (y + 1 >= m) { index++; if (index == 4) index = 0; continue; } if (map[x][y + 1] != 0) { index++; if (index == 4) index = 0; continue; } res.push_back(matrix[x][y]); map[x][y] = 1; y++; } else if (index == 1) { if (x + 1 >= n) { index++; if (index == 4) index = 0; continue; } if (map[x + 1][y] != 0) { index++; if (index == 4) index = 0; continue; } res.push_back(matrix[x][y]); map[x][y] = 1; x++; } else if (index == 2) { if (y - 1 < 0) { index++; if (index == 4) index = 0; continue; } if (map[x][y - 1] != 0) { index++; if (index == 4) index = 0; continue; } res.push_back(matrix[x][y]); map[x][y] = 1; y--; } else if (index == 3) { if (x - 1 < 0) { index++; if (index == 4) index = 0; continue; } if (map[x - 1][y] != 0) { index++; if (index == 4) index = 0; continue; } res.push_back(matrix[x][y]); map[x][y] = 1; x--; } } return res; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
-
相关阅读:
性能优化-中间件tomcat调优
企业电子招投标系统源码之电子招投标系统建设的重点和未来趋势
三大排序(插入排序，选择排序，冒泡排序）
讲讲项目里的仪表盘编辑器（一）
（8）Lightweight OpenPose轻量化模型之 模型封装 + 摔倒检测
简单好用的 SemVer: 如何命名你的应用版本
如何让一个大几千页的打开巨慢的 PDF 秒开
解决absolute绝对定位带来的div穿透问题
golang读取键盘功能按键输入
Mysql(三) mysql事务和隔离级别
- 原文地址：https://blog.csdn.net/qq_51537085/article/details/127910353
