【数据结构和算法】最大连续1的个数 III

这篇具有很好参考价值的文章主要介绍了【数据结构和算法】最大连续1的个数 III。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一:滑动窗口

 2.2 滑动窗口解题模板

三、代码

3.1 方法一:滑动窗口

四、复杂度分析

4.1 方法一:滑动窗口


前言

这是力扣的 1004 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。

又是一道滑动窗口的典型例题,可以帮助我们巩固滑动窗口算法。

这道题很活灵活现,需要加深对题意的变相理解。


一、题目描述

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。

示例 1:

输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。

示例 2:

输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

提示:

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1
  • 0 <= k <= nums.length

二、题解

2.1 方法一:滑动窗口

思路与算法:

重点:题意转换。把「最多可以把 K 个 0 变成 1,求仅包含 1 的最长子数组的长度」转换为 「找出一个最长的子数组,该子数组内最多允许有 K 个 0 」。

经过上面的题意转换,我们可知本题是求最大连续子区间,可以使用滑动窗口方法。滑动窗口的限制条件是:窗口内最多有 K 个 0。

可以使用我多次分享的滑动窗口模板解决,模板在代码之后。

首先定义四个变量:

  1. 左指针
  2. 右指针
  3. 最长的子串长度
  4. 0 的数量

代码思路:

  1. 使用 left 和 right 两个指针,分别指向滑动窗口的左右边界。
  2. right 主动右移:right 指针每次移动一步。当 A[right] 为 0,说明滑动窗口内增加了一个 0;
  3. left 被动右移:判断此时窗口内 0 的个数,如果超过了 K,则 left 指针被迫右移,直至窗口内的 0 的个数小于等于 K 为止。
  4. 滑动窗口长度的最大值就是所求。

【数据结构和算法】最大连续1的个数 III,数据结构与算法合集,数据结构,算法,策略模式,java,开发语言,redis,inscode

2.2 滑动窗口解题模板

滑动窗口算法是一种常用的算法,用于解决数组或列表中的子数组问题。下面是一个滑动窗口算法的解题模板:

  1. 定义窗口大小:首先需要确定滑动窗口的大小,即每次滑动时包含的元素个数。
  2. 初始化窗口:将窗口的起始位置设置为0,窗口大小设置为n,其中n为数组或列表的长度。
  3. 计算窗口中的元素和:使用一个变量sum来记录当前窗口中的元素和,初始值为0。
  4. 移动窗口:从左到右依次遍历数组或列表,每次将当前元素加入窗口中,并更新sum的值。
  5. 判断是否满足条件:在移动窗口的过程中,不断判断当前窗口中的元素和是否满足题目要求。如果满足条件,则返回当前窗口中的元素和。
  6. 移动窗口:如果当前窗口中的元素和不满足题目要求,则将窗口向右移动一位,并更新sum的值。
  7. 重复步骤4-6,直到遍历完整个数组或列表。

下面是一个具体的例子,使用滑动窗口算法求解数组中连续子数组的最大和:

def maxSubArray(nums):  
    if not nums:  
        return 0  
      
    max_sum = current_sum = nums[0]  
    for i in range(1, len(nums)):  
        current_sum = max(nums[i], current_sum + nums[i])  
        max_sum = max(max_sum, current_sum)  
      
    return max_sum

在这个例子中,我们使用一个变量max_sum来记录当前最大子数组的和,一个变量current_sum来记录当前窗口中的元素和。在遍历数组的过程中,不断更新current_sum的值,并判断是否满足题目要求。如果满足条件,则更新max_sum的值。最后返回max_sum即可。


三、代码

3.1 方法一:滑动窗口

Java版本:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, right = 0, longestOnes = 0, zero = 0;
        while (right < nums.length) {
            if (nums[right] == 0) zero++;
            if (zero > k) {
                left++;
                if (nums[left - 1] == 0) zero--;
            }
            if (zero == k || right == nums.length - 1) {
                longestOnes = Math.max(right - left + 1, longestOnes);
            }
            right++;
        }
        return longestOnes;
    }
}

C++版本:

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0, longestOnes = 0, zero = 0;
        while (right < nums.size()) {
            if (nums[right] == 0) zero++;
            if (zero > k) {
                left++;
                if (nums[left - 1] == 0) zero--;
            }
            if (zero == k || right == nums.size() - 1) {
                longestOnes = max(right - left + 1, longestOnes);
            }
            right++;
        }
        return longestOnes;
    }
};

