“分组循环“方式来对数组完成一次遍历【解题模板带你减少一半coding时间】
2024-01-08 20:39:36
1 总结
1.1 为什么要对数组进行分组处理？
官解的代码是我之前讲周赛时提到的「分组循环」。这个写法的好处是，（1）无需特判 nums 是否为空，（2）也无需在循环结束后，再补上处理最后一段区间的逻辑。以我的经验，（3）这种写法是所有写法中最不容易出 bug 的，（4）代码行数也很少 ， 推荐大家记住。
适用场景：按照题目要求，数组会被分割成若干段，且每一段的判断/处理逻辑是一样的。
注：虽然代码写的是一个二重循环，但 i += 1 这句话至多执行 nnn 次，所以总的时间复杂度仍然是 O(n) 的。
1.2 泛化的模板
i, n = 0, len(nums)
while i < n:
start = i
// 为什么是n-1而不是小于n呢？为了避免出现nums[i]指针异常
while i < n-1 and ...:
i += 1
# 从 start 到 i-1 是一段
# 下一段从 i 开始
i+=1
1.3 经典例题：LC228. 汇总区间
1.3.1 传统解法
public List<String> summaryRanges(int[] nums) {
List<String>ans=new ArrayList<>();
int n=nums.length;
// 对应缺点（1）
if(n==0)return ans;
StringBuilder sb=new StringBuilder();
sb.append(nums[0]+"->");
int first=0;
for(int i=1;i<n;i++){
if(nums[i]!=nums[i-1]+1){
sb.append(nums[i-1]);
ans.add(sb.toString());
sb=new StringBuilder();
sb.append(nums[i]+"->");
}
}
// 后处理步骤1：缺点（2）
sb.append(nums[n-1]);
ans.add(sb.toString());
// 后处理步骤2：统一的标准删除多余的end端点，需要进行后处理，对应缺点（2），（3），（4）
for(int i=0;i<ans.size();i++){
String str=ans.get(i);
String ss[]=str.split("->");
ans.set(i, ss[0].equals(ss[1])?ss[0]:str);
}
return ans;
}
1.3.2 分组循环解法：
public List<String> summaryRanges(int[] nums) {
List<String>ans=new ArrayList<>();
int n=nums.length;
int i=0;
StringBuilder sb=new StringBuilder();
int start=0;
while(i<n){
start=i;
while(i<n-1&&nums[i]+1==nums[i+1])i++;
String str=String.valueOf(nums[start]);
if(start<i){
str+="->"+nums[i];
}
ans.add(str);
i+=1;
}
return ans;
}
1.4 应用场景
总结一下：一般使用场景是数组或字符串前后有关联的情况，使用两个指针找到满足条件的闭区间[start, i]，然后根据题意来更新结果ans。 有一个注意点：那就是数字比较大的相乘记得要先转long
2 用"分组循环"解决面试经典题
2.1 LC468. 验证IP地址
class Solution {
public String validIPAddress(String ip) {
if (ip.indexOf(".") >= 0 && check4(ip)) return "IPv4";
if (ip.indexOf(":") >= 0 && check6(ip)) return "IPv6";
return "Neither";
}
boolean check4(String ip) {
int n = ip.length(), cnt = 0;
char[] cs = ip.toCharArray();
for (int i = 0; i < n && cnt <= 3; ) {
// 找到连续数字段，以 x 存储
int j = i, x = 0;
while (j < n && cs[j] >= '0' && cs[j] <= '9' && x <= 255) x = x * 10 + (cs[j++] - '0');
// 非 item 字符之间没有 item
if (i == j) return false;
// 含前导零 或 数值大于 255
if ((j - i > 1 && cs[i] == '0') || (x > 255)) return false;
i = j + 1;
if (j == n) continue;
// 存在除 . 以外的其他非数字字符
if (cs[j] != '.') return false;
cnt++;
}
// 恰好存在 3 个不位于两端的 .
return cnt == 3 && cs[0] != '.' && cs[n - 1] != '.';
}
boolean check6(String ip) {
int n = ip.length(), cnt = 0;
char[] cs = ip.toCharArray();
for (int i = 0; i < n && cnt <= 7; ) {
int j = i;
while (j < n && ((cs[j] >= 'a' && cs[j] <= 'f') || (cs[j] >= 'A' && cs[j] <= 'F') || (cs[j] >= '0' && cs[j] <= '9'))) j++;
// 非 item 字符之间没有 item 或 长度超过 4
if (i == j || j - i > 4) return false;
i = j + 1;
if (j == n) continue;
// 存在除 : 以外的其他非数字字符
if (cs[j] != ':') return false;
cnt++;
}
// 恰好存在 7 个不位于两端的 :
return cnt == 7 && cs[0] != ':' && cs[n - 1] != ':';
}
}
作者：宫水三叶
链接：https://leetcode.cn/problems/validate-ip-address/solutions/1523921/by-ac_oier-s217/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.2 LC71 简化路径：https://leetcode.cn/problems/simplify-path/description/
虽然下面的代码不是标准的“分组循环”的模板，但其思路也是差不多的，只不过是因为可以通过正则表达式预先匹配，确定性的知道所有分组，而在1.3 题目中，我们只能通过边遍历边感知子分组的边界
class Solution {
public String simplifyPath(String path) {
String[] names = path.split("/");
Deque<String> stack = new ArrayDeque<String>();
for (String name : names) {
if ("..".equals(name)) {
if (!stack.isEmpty()) {
stack.pollLast();
}
} else if (name.length() > 0 && !".".equals(name)) {
stack.offerLast(name);
}
}
StringBuffer ans = new StringBuffer();
if (stack.isEmpty()) {
ans.append('/');
} else {
while (!stack.isEmpty()) {
ans.append('/');
ans.append(stack.pollFirst());
}
}
return ans.toString();
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/simplify-path/solutions/1193258/jian-hua-lu-jing-by-leetcode-solution-aucq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3 大量练习：2 lc上其他的类似例题，大家可以在lc上搜索对应的题号进行练习
1446. 连续字符
1869. 哪种连续子字符串更长
1957. 删除字符使字符串变好
2038. 如果相邻两个颜色均相同则删除当前颜色
1759. 统计同质子字符串的数目
2110. 股票平滑下跌阶段的数目
1578. 使绳子变成彩色的最短时间
1839. 所有元音按顺序排布的最长子字符串
2760. 最长奇偶子数组
2765. 最长交替子序列
3.1 LC 1446. 连续字符
class Solution {
public int maxPower(String s) {
int n=s.length();
int start=0;
int i=0,ans=0;
while(i<n){
start=i;
while(i<n-1&&s.charAt(i)==s.charAt(i+1)){
i++;
}
ans=Math.max(ans,i-start+1);
i+=1;
}
return ans;
}
}
3.2 LC1869. 哪种连续子字符串更长(参考3.4)
class Solution {
public boolean checkZeroOnes(String s) {
int n=s.length();
int start=0;
int i=0;
int cnt0=0;
int cnt1=0;
while(i<n){
start=i;
while(i<n-1&&s.charAt(i)==s.charAt(i+1)){
i++;
}
if(s.charAt(start)=='0'){
cnt0=Math.max(cnt0,i-start+1);
}else{
cnt1=Math.max(cnt1,i-start+1);
}
i+=1;
}
return cnt1>cnt0;
}
}
3.3 LC1957. 删除字符使字符串变好
class Solution {
public String makeFancyString(String s) {
int n=s.length();
int i=0,start=0;
StringBuilder sb=new StringBuilder();
while(i<n){
start=i;
while(i<n-1&&s.charAt(i)==s.charAt(i+1)){
i++;
}
if(start==i){
sb.append(s.charAt(i));
}else{
sb.append(s.substring(start,start+2));
}
i++;
}
return sb.toString();
}
}
3.4 LC2038. 如果相邻两个颜色均相同则删除当前颜色（3.2 LC1869.的进阶版）
public boolean winnerOfGame(String colors) {
int n=colors.length();
int i=0,start=0;
int cnt0=0,cnt1=0;
while(i<n){
start=i;
while(i<n-1&&colors.charAt(i)==colors.charAt(i+1)){
i++;
}
if(i-start>=2&&colors.charAt(start)=='A'){
cnt0+=i-start-1;
}else if(i-start>=2&&colors.charAt(start)=='B'){
cnt1+=i-start-1;
}
i++;
}
return cnt0>cnt1;
}
3.5 【经典】LC1759. 统计同质子字符串的数目
3.5.1 采用传统的遍历方式
class Solution {
public int countHomogenous(String s) {
//预处理
if(s.length()==0)return 0;
final int MOD = 1000000007;
long res = 0;
char prev = s.charAt(0);
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 有if-else分支，更难理解
if (c == prev) {
cnt++;
} else {
res += (long) (cnt + 1) * cnt / 2;
cnt = 1;
prev = c;
}
}
// 多出后处理部分
res += (long) (cnt + 1) * cnt / 2;
return (int) (res % MOD);
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/count-number-of-homogenous-substrings/solutions/2031869/tong-ji-tong-gou-zi-zi-fu-chuan-de-shu-m-tw5m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3.5.2 采用分组循环方式处理
public int countHomogenous(String s) {
int n=s.length();
int mod=1000000007;
int i=0,start=0;
// 使用map记录某一个字符串出现了多少次
long ans=0l;
while(i<n){
start=i;
while(i<n-1&&s.charAt(i)==s.charAt(i+1)){
i++;
}
int len=i-start+1;
ans+=(long)len*(len+1)/2;
i++;
}
return (int)(ans%mod);
}
3.5.3 滑动窗口【问：为什么滑动窗口也不需要后处理？】
private static final int MOD = 1_000_000_007;
public int countHomogenous(String s) {
int n = s.length();
int left = 0;
int right = 0;
int res = 0;
while (right < n) {
if (s.charAt(left) != s.charAt(right)) {
left = right;
}
res = (res % MOD + (right - left + 1) % MOD) % MOD;
right++;
}
return res;
}
3.6 LC2110. 股票平滑下跌阶段的数目【同LC1759这道题目】
class Solution {
public long getDescentPeriods(int[] prices) {
int n=prices.length;
int i=0;
int start=0;
long ans=0;
while(i<n){
start=i;
while(i<n-1&&prices[i]-1==prices[i+1]){
i++;
}
int len=i-start+1;
ans+=(long)(len+1)*len/2;
i++;
}
return ans;
}
}
3.7 LC1578. 使绳子变成彩色的最短时间
3.7.1 解法一
class Solution {
public int minCost(String colors, int[] neededTime) {
int n=colors.length();
int i=0,start=0,ans=0;
while(i<n){
start=i;
while(i<n-1&&colors.charAt(i)==colors.charAt(i+1)){
i++;
}
int len=i-start+1;
if(len>1){
int sum=0;
int max=Integer.MIN_VALUE;
for(int j=start;j<=i;j++){
sum+=neededTime[j];
max=Math.max(max,neededTime[j]);
}
ans+=sum-max;
}
i++;
}
return ans;
}
}
3.7.2 解法二：使用”稍带确认“对3.7.1的代码改进
class Solution {
public int minCost(String colors, int[] neededTime) {
int i = 0, len = colors.length();
int ret = 0;
while (i < len) {
char ch = colors.charAt(i);
int maxValue = 0;
int sum = 0;
while (i < len && colors.charAt(i) == ch) {
maxValue = Math.max(maxValue, neededTime[i]);
sum += neededTime[i];
i++;
}
ret += sum - maxValue;
}
return ret;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/minimum-time-to-make-rope-colorful/solutions/440327/bi-mian-zhong-fu-zi-mu-de-zui-xiao-shan-chu-chen-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3.7.3 拓展:如果将"Bob 可以从绳子上移除一些气球使绳子变成 彩色"改成"Bob 可以从绳子上将重复一些气球变成其他不同颜色,但是这些颜色必须是绳子中出现过的",将如何解决这个问题?
3.8 LC1839. 所有元音按顺序排布的最长子字符串
3.8.1 方法一：利用分组循环模板, beat10%
class Solution {
public int longestBeautifulSubstring(String word) {
int n=word.length();
// 给每个字符分配一个优先级
int[]mp=new int[26];
mp['a'-'a']=0;
mp['e'-'a']=1;
mp['i'-'a']=2;
mp['o'-'a']=3;
mp['u'-'a']=4;
int i=0,start=0;
int ml=0;
while(i<n){
start=i;
Set<Character>set=new HashSet<>();
set.add(word.charAt(start));
while(i<n-1&&mp[word.charAt(i)-'a']<=mp[word.charAt(i+1)-'a']){
i++;
set.add(word.charAt(i));
}
if(set.size()==5){
ml=Math.max(ml,i-start+1);
}
i++;
}
return ml;
}
}
3.8.2 方法二(借鉴了3.8.3)：利用aeiou的自然排序特性比较优先级,同时在窗口向右滑动时确定种类而不需要借助set, 时间性能由beat10%提升到beat70%
public int longestBeautifulSubstring(String word) {
int n=word.length();
int i=0,start=0;
int ml=0;
while(i<n){
start=i;
int type=1;
while(i<n-1&&word.charAt(i)<=word.charAt(i+1)){
if(word.charAt(i)<word.charAt(i+1)){
type++;
}
i++;
}
if(type==5){
ml=Math.max(ml,i-start+1);
}
i++;
}
return ml;
}
3.8.3 方法三: 利用滑动窗口
class Solution {
public int longestBeautifulSubstring(String word) {
int ans = 0, type = 1, len = 1;
for(int i = 1; i < word.length(); i++){
if(word.charAt(i) >= word.charAt(i-1)) len++; //更新当前字符串长度
if(word.charAt(i) > word.charAt(i-1)) type++; //更新当前字符种类
if(word.charAt(i) < word.charAt(i-1)) { type = 1; len = 1;} //当前字符串不美丽，从当前字符重新开始
if(type == 5) ans = Math.max(ans, len); //更新最大字符串
}
return ans;
}
}
作者：Alan
链接：https://leetcode.cn/problems/longest-substring-of-all-vowels-in-order/solutions/742769/pan-duan-zi-fu-chong-lei-he-da-xiao-by-a-xfmd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3.8.4 拓展: 如果这个题改成子序列怎么做？
1 分析
本变种可以参考 LC300. 最长递增子序列, 与LC300不同的是,本改编题多了一个"这个子序列必须包含aeiou这五个元音字母"
2 代码
3.9 LC2760. 最长奇偶子数组（参考3.10的解法，都保证了分组循环内合法的起点）
基于此，我们容易想到：找到所有的合法左端点 i，并统计该合法左端点的最远右端点 j。跳过 [i,j]之间的点作为左端点的情况，直接从结束位置 j 开始找下一个合法左端点。
class Solution {
public int longestAlternatingSubarray(int[] nums, int threshold) {
int n=nums.length;
int i=0, start=0;
int ml=0;
while(i<n){
start=i;
// 找到所有的合法左端点 i, 在这个范围内进行查找和更新
if(nums[i]%2==0&&nums[i]<=threshold){
while(i<n-1&&nums[i]%2!=nums[i+1]%2&&nums[i+1]<=threshold){
i++;
}
ml=Math.max(ml, i-start+1);
}
i++;
}
return ml;
}
}
3.10 LC2765. 最长交替子序列（参考3.9的解法，都保证了分组循环内合法的起点），这也算是一种滑动窗口的解法
class Solution {
public int alternatingSubarray(int[] nums) {
int n=nums.length;
int i=0;
int start=0;
int ml=-1;
while(i<n){
start=i;
// 首先保证起点是合法的，找到所有的合法左端点 i
if(i<n-1&&nums[i+1]-nums[i]==1){
int prev=0;
while(i<n-1&&Math.abs((nums[i+1]-nums[i]))==1&&(prev==0||(nums[i+1]-nums[i])*prev==-1)){
prev=nums[i+1]-nums[i];
i++;
}
if(i>start){
ml=Math.max(ml,i-start+1);
continue;
}
}
i++;
}
return ml;
}
}
4 "分组循环"和"滑动窗口or双指针"解法的关系
4.1 和双指针的区别
从+=1 的角度来说，其实只有一个指针在移动，其左侧边界固定，但是滑动窗口的左侧边界也是需要动态更新的，start 只是保存了 i 的一个快照，和一般的双指针还是有区别的。
4.2 能不能用“分组循环”的板子解决滑动窗口问题？【答案是不能，因为分组循环的左边界确定不变，但是滑动窗口的左边界需要动态更新！可以看一下分析】
4.2.1 尝试一下LC3. 无重复字符的最长子串
1 滑动窗口解法
class Solution {
// 滑动窗口解法
public int lengthOfLongestSubstring2(String s) {
int n=s.length();
Map<Character,Integer>mp=new HashMap<>();
int l=-1,ans=0;
for(int i=0;i<n;i++){
char c=s.charAt(i);
if(mp.containsKey(c)){
l=Math.max(l,mp.get(c));
}
ans=Math.max(ans, i-l);
mp.put(c, i);
}
return ans;
}
}
2 尝试用分组循环解决这个“滑动窗口“问题：无法通过case-“dvdf”
public int lengthOfLongestSubstring(String s) {
int n=s.length();
int i=0,ans=0,start=0;
int l=0;
int[]set=new int[128];
Arrays.fill(set,-1);
while(i<=n){
start=i;
while(i<n&&set[s.charAt(i)]==-1){
set[s.charAt(i)]=i;
i++;
}
ans=Math.max(ans,i-l);
if(i<n){
System.out.println("i:"+i+", l:"+l+", s.charAt(l):"+s.charAt(l)+", "+s.charAt(i)+",ans:"+ans);
set[s.charAt(i)]=i;
l=Math.max(l,set[s.charAt(i)]);
}
i++;
}
return ans;
}
文章来源:https://blog.csdn.net/yxg520s/article/details/135413393
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！