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)


相关推荐

  • prototype.js学习(1)

    prototype.js学习(1) 1、关于javascript的apply和call函数prototype.js中用了大量的apply和call函数,不注意会造成理解偏差。官方解释:应用某一对象的一个方法,用另一个对象替换当前对象。apply与call的区别是第二个参数不同。apply是 数组或者arguments对象。而call是逗号隔开的任何类型。apply,call方法最让人混淆的地方也是apply,call的

  • 飞在水面上的石头

    飞在水面上的石头

  • java基础-栈_java中的栈是什么

    java基础-栈_java中的栈是什么小伙伴们,你们好呀!我是老寇!栈是一种特殊的线性表,并且只能一端进行插入和删除操作本文采用链表来创建栈1.创建一个节点的类packagecn.itcast.com.istack;publicclassNode{ publicObjectdata; publicNodenext; publicNode(Objectdata){ this(data,null); } publicNode(){ this(null,null);

  • springboot事物oracle,SpringBoot 事务管理

    springboot事物oracle,SpringBoot 事务管理事务管理是项目中必不可少的一部分,使用SpringBoot时,可以很方便的配置和使用事务管理器。1.导入依赖当导入jdbc或者jpa依赖后,SpringBoot会自动分别注入DataSourceTransactionManager或JpaTransactionManager。所以我们不需要任何配置就可以使用@Transactional注解来进行事务的使用。我习惯使用jdbc,虽然Jpa有各种…

  • SpringBoot启动全流程源码解析(超详细版)[通俗易懂]

    SpringBoot启动全流程源码解析(超详细版)[通俗易懂]我们在使用SpringBoot启动项目的时候,可能只需加一个注解,然后启动main,整个项目就运行了起来,但事实真的是所见即所得吗,还是SpringBoot在背后默默做了很多?本文会通过源码解析的方式深入理解SpringBoot启动全过程SpringBoot启动过程流程图源码解析大家不要抗拒源码解析,这个非常优秀的代码,我们如果能够学会对自己代码编写水平大有裨益首先,我们先来看下SpringBoot项目的启动类@SpringBootApplicationpublicclassSp.

  • java数据导出为excel表格_将数据库表中数据导出到文本文件

    java数据导出为excel表格_将数据库表中数据导出到文本文件公司开发新系统,需要创建几百个数据库表,建表的规则已经写好放到Excel中,如果手动创建的话需要占用较长的时间去做,而且字段类型的规则又被放到了另一张表,如果手动去一个一个去匹配就很麻烦,所以我先把两张表都导入数据库中,建表的数据如下:其中字段类型被存放到了另一个表中,根据字段的code从另一表去取字段类型:然后通过java程序的方式,从数据库中取出数据自动生成建表语句,代码如下:(主要是提供思路,对于不同的建表规则不能完全适用,SQL语句为oracle数据库SQL语句)importjava.i

发表回复

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

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