Python版本:文章来源地址https://www.toymoban.com/news/detail-763127.html

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left, right, longestOnes, zero = 0, 0, 0, 0
        while right < len(nums):
            if nums[right] == 0:
                zero += 1
            if zero > k:
                left += 1
                if nums[left - 1] == 0:
                    zero -= 1
            if zero == k or right == len(nums) - 1:
                longestOnes = max(right - left + 1, longestOnes)
            right += 1
        return longestOnes

四、复杂度分析

4.1 方法一:滑动窗口

  • 时间复杂度:O(N),因为每个元素只遍历了一次。
  • 空间复杂度:O(1),因为使用了常数个空间。

到了这里,关于【数据结构和算法】最大连续1的个数 III的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之字符串: Leetcode 557. 反转字符串中的单词 III (Typescript版)

    翻转字符串中的单词 III https://leetcode.cn/problems/reverse-words-in-a-string-iii/ 描述 给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例 1: 示例 2: 提示: 1 = s.length = 5 * 1 0 4 10^4 1 0 4 s 包含可打印的 ASCII 字符。 s 不包含任何开头或

    2024年02月01日
    浏览(74)
  • 【算法与数据结构】654、LeetCode最大二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代码可以互相参考,本题明示了要用递归来做,那么递归三要素不可缺少: 输入参数和返

    2024年02月09日
    浏览(44)
  • 【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

    Kadane\\\'s 算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。 算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。 以下是Kadane’s算

    2024年03月22日
    浏览(99)
  • leetcode485. 最大连续 1 的个数

    题目描述 解题思路 执行结果 leetcode 485. 最大连续 1 的个数 题目描述 给定一个二进制数组 nums , 计算其中最大连续 1 的个数。 示例 1: 输入:nums = [1,1,0,1,1,1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3. 示例 2: 输入:nums = [1,0,1,1,0,1] 输出

    2023年04月15日
    浏览(31)
  • Leetcode:【485. 最大连续 1 的个数】

    题目 给定一个二进制数组  nums  , 计算其中最大连续  1  的个数。 难度: 简单 题目链接:485. 最大连续 1 的个数 示例1: 示例2: 代码展示 【解析】 在二进制数组中,元素只有 0 和 1 ,返回得是连续1最多得个数,此时回想到 用一个变量来记录每一次得连续1的个数(co

    2024年02月08日
    浏览(33)
  • LeetCode 1004.最大连续1的个数

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 硬往题目介绍上边去想的话其实非常困难,如果换种方式思考就会简单许多。 若我们将思想转化为,找出最长的子串(里面含有的0的数量最大为k),然后返回其最长长度。 这样思路就清晰了许多,那么我们使用一个zero变量来

    2024年02月09日
    浏览(31)
  • 每日一练【最大连续1的个数】

    给定一个二进制数组  nums  和一个整数  k ,如果可以翻转最多  k  个  0  ,则返回  数组中连续  1  的最大个数  。 本题同样是利用滑动窗口的解法。 首先进入窗口,如果是1,就直接让right++,但是如果是0,那么需要让计数器去++,当计数器大于指定的k时,就需要让l

    2024年01月21日
    浏览(63)
  • 【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

        目录 一.前言 二.二叉树的节点数 二.二叉树的深度 三.二叉树第k层的节点数 四.二叉树的遍历 1.前序遍历 2.中序遍历 3.后序遍历 总结 4.层序遍历 五.二叉树叶节点的个数 我们需要 先构建个二叉树 ,方便后续对函数的测试; 还有我们在实现二叉树的这些函数时, 尽量少用

    2023年04月08日
    浏览(73)
  • 【滑动窗口】leetcode1004:最大连续1的个数

    最大连续1的个数  这道题要我们找最大连续1的个数,看到“连续”二字,我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间,这个区间需要满足某个条件。那么本题要找的是怎样的区间呢?是一个通过翻转0后得到连续1的区间,而最多可以翻转k个字符。 故

    2024年02月11日
    浏览(39)
  • 【Leetcode -485.最大连续1的个数 -492.构造矩形】

    题目:给定一个二进制数组 nums , 计算其中最大连续 1 的个数。 示例 1: 输入:nums = [1, 1, 0, 1, 1, 1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3. 示例 2: 输入:nums = [1, 0, 1, 1, 0, 1] 输出:2 思路是遍历一次数组,如果是1就使用变量count累加

    2024年02月05日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包