常德网站建设的策划方案,免费开源的cms,虚拟主机手机网站,遵义在线网站建设【算法系列总结之分组循环篇】 分组循环1446.连续字符1869.哪种连续子字符串更长1957.删除字符使字符串变好2038.如果相邻两个颜色均相同则删除当前颜色1759.统计同质子字符串的数目2110.股票平滑下跌阶段的数目1578.使绳子变成彩色的最短时间1839.所有元音按顺序排布的最长子字… 【算法系列总结之分组循环篇】 分组循环1446.连续字符1869.哪种连续子字符串更长1957.删除字符使字符串变好2038.如果相邻两个颜色均相同则删除当前颜色1759.统计同质子字符串的数目2110.股票平滑下跌阶段的数目1578.使绳子变成彩色的最短时间1839.所有元音按顺序排布的最长子字符串2760.最长奇偶子数组2765.最长交替子序列228.汇总区间 分组循环
分组循环指的是将整个数组或者字符串分为很多片段这些片段的判断处理逻辑是一样的。分组循环需要使用同向双指针但是与滑动窗口不同的是滑动窗口是收集左右区间内连续数组或者字符串当不满足收集要求时移动右指针而当满足后移动左指针此时左指针移动到原来左指针的下一位而分组循环是左指针移动到右指针下一位。
// 模板 l、r分别表示左右指针int l0,r0;while(rn){// 每一次求新区间则重新赋值llr;// r表示最长连续区间最后一个while(rn-1s[r]s[r1])r;// 求完区间后收集结果resmax(r-l1,res);// 并移动r到下一个r;}1446.连续字符
思路分组循环相当于把字符串分为多个连续相同字符片段利用左右端点l、r求解最长连续相同字符片段长度。
class Solution {
public:int maxPower(string s) {int ns.size();int l0,r0;int res0;while(rn){// 每一次求新区间则重新赋值llr;// r表示最长连续区间最后一个while(rn-1s[r]s[r1])r;// 求完区间后收集结果resmax(r-l1,res);// 并移动r到下一个r;}return res;}
};1869.哪种连续子字符串更长
思路分组循环相当于把字符串分为多个连续1或者0字符片段利用左右端点l、r和元素s[l]求解最长连续1或者0字符片段长度再根据条件返回对应结果。
class Solution {
public:bool checkZeroOnes(string s) {// 分别记录最长1、最长0长度int num10,num00;int ns.size();// 区间左右端点int l0,r0;while(rn){// l表示每轮左区间lr;// r表示当前符合条件区间右端点while(rn-1s[r]s[r1])r;// 收集0或者1长度if(s[l]0)num0max(num0,r-l1);elsenum1max(num1,r-l1);r;}return num1num0;}
};1957.删除字符使字符串变好
思路分组循环相当于把字符串分为多个连续相同片段利用左右端点l、r求解每一个连续相同片段长度如果长度小于3则直接将该片段加入结果反之则只加入两个字符即可。
class Solution {
public:string makeFancyString(string s) {string res;int ns.size();int l0,r0;while(rn){lr;while(rn-1s[r]s[r1])r;if(r-l13)ress.substr(l,r-l1);else {// 加入两次res.push_back(s[l]);res.push_back(s[l]);}r;}return res;}
};2038.如果相邻两个颜色均相同则删除当前颜色
思路分组循环相当于把字符串分为多个连续A或者B字符片段利用左右端点l、r和元素colors[l]求解最长连续A或者B字符片段可选择的次数再根据条件返回对应结果。注意最长连续A或者B字符片段可选择的次数为在保留左右两边字符的情况下中间所有剩余字符即一旦长度大于等于3则为长度减去2反之则为0由于A是先手故A必须严格大于B。
class Solution {
public:bool winnerOfGame(string colors) {int ncolors.size();// 转换为次数int numA0,numB0;int l0,r0;while(rn){lr;while(rn-1colors[r]colors[r1])r;// 一旦3 则可移动的为长度减去左右两边2if(colors[l]A)numA(r-l1)3?(r-l1)-2:0;elsenumB(r-l1)3?(r-l1)-2:0;r;}return numAnumB;}
};1759.统计同质子字符串的数目
思路分组循环相当于把字符串分为多个连续相同片段利用左右端点l、r求解每一个连续相同片段长度然后利用1、3、6、10、15…规律根据长度n求出方案数n*(n1)/2最后累计方案数即可。
class Solution {
public:const long long NUM1e97;int countHomogenous(string s) {// 1 3 6 10 15 n*(n1)/2int ns.size();int l0,r0;// long long 避免精度不够long long res0;while(rn){lr;while(rn-1s[r]s[r1])r;int lenr-l1;// 注意取模res(long long)(len1)*len/2;r;}// 取模return res%NUM;}
};2110.股票平滑下跌阶段的数目
思路分组循环相当于把数组分为多个连续公差为1的递减片段利用左右端点l、r求解每一个连续公差为1的递减片段长度然后利用1、3、6、10、15…规律根据长度n求出方案数n*(n1)/2最后累计方案数即可。
class Solution {
public:long long getDescentPeriods(vectorint prices) {int nprices.size();int l0,r0;long long res0;while(rn){lr;// 当前日比前一日股价少一while(rn-1prices[r]prices[r1]1)r;long long lenr-l1;reslen*(len1)/2;r;}return res;}
};1578.使绳子变成彩色的最短时间
思路分组循环相当于把绳子分为多个连续相同气球片段利用左右端点l、r求解每一个连续相同气球片段并对每个大于1的片段求解总时间和最大时间从而得到最小时间对这些时间累加即可得到结果。
class Solution {
public:int minCost(string colors, vectorint neededTime) {int ncolors.size();int l0,r0;int res0;while(rn){lr;while(rn-1colors[r]colors[r1])r;if(l!r){int maxn0;for(int il;ir;i){maxnmax(neededTime[i],maxn);resneededTime[i];}res-maxn;}r;}return res;}
};1839.所有元音按顺序排布的最长子字符串
思路分组循环相当于把字符串分为多个按照元音字母递增的至少含有所有元音字母各一个的字符串与前面几题不同的是该题需要在记录符合区间的同时也使用uset来记录元音字母个数从而便于后序收集结果条件各个元音字母至少一个的判断。
class Solution {
public:int longestBeautifulSubstring(string word) {int nword.size();int l0,r0;int res0;while(rn){lr;// 存储次数 保证各个字母至少出现一次unordered_setint uset;// 按照 a e i o u顺序while(rn-1word[r1]word[r]){uset.emplace(word[r]);r;}// 加入最后一个 前几题都是只需r 不需额外处理uset.emplace(word[r]);// coutuset.size()endl;if(uset.size()5)resmax(res,r-l1);r;}return res;}
};2760.最长奇偶子数组
思路分组循环相当于把数组分为多个[l,r]区间其中求出满足题目要求的长度最长的[l,r]区间。该题与上述题目不同的地方在于该题中存在l、[l,r-1]、[l,r]三个判断由于此处的差异就会导致在处理判断边界条件时可能会出现些许差异和错误。此处首先对于l不满足的情况进行特殊处理由于已经处理过l那么后续就是在l满足条件的情况下进行此时将r加一相当于比较r和r-1而不是原先的r和r1那么相应的此处得到的r就是第一个不满足的对应的长度变为r-l同时也不需要继续对r啦。(注意细节)
class Solution {
public:int longestAlternatingSubarray(vectorint nums, int threshold) {int nnums.size();int l0,r0;int res0;while(rn){// 左区间都不满足情况直接下一个if(nums[r]%2!0||nums[r]threshold){// continue之前记得r啊否则区间不动r;continue;}// 此处才更新左区间lr;// 左区间已经满足 此时r1r1;// r是第一个不满足的 故此时长度为r-l 并且后续不需要rwhile(rnnums[r]threshold(nums[r]%2!nums[r-1]%2))r;resmax(res,r-l);}return res;}
};2765.最长交替子序列
思路分组循环相当于把数组分为多个[l,r]区间其中求出满足题目要求的长度最长的[l,r]区间。该题与2760不同的地方在于该题所分得的区间可能重叠喔比如2 3 4 3 4其中2 3和3 4 3 4其重叠一个但是其最多也只会重叠一个故我们找到第一个不满足的r后回退1即可。建议在分组循环类别的题目中遇到给区间[l,r]设置条件时先对首部条件进行不合法判断处理再继续喔
class Solution {
public:int alternatingSubarray(vectorint nums) {int nnums.size();int l0,r0;int res-1;// 数组长度至少为2while(r1n){// 排除s1!s01的情况if(nums[r1]-nums[r]!1){r;continue;}// 记录左端点lr;r1; // 右端点加一 至少长度为2int m1;// r是第一个不满足的while(rnnums[r]-nums[r-1]m){r;m*-1;}resmax(res,r-l);// 2 3 4 3 4 // 2 3和3 4 3 4重合一个 为什么能保证最多重复一个r-1; // 所以r需要回退一个}return res;}
};总结灵老师的nums[i]nums[i0(i-i0)%2]也很灵性
228.汇总区间
思路分组循环相当于把字符串分为多个连续公差为1的递增片段利用左右端点l、r求解每一个连续公差为1的递增片段两端并按照要求格式加入结果。
class Solution {
public:vectorstring summaryRanges(vectorint nums) {int nnums.size();int r0,l;string tmp;vectorstring res;// l 左端點 r右端點 同向雙指針while(rn){lr;while(rn-1nums[r]1nums[r1])r;tmpto_string(nums[l]);if(lr)tmp-to_string(nums[r]);res.push_back(tmp);r;}return res;}
};有一说一虽然现在力扣刷了四百多题牛客刷了两百多题包括前端和算法但还是觉得遇到一些脑筋急转弯的简单或者中等题还是不会对于一些题型也没有形成自己的解题思路逻辑遇到困难题也是要看题解才行除非自己刷过几次感觉好挫败啊呜呜呜呜呜呜呜呜要怎么办
