leetcode 485,487,1004. Max Consecutive Ones I ,II, III（最大连续1的个数问题合集）

墨蓝 2022-10-11 12:06 128阅读 0赞

## 485. Max Consecutive Ones ##

[https://leetcode.com/problems/max-consecutive-ones/][https_leetcode.com_problems_max-consecutive-ones]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]  
easy 题，思路不说了，直接上代码。

class Solution { 
        public int findMaxConsecutiveOnes(int[] nums) { 
            int cnt = 0;
            int max = 0;
            for (int num : nums) { 
                if (num == 0) cnt = 0;
                else max = Math.max(max, ++cnt);
            }
            return max;
        }
    }

## 487. Max Consecutive Ones II ##

力扣这题需要 plus 会员，所以，为了保证“Max Consecutive Ones”的完整性，临时用一下 lintcode。

[https://www.lintcode.com/problem/883/][https_www.lintcode.com_problem_883]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
本题思路由题目 III 加了一个条件 k=1 改编而来。

另外，lintcode 的测试用例不够全面，之前写了一个明显的 bug 但还是通过了，后来才发现，已更正。

public class Solution { 
        public int findMaxConsecutiveOnes(int[] nums) { 
            int k = 1;
            int cnt = 0;
            List<Integer> list = new ArrayList<>();
            for (int n : nums) { 
                if (n == 0) { 
                    if (cnt != 0) list.add(cnt);
                    list.add(0);
                    cnt = 0;
                } else cnt++;
            }
            if (nums[nums.length - 1] == 1) list.add(cnt);
    
            int maxSum = 0;
            for (int i = 0; i < list.size(); i++) { 
                int curSum = 0;
                int zeroCnt = 0;
                for (int j = i; j < list.size(); j++) { 
                    if (list.get(j) == 0) { 
                        if (++zeroCnt > k) break;
                        curSum++;
                    } else { 
                        curSum += list.get(j);
                    }
                }
                maxSum = Math.max(maxSum, curSum);
            }
    
            if (maxSum == 0) { 
                int zeroCnt = 0;
                for (Integer n : list) { 
                    if (n == 0) { 
                        if (++zeroCnt > k) break;
                        maxSum++;
                    } else { 
                        maxSum += n;
                    }
                }
            }
            return maxSum;
        }
    }

## 1004. Max Consecutive Ones III ##

[https://leetcode.com/problems/max-consecutive-ones-iii/][https_leetcode.com_problems_max-consecutive-ones-iii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

#### 普通思路 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

public class Solution { 
        public int longestOnes(int[] nums, int k) { 
        	// 建立辅助数组
            int cnt = 0;
            List<Integer> list = new ArrayList<>();
            for (int n : nums) { 
                if (n == 0) { 
                    if (cnt != 0) list.add(cnt);
                    list.add(0);
                    cnt = 0;
                } else cnt++;
            }
            if (nums[nums.length - 1] == 1) list.add(cnt); // 处理边界
    		// 利用辅助数组计算maxSum
            int maxSum = 0;
            for (int i = 0; i < list.size(); i++) { 
                int curSum = 0;
                int zeroCnt = 0;
                for (int j = i; j < list.size(); j++) { 
                    if (list.get(j) == 0) { 
                        if (++zeroCnt > k) break;
                        curSum++;
                    } else { 
                        curSum += list.get(j);
                    }
                }
                maxSum = Math.max(maxSum, curSum);
            }
    		// 独立处理因数组长度不足而无法进入for循环的情况
            if (maxSum == 0) { 
                int zeroCnt = 0;
                for (Integer n : list) { 
                    if (n == 0) { 
                        if (++zeroCnt > k) break;
                        maxSum++;
                    } else { 
                        maxSum += n;
                    }
                }
            }
            return maxSum;
        }
    }

#### 进阶思路：滑动窗口 ####

思路参考：[https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/hua-dong-chuang-kou-de-liang-chong-jie-j-8ses/][https_leetcode-cn.com_problems_max-consecutive-ones-iii_solution_hua-dong-chuang-kou-de-liang-chong-jie-j-8ses]

双指针法，时间复杂度O(n)。

public int longestOnes(int[] A, int K) { 
        int left = 0;//窗口左边的位置
        int right = 0;//窗口右边的位置
        int zeroCount = 0;//窗口中0的个数
        for (; right < A.length; right++) { 
            if (A[right] == 0) { 
                zeroCount++;
            }
            //如果窗口中0的个数超过了K，要缩小窗口的大小
            if (zeroCount > K && A[left++] == 0)
                zeroCount--;
        }
        return right - left;
    }

[https_leetcode.com_problems_max-consecutive-ones]: https://leetcode.com/problems/max-consecutive-ones/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/ca164b45426549849ecf2bd1c81efb20.png
[https_www.lintcode.com_problem_883]: https://www.lintcode.com/problem/883/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/1daa17bb75134eebaf30693168d1d622.png
[https_leetcode.com_problems_max-consecutive-ones-iii]: https://leetcode.com/problems/max-consecutive-ones-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/04f62f8866ba4804b259b0b7e1f51c01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/d8083de8d903496d8ecbad25a65993ff.png
[https_leetcode-cn.com_problems_max-consecutive-ones-iii_solution_hua-dong-chuang-kou-de-liang-chong-jie-j-8ses]: https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/hua-dong-chuang-kou-de-liang-chong-jie-j-8ses/