题目地址:https://leetcode.com/problems/max-consecutive-ones/description/

题目描述

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

示例 1:

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.

注意:

  1. 输入的数组只包含 0 和1。
  2. 输入数组的长度是正整数,且不超过 10,000。

解题思路

设定一个计数器num和最大连续个数maxNum, 然后开始遍历整个数组。遇到1则计数器累加;遇到0时,将当前的计数器num和最大连续个数maxNum比较,取其中较大的,然后将当前计数器num清零。继续往后遍历,直到最后取nummaxNum中较大的返回。

通过代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
maxNum = 0
num = 0
for i in nums:
if i == 1:
num += 1
else:
if num > maxNum:
maxNum = num
num = 0
return max(num, maxNum)

方法二

将数组nums=[1,1,0,1,1,1]转化为字符串str_nums=’101101’,然后以0为分隔符,用split对字符串str_nums切片,获得分割后的字符串列表,统计出最多1的长度。

1
2
3
4
def findMaxConsecutiveOnes(self, nums):
num_str = ''.join(map(str,nums))
num_list = num_str.split('0')
return len(max(num_list))

方法三

上面是使用计数器num来实现遇到1累加,比较容易想到,下面看别人写的:

1
2
3
4
5
6
class Solution:
def findMaxConsecutiveOnes(self, nums):
for i in range(1, len(nums)):
if nums[i]:
nums[i] += nums[i - 1]
return max(nums)

从数组中的第二位开始遍历,如果第i位是0,则跳过,如果第i位是1,则将其与前一位的1相加,这样遇到连续多个1时,通过与前一个1的相加实现计数

比如输入数组: nums = [0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1]

转换后的数组: nums = [0, 1, 2, 3, 0, 1, 2, 0, 0, 1, 2, 3, 4]

最后统计出最大值,就是连续1的最多个数。