海南省建设监理协会网站,新河网吧,小程序注册失败怎么办,怎样建设淘宝网站目录#xff1a;
解题及思路学习
977.有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array/submissions/
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例 1
解题及思路学习
977.有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array/submissions/
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10]
输出[0,1,9,16,100]思考双指针法
class Solution {
public:vectorint sortedSquares(vectorint nums) {int k nums.size() - 1;vectorint result(nums.size(), 0);for (int i 0, j k; i j;) {if (nums[j] * nums[j] nums[i] * nums[i]) {result[k--] nums[j] * nums[j];j--;} else {result[k--] nums[i] * nums[i];i;}}return result;}
};时间复杂度为O(n)
空间复杂度为O(1)
209.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
给定一个含有 n ****个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ****≥ target **的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。**如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2思考需要找到满足和≥ target的最短子数组长度。利用双指针法统计两个指针之间的和。当两个指针之间的数值count target的时候指针就一直往前移动。当 ≥ target的时候记录下最短的距离。然后左边的指针就往右移看是否满足。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int result INT32_MAX;int i 0; int sum 0;int sublength 0;for (int j 0; j nums.size(); j) {sum nums[j];while(sum target) {sublength (j - i 1);result result sublength? result: sublength;sum - nums[i];}}return result INT32_MAX ? 0 : result;}
};时间复杂度O(n)空间复杂度O(1)
59.螺旋矩阵II
https://leetcode.cn/problems/spiral-matrix-ii/
给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1
!https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg
输入n 3
输出[[1,2,3],[8,9,4],[7,6,5]]思考这道题 就模拟题。之前我记得主要是考察边界的问题。
class Solution {
public:vectorvectorint generateMatrix(int n) {vectorvectorint res(n, vectorint(n, 0));int startx 0, starty 0;int loop n / 2;int mid n / 2;int count 1;int offset 1;int i , j;while(loop--) {i startx;j starty;for (j starty; j n - offset; j) {res[startx][j] count;}for (i startx; i n - offset; i) {res[i][j] count;}for (; j starty; j--) {res[i][j] count;}for (; i startx; i--) {res[i][j] count;}startx;starty;offset 1;}if (n % 2) {res[mid][mid] count;}return res;}};时间复杂度 O(n^2): 模拟遍历二维矩阵的时间空间复杂度 O(1)
扩展题目
904. 水果成篮
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果
你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。
给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。
示例 2
输入fruits [0,1,2,2]
输出3
解释可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘则只能采摘 [0,1] 这两棵树。思考水果篮只能装单一类型水果。这道题可以抽象一下最多只能有两种不同的数据问最多的nums范围。可以用双指针法在两个指针的中间最多只能有两种数据。遇到另一种数据则停止。可以用一个map来记录。
解题
我们用哈希表 cntcntcnt 维护当前窗口内的水果种类以及对应的数量用双指针 jjj 和 iii 维护窗口的左右边界。
遍历数组 fruits将当前水果 xxx 加入窗口即 cnt[x]cnt[x]cnt[x]然后判断当前窗口内的水果种类是否超过了 222 种如果超过了 222 种就需要将窗口的左边界 jjj 右移直到窗口内的水果种类不超过 222 种为止。然后更新答案即 ansmax(ans,i−j1)ans \max(ans, i - j 1)ansmax(ans,i−j1)。
遍历结束后即可得到最终的答案。
class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint, int umap;int result 0;for (int i 0, j 0; i fruits.size(); i) {umap[fruits[i]]; //记录水果种类及数量while(umap.size() 2) {int temp fruits[j];if (--umap[temp] 0) umap.erase(temp); // 当水果数量为0的时候就可以将其擦除了}result max(result, i - j 1);}return result;}
};时间复杂度O(n)空间复杂度O(1)
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。思考用一个unordered_map 哈希表来记录t中所有字符的出现次数。然后用双指针在s中寻找满足条件的子串。
解题两个哈希表hs哈希表维护的是s字符串中滑动窗口中各个字符出现多少次ht哈希表维护的是t字符串各个字符出现多少次。如果hs哈希表中包含ht哈希表中的所有字符并且对应的个数都不小于ht哈希表中各个字符的个数那么说明当前的窗口是可行的可行中的长度最短的滑动窗口就是答案。
过程如下
1、遍历t字符串用ht哈希表记录t字符串各个字符出现的次数。
2、定义两个指针j和ij指针用于收缩窗口i指针用于延伸窗口则区间[j,i]表示当前滑动窗口。首先让i和j指针都指向字符串s开头然后枚举整个字符串s 枚举过程中不断增加i使滑动窗口增大相当于向右扩展滑动窗口。
3、每次向右扩展滑动窗口一步将s[i]加入滑动窗口中而新加入了s[i]相当于滑动窗口维护的字符数加一即hs[s[i]]。
4、对于新加入的字符s[i],如果hs[s[i]] ht[s[i]]说明当前新加入的字符s[i]是必需的且还未到达字符串t所要求的数量。我们还需要事先定义一个cnt变量 cnt维护的是s字符串[j,i]区间中满足t字符串的元素的个数记录相对应字符的总数。新加入的字符s[i]必需则cnt。
5、我们向右扩展滑动窗口的同时也不能忘记收缩滑动窗口。因此当hs[s[j]] ht[s[j]时说明hs哈希表中s[j]的数量多于ht哈希表中s[j]的数量此时我们就需要向右收缩滑动窗口j并使hs[s[j]]–即hs[s[j ]] --。
6、当cnt t.size时说明此时滑动窗口包含符串 t 的全部字符。我们重复上述过程找到最小窗口即为答案。
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar, int hs, ht;for (auto c: t) ht[c];string result;int count 0;for (int i 0, j 0; i s.size(); i) {hs[s[i]]; if (hs[s[i]] ht[s[i]]) count; //记录必须加入的字符长度while(hs[s[j]] ht[s[j]]) hs[s[j]]--; // 右移j并将hs中的计数-1if (count t.size()) { //当包含了t中所有的字符if (result.empty() || i - j 1 result.size()) result s.substr(j, i - j 1); //分割子字符串}}return result;}
};时间复杂度O(n)空间复杂度O(1)
54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。
示例 1
!https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg
输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[1,2,3,6,9,8,7,4,5]思考这道题也是一道模拟题主要考察对代码的掌控能力。
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {vectorint result;if (matrix.empty()) return result;int u 0;int d matrix.size() - 1;int l 0;int r matrix[0].size() - 1;while (true) {for (int i l; i r; i) result.push_back(matrix[u][i]);if ( u d) break;for (int i u; i d; i) result.push_back(matrix[i][r]);if (-- r l) break;for (int i r; i l; i--) result.push_back(matrix[d][i]);if (--d u) break;for (int i d; i u; i--) result.push_back(matrix[i][l]);if (l r) break;}return result;}
};复盘总结
个人反思
双指针方法yyds
模拟题的话只能是找到规律来做了。
