美文网首页
Day50: 连续数组

Day50: 连续数组

作者: 快乐的老周 | 来源:发表于2020-07-21 16:50 被阅读0次

    给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组(的长度)。

    示例 1:

    输入: [0,1]

    输出: 2

    说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

    示例 2:

    输入: [0,1,0]

    输出: 2

    说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

    注意: 给定的二进制数组的长度不会超过50000。

    补充下面代码

    class Solution(object):

       # def findMaxLength(self, nums):
              # pass
    

    来源: https://leetcode-cn.com/problems/contiguous-array/

    class Solution(object):
    def findMaxLength(self, nums):
    max_len = 0
    for index, num in enumerate(nums):
    if num == 0:
    nums[index] = -1

        # 暴力法
        if len(nums) <2 :return 0 # 仅零或一个元素,返回0
        for i in range(len(nums)):
            for j in range(1, len(nums)+1):
                if sum(nums[i:j+1]) ==0:
                    if j-i > max_len:
                        max_len = j-i+1
        return max_len
    
    def findMaxLength1(self, nums):
        max_len , count = 0, 0
        d = {0:-1}
        for index, num in enumerate(nums):
            if num == 0:
                count += -1
            if num ==1:
                count += 1
            if count in d:
                max_len = max(max_len, index - d[count])
            else:
                d[count] = index
        return max_len
    

    def test_findMaxLength():
    s = Solution()
    nums = [0,1]
    assert s.findMaxLength(nums) == 2
    nums = [0,1,0]
    assert s.findMaxLength(nums) == 2
    nums = [0,1,0,1,0,1]
    assert s.findMaxLength(nums) == 6
    nums = [0,1,0,1,0,1, 1]
    assert s.findMaxLength(nums) == 6
    nums = [0,1,0,1,0,1,1,1,1,1,0,0,0,0,0]
    assert s.findMaxLength(nums) == 14
    nums = [1,1,1,1,1,1,1,1]
    assert s.findMaxLength(nums) == 0

    nums = [0,1]
    assert s.findMaxLength1(nums) == 2
    nums = [0,1,0]
    assert s.findMaxLength1(nums) == 2
    nums = [0,1,0,1,0,1]
    assert s.findMaxLength1(nums) == 6
    nums = [0,1,0,1,0,1, 1]
    assert s.findMaxLength1(nums) == 6
    nums = [0,1,0,1,0,1,1,1,1,1,0,0,0,0,0]
    assert s.findMaxLength1(nums) == 14
    nums = [1,1,1,1,1,1,1,1]
    assert s.findMaxLength1(nums) == 0
    

    相关文章

      网友评论

          本文标题:Day50: 连续数组

          本文链接:https://www.haomeiwen.com/subject/gwmbkktx.html