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

简介: 这是力扣的 1004 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。又是一道滑动窗口的典型例题,可以帮助我们巩固滑动窗口算法。这道题很活灵活现,需要加深对题意的变相理解。给定一个二进制数组nums和一个整数k,如果可以翻转最多k个0,则返回数组中连续1的最大个数。

 其他系列文章导航

Java基础合集

数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一:滑动窗口

2.2 滑动窗口解题模板

三、代码

3.1 方法一:滑动窗口

四、复杂度分析

4.1 方法一:滑动窗口


前言

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

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

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


一、题目描述

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k0 ,则返回 数组中连续 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. 滑动窗口长度的最大值就是所求。

        image.gif编辑

        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

          image.gif

          在这个例子中,我们使用一个变量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;
              }
          }

          image.gif

          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;
              }
          };

          image.gif

          Python版本:

          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

          image.gif


          四、复杂度分析

          4.1 方法一:滑动窗口

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


            目录
            相关文章
            |
            23天前
            |
            算法 数据处理 C语言
            C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
            本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
            34 1
            |
            26天前
            |
            机器学习/深度学习 算法 数据挖掘
            K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
            K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
            81 4
            |
            2月前
            |
            存储 人工智能 算法
            数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
            这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
            92 3
            数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
            |
            24天前
            |
            存储 算法 搜索推荐
            Python 中数据结构和算法的关系
            数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
            |
            23天前
            |
            数据采集 存储 算法
            Python 中的数据结构和算法优化策略
            Python中的数据结构和算法如何进行优化?
            |
            1月前
            |
            算法
            数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
            在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
            97 23
            |
            1月前
            |
            算法
            数据结构之蜜蜂算法
            蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
            60 20
            |
            23天前
            |
            并行计算 算法 测试技术
            C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
            C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
            54 1
            |
            1月前
            |
            机器学习/深度学习 算法 C++
            数据结构之鲸鱼算法
            鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
            50 0
            |
            1月前
            |
            算法 vr&ar 计算机视觉
            数据结构之洪水填充算法(DFS)
            洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
            42 0