数组力扣485题---最大连续1的个数

485 最大连续 1 的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：输入：nums = [1,1,0,1,1,1] 输出：3
解释：开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
示例 2：输入：nums = [1,0,1,1,0,1] 输出：2

提示：1<=nums.length<=105 nums[i] 不是0就是1.

解题方法1 单指针 一次遍历法

public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1};
        Main solution = new Main();
        int x = solution.findMaxConsecutiveOnes(nums);
        System.out.println(x);
    }
    private static int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;//最大值 初始为0
        int count = 0;//累加值 初始为0
        for (int i : nums) {//遍历数组
            if (i == 1) {//if判断语句，对数组里的数进行判断
                count++;//对连续1进行累加
            } else {
                max = Math.max(max, count);//作比较,取当前最大个数
                count = 0;//遇到0的话就需要归零，寻找下一个连续序列，重新累加
            }
        }
        //因为最后一次连续序列在循环中无法比较，所以在循环外进行比较
        max = Math.max(max, count);//作比较,取最大的数
        return max;//返回最大的值
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解题方法2 双指针法

public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1};
        Main solution = new Main();
        int x = solution.findMaxConsecutiveOnes(nums);
        System.out.println(x);
    }
 
    private static int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;//数组长度
        int max = 0;//最大值 初始为0
 
        int i = 0, j = 0;//创建2个指针
        while (i < n && n - j > max) {//i指针先探测,见到1就住继续
            if (nums[j] == 0) {//对数组里的数进行判断,遇到0的话就跳过
                j++;//将j指针往后移动一下
                continue;
            }
            int count = 0;//累加值 初始为0
            for (i = j; i < n && nums[i] != 0; i++) {
                count++;
            }
            j = i + 1;
            max = Math.max(count, max);//作比较,取最大的数
        }
        return max;//返回最大的值
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解题方法3 暴力模拟法

从左开始往右比较，如果是1开始计数；见到0要先把前面的记录下来，然后从0重新开始。采用链表的方式存储最大值.

import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1};
        Main solution = new Main();
        int x = solution.findMaxConsecutiveOnes(nums);
        System.out.println(x);
    }
 
    private static int findMaxConsecutiveOnes(int[] nums) {
        ArrayList<Integer> max = new ArrayList<>();
        ArrayList<Integer> count = new ArrayList<>();
        for (int i : nums) {
            if (i == 1) {
                max.add(i);
                count.add(max.size());
            } else {
                max.clear();
            }
        }
        return count.size() > 0 ? Collections.max(count) : 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

解题方法4 滑动窗口法

public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1};
        Main solution = new Main();
        int x = solution.findMaxConsecutiveOnes(nums);
        System.out.println(x);
    }
 
    private static int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        int count = 0;
        while (right < n) {
            //当窗口中所有元素为 1 时，右指针向右移，扩大窗口。
            if (nums[right++] == 0) {
                //当窗口中存在 0 时，计算连续序列长度，左指针指向右指针。
                count = Math.max(count, right - left - 1);
                left = right;
            }
        }
        // 因为最后一次连续序列在循环中无法比较，所以在循环外进行比较
        return Math.max(count, right - left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

解题方法5 动态规划法

观察后得到方程，采用存储结构存储记录值，最后返回最大值。

public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1};
        Main solution = new Main();
        int x = solution.findMaxConsecutiveOnes(nums);
        System.out.println(x);
    }
 
    private static int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) {
            return 0;
        }
        nums[0] = nums[0] == 1 ? 1 : 0;
        int count = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] == 1) {
                nums[i] = nums[i - 1] + 1;
            } else {
                nums[i] = 0;
            }
            count = Math.max(count, nums[i]);
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

解题方法6 字符串分割法

将数组转为字符串，然后按0进行分割，得到所有都是1的字符串，取出最长值。

import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1};
        Main solution = new Main();
        int x = solution.findMaxConsecutiveOnes(nums);
        System.out.println(x);
    }
 
    private static int findMaxConsecutiveOnes(int[] nums) {
        String str = Arrays.toString(nums);
        String[] array = str.replace(" ", "").replace(",", "").replace("[", "").replace("]", "").split("0");
        int max = 0;
        for (String s : array) {
            if (s.length() > max) {
                max = s.length();
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22