包装纸箱公司怎么做网站,谷歌网站排名,品牌建设之道,北京网站建设需要花多少钱算法刷题
209. 长度最小的子数组-二分或者滑动窗口
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度**。**如果不存在符合条件的子数…算法刷题
209. 长度最小的子数组-二分或者滑动窗口
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度**。**如果不存在符合条件的子数组返回 0
思路
二分
因为数据都是大于0的因此数组的前缀和数组是单调增的
我们遍历每一个元素二分去小最小的满足s[r]-s[l-1]target的位置即可。
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
或者 滑动窗口
维护一个变量sum,记录区间的和
两个指针l,r 指向区间的尾巴和头部每次迭代将nums[r]加入到sum中
如果满足sumtarget了更新res,并且指针l右移直到不满足sumtarget
代码
二分 int minSubArrayLen(int target, vectorint nums) {int res1e6;int nnums.size();vectorint s(n10);for(int i1;in;i) s[i]s[i-1]nums[i-1];for(int i1;in;i){int li,rn;while(lr){int m(lr)1;if(s[m]-s[i-1]target) rm;else lm1;}if(s[l]-s[i-1]target){resmin(res,l-i1);}}if(res1e6) res0;return res;}滑动窗口 int minSubArrayLen(int target, vectorint nums) {int res1e6;int l0,r0;int sum0;int nnums.size();for(;rn;r){sumnums[r];while(sumtarget) resmin(res,r-l1),sum-nums[l];}if(res1e6) res0;return res;}904. 水果成篮-滑动窗口
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果
你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。
给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。
思路
滑动窗口 定义两个指针指向区间的开始和结尾
开一个哈希表来记录区间内每个元素出现的次数
如果哈希表的长度大于2了那么就从左边开始删
注意当哈希表内没有这个元素的时候需要删除key
代码 int totalFruit(vectorint fruits) {int n fruits.size();mapint, int mp;int l 0, res 0;for (int r 0; r n; r) {mp[fruits[r]];while (mp.size() 2) {auto it mp.find(fruits[l]);it-second--;if (mp[fruits[l]] 0) mp.erase(it);l;}res max(res, r - l 1);}return res;}76. 最小覆盖子串-滑动窗口
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
思路
滑动窗口
开两个哈希表tt记录t中每个字符出现的次数ss记录窗口中每个字符出现的次数
遍历字符串的右端点每次去check是不是满足tt的字符包含于ss的字符个数。
如果满足那么就可以不断缩小左端点更新答案
时间复杂度为 O ( 26 n ) O(26n) O(26n)
代码 string minWindow(string s, string t) {int n s.size();mapint, int tt, ss;for (char c: t) tt[c];int len 1e6, ansL -1;int l 0, r -1;auto check []() - bool {for (auto [x, y]: tt) {if (ss[x] y) return false;}return true;};while (r n) {if (tt.find(s[r]) ! tt.end()) ss[s[r]];while (check() l r) {if (r - l 1 len) {len r - l 1;ansL l;}if (tt.find(s[l]) ! tt.end()) ss[s[l]]--;l;}}string res ;if (ansL ! -1) res s.substr(ansL, len);return res;}59. 螺旋矩阵 II-模拟
给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思路
按照题目模拟即可
代码
vectorvectorint generateMatrix(int n) {int l0,rn-1,bn-1,t0;vectorvectorint res(n,vectorint(n));int num1,tarn*n;while(numtar){for(int il;ir;i) res[t][i]num;t;for(int it;ib;i) res[i][r]num;r--;for(int ir;il;i--) res[b][i]num;b--;for(int ib;it;i--) res[i][l]num;l;}return res;}54. 螺旋矩阵-模拟
给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。
输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[1,2,3,6,9,8,7,4,5]输入matrix [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出[1,2,3,4,8,12,11,10,9,5,6,7]思路
模拟。
代码 vectorint spiralOrder(vectorvectorint matrix) {int nmatrix.size(),mmatrix[0].size();vectorint res;int l0,rm-1,t0,bn-1;int sumn*m;while(sum){for(int il;ir;i) res.push_back(matrix[t][i]),sum--;if(tb) break;for(int it;ib;i) res.push_back(matrix[i][r]),sum--;if(--rl) break;for(int ir;il;i--) res.push_back(matrix[b][i]),sum--;if(--bt) break;for(int ib;it;i--) res.push_back(matrix[i][l]),sum--;if(lr) break;}return res;}LCR 146. 螺旋遍历二维数组-模拟
给定一个二维数组 array请返回「螺旋遍历」该数组的结果。
螺旋遍历从左上角开始按照 向右、向下、向左、向上 的顺序 依次 提取元素然后再进入内部一层重复相同的步骤直到提取完所有元素。
示例 1
输入array [[1,2,3],[8,9,4],[7,6,5]]
输出[1,2,3,4,5,6,7,8,9]示例 2
输入array [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]思路
模拟
代码 vectorint spiralArray(vectorvectorint a) {vectorint res; if(a.empty()) return res;int na.size(),ma[0].size();int l0,t0,rm-1,bn-1;while(1){for(int il;ir;i) res.push_back(a[t][i]);if(tb) break;for(int it;ib;i) res.push_back(a[i][r]);if(--rl) break;for(int ir;il;i--) res.push_back(a[b][i]);if(--bt) break;for(int ib;it;i--) res.push_back(a[i][l]);if(lr) break;}return res;}
