leetcode1293_leetcode第一题

leetcode1293_leetcode第一题【leetcode】1004. Max Consecutive Ones III

大家好,又见面了,我是你们的朋友全栈君。

题目如下:

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. 

 

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. 

 

Note:

  1. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i] is 0 or 1 

解题思路:如果我们把所有0所在位置对应的下标存入一个数组inx_0中,例如Example 2的inx_0 = [0,1,4,5,9,12,13,14],因为最多把K个0变成1,要构造出最长的全为1的连续子数组,那么很显然所有进行反转操作的0所对应下标在inx_0中必须是连续的。接下来开始遍历数组A,在K大于0的条件下,遇到1则count_1加1,遇到0的话则K减1并且count_1加1(表示这个0反转成1);如果在K=0的情况下遇到0,那么需要去掉第一个0变成的1和这个0之前连续的1的数量,即count减1(减去第一个0变成1的计数),再减去第一个0前面连续的1的数量i,记为count_1减i。记录count_1出现的最大值,直到数组A遍历完成为止。

代码如下:

class Solution(object):
    def longestOnes(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        count_1 = 0
        zero_inx = []
        res = 0
        zero_before = -1
        for i in range(len(A)):
            if A[i] == 1:
                count_1 += 1
            else:
                zero_inx.append(i)
                if K > 0:
                    K -= 1
                    count_1 += 1
                elif K == 0:
                    res = max(res,count_1)
                    first_0 = zero_inx.pop(0)
                    count_1 -= (first_0 - zero_before - 1)
                    zero_before = first_0
        res = max(res, count_1)
        return res

 

转载于:https://www.cnblogs.com/seyjs/p/10469180.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/106957.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号