分组循环A

模板

i = 0
while(i<n){start = iwhile( i<n && check(args) ) {i+=1}
}

1. LC 3011 判断一个数组是否可以变为有序

这题我比赛时用的并查集。看灵神视频学了个分组循环的做法。

对于每个分组，如果可以交换，则扩展分组的窗口，直至达到尽头或者不能交换为止。这样这个分组里的数都是可以任意交换的，因此就可以对这个分组进行排序。对每个分组排序后如果能使得整个数组有序，那么就成功。

import java.util.Arrays;class Solution {public boolean canSortArray(int[] nums) {int i = 0;int start;int n = nums.length;while(i<n){start = i;while(i<n && check(nums[start],nums[i])){i++;}Arrays.sort(nums,start,i);}return inOrder(nums);}private boolean check(int num1,int num2){return Integer.bitCount(num1)==Integer.bitCount(num2);}private boolean inOrder(int[] nums){for (int i = 1; i < nums.length; i++) {if(nums[i-1]>nums[i]){return false;}}return true;}
}

2. LC 1446 连续字符

入门题。分组记录每个连续字符子串长度，维护最大值。

class Solution {public int maxPower(String s) {char[] ch = s.toCharArray();int i = 0;int n = ch.length;int max = 0;while(i<n){char c = ch[i];int start = i;while(i<n&&ch[i]==c){i++;}max = Math.max(max,i-start);}return max;}
}

3. LC 1869 哪种连续子字符串更长

入门题。分组记录0/1子串长度，维护最大值，最后比较。

class Solution {public boolean checkZeroOnes(String s) {int max0 = 0;int max1 = 1;char[] ch = s.toCharArray();int i = 0;int n = ch.length;while(i< n){int start = i;char c = ch[i];boolean which = c =='1';while(i<n && c == ch[i]){i++;}if(which){max1 = Math.max(max1,i-start);}else{max0 = Math.max(max0,i-start);}}return max1>max0;}
}

4. LC 1957 删除字符使字符串变好

入门题。分组检查连续相同子串长度，超过2就缩减到2，拼到答案里即可。

class Solution {public String makeFancyString(String s) {char[] ch = s.toCharArray();StringBuilder sb = new StringBuilder();int i = 0;int n = ch.length;while(i<n){int start = i;while(i<n && ch[start]==ch[i]){i++;}int cnt = Math.min(2,i-start);sb.append(String.valueOf(ch[start]).repeat(cnt));}return sb.toString();}
}

5. LC 2110 股票平滑下跌阶段的数目

入门题。分组查询每段平滑下跌阶段。贡献是(l+1)*l/2（等差数列），累加即可。

class Solution {public long getDescentPeriods(int[] prices) {int i = 0;int start;int n = prices.length;long ans = 0;while(i<n){start = i;while(i<n-1 && prices[i]==prices[i+1]+1 ){i++;}int cnt = i-start+1;ans += (long) (cnt + 1) *cnt/2;i++;}return ans;}
}

6. LC 2765 最长交替子数组

每日一题+入门题。分组查询交替子数组长度，维护最大值

class Solution {public int alternatingSubarray(int[] nums) {int n = nums.length;int max = -1;int i = 0;int start;while(i<n){start = i;int diff = 1;while(i<n-1 && nums[i+1]-nums[i]==diff){diff *= -1;i++;}if(i>start){max = Math.max(max,i-start+1);}if(!(i>start)){i++;}}return max;}
}