“分组循环“方式来对数组完成一次遍历【解题模板带你减少一半coding时间】

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

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！