首页 > 代码库 > [LeetCode OJ]485. Max Consecutive Ones

[LeetCode OJ]485. Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

 

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

 

  大意是给一个数组,判断出连续1的个数最多的数,比如例子中,有一个两个连续的1,有一个三个连续的1,则最大数为3.数组只包含0和1,数组内数字个数不会超过10000个.

  我的思路:

    遍历数组,准备一个count变量记录连续的1的个数,一个max变量记录最大的连续个数.

    碰到连续的1中的第一个1,进入判断条件内部,计数器count开始++,并且继续往下遍历,直到遇到的不是1,则判断:count是否大于当前max的值,如果大于,则是最大的连续个数,则赋值给max,否则,继续最外层遍历,直到遇到下一个1,再次进入判断条件内部,统计连续的1的个数,如此往复.

 1 int findMaxConsecutiveOnes(int* nums, int numsSize) {
 2     int i = 0,max = 0,count=0;
 3     for(i=0;i<numsSize;i++){
 4         //遇到一个打头的1,进入判断条件内部
 5         if(nums[i] == 1){
 6             //从这个1开始计数,直到遇到0停止
 7             while(nums[i] == 1){
 8                 count++;
 9                 i++;
10             }
11             //遇到0,退出while循环,判断与max的大小,如果大于max则赋值给max,否则放弃这个count值
12             if(count > max){
13                 max = count;
14             }
15             //寻找下一个连续的1,count归零
16             count = 0;
17         }
18     }
19     return max;
20 }

 

  贴上最佳答案供参考:

 1 int findMaxConsecutiveOnes(int* nums, int numsSize) {
 2     int max = 0;
 3     int sum = 0;
 4     for (int i=0; i<numsSize; i++)
 5     {
 6         sum = (sum+nums[i])*nums[i];
 7         if(max<sum){max=sum;}
 8     }
 9     return max;
10 }

  答案描述:Use the fact that multiplication with 0 resets everything..

  个人理解:核心代码就for循环中的那两行,利用的原理就是,任何数乘以0都得0,即任何数乘以0都会归零.

       sum值一开始为0,进入遍历后,遇到1,则会变成(0 + 1) * 1 = 1.只要遇到连续的1就会一直累加,把每次累加之后的sum和max比,大于max就赋值给max,遇到a[i] = 0,sum就会归0,进行下一轮的累加.这样最后得到的max则为最大连续数.

 

 

  版权声明:本文为博主原创文章,未经博主允许不得转载。

[LeetCode OJ]485. Max Consecutive Ones