美文网首页
算法题:给定正整数数组和正整数k。数组中只含有0或1,可以最多k

算法题:给定正整数数组和正整数k。数组中只含有0或1,可以最多k

作者: 蓦然回味 | 来源:发表于2024-03-10 10:09 被阅读0次

算法题:给定正整数数组和正整数k。数组中只含有0或1,可以最多k次将0翻转成1。求数组中最长连续1的长度。

以下是该段JavaScript代码的解题思路:

解题思路:

1、初始化参数:
· 初始化左边界left和右边界right,均指向数组的第一个元素。
· 初始化zeros,用于记录当前窗口内0的个数。
· 初始化maxLength,用于记录最长连续1的长度。
2、遍历数组:
· 使用while循环遍历数组,直到右边界right到达数组的末尾。
3、处理右边界:
· 每次循环,检查右边界对应的元素是否为0。如果是,则zeros增加1。
4、调整窗口大小:
· 如果zeros的数量超过了k(即允许翻转的0的最大数量),则需要缩小窗口,以去除多余的0。
· 使用内部的while循环,逐步移动左边界left,直到zeros的数量减少到k或以下。
· 在移动左边界的过程中,如果左边界对应的元素是0,则zeros减少1。
5、更新最长连续1的长度:
· 在每次循环中,计算当前窗口的大小(right - left + 1),并与之前记录的最长连续1的长度maxLength比较。
· 如果当前窗口大小更大,则更新maxLength。
6、移动右边界:
· 在每次循环的末尾,右边界right向右移动一位,以处理下一个数组元素。
7、返回结果:
· 当右边界right遍历完整个数组后,返回最长连续1的长度maxLength。

这个解题思路的核心是利用滑动窗口技巧来动态地调整窗口的大小,使得窗口内0的个数不超过k,从而找到最长连续1的长度。通过不断移动窗口的左右边界,算法能够在一次遍历中有效地解决问题。

javascript解题参考代码:


//javascript

function longestOnes(nums, k) {  
    let left = 0; // 滑动窗口左边界  
    let right = 0; // 滑动窗口右边界  
    let zeros = 0; // 窗口内0的个数  
    let maxLength = 0; // 最长连续1的长度  
  
    while (right < nums.length) {  
        // 如果当前数字是0,则增加0的计数  
        if (nums[right] === 0) {  
            zeros++;  
        }  
  
        // 如果0的个数超过了k,则需要收缩窗口左边界  
        while (zeros > k) {  
            // 如果左边界的数字是0,则减少0的计数  
            if (nums[left] === 0) {  
                zeros--;  
            }  
            // 左边界向右移动  
            left++;  
        }  
  
        // 更新最长连续1的长度  
        maxLength = Math.max(maxLength, right - left + 1);  
  
        // 右边界向右移动  
        right++;  
    }  
  
    return maxLength;  
}  
  
// 测试  
const nums = [1, 0, 0, 1, 1, 0, 1, 1, 0, 1];  
const k = 2;  
const result = longestOnes(nums, k);  
console.log("最长连续1的长度为:", result);

这段代码定义了一个longestOnes函数,它接收一个只包含0和1的数组nums以及一个正整数k作为参数。函数内部使用滑动窗口技巧来遍历数组,并维护一个窗口,其中最多包含k个0。当0的个数超过k时,窗口的左边界会向右移动,直到0的个数减少到k或以下。在此过程中,函数记录并更新最长连续1的长度。最后,函数返回这个长度。

在测试部分,我们创建了一个示例数组nums并设置了k的值为2,然后调用longestOnes函数并打印结果。

相关文章

  • 10.LeetCode刷题For Swift·209. 长度最小

    1、原题 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子...

  • [中等]457.环形数组循环

    给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数,则向前移动 k 个索引。相反,如...

  • Leetcode --- 子数组问题(滑动窗口)

    1.长度最小的子数组(209 - 中) 题目描述:给定一个含有 n 个正整数的数组和一个正整数 target 。 ...

  • leetcode-双指针

    209 :给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target ...

  • LeetCode-209-长度最小的子数组

    长度最小的子数组 题目描述:给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥...

  • 209. 长度最小的子数组

    【Description】给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度...

  • 209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小...

  • LeetCode 209. 长度最小的子数组

    题目 给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最...

  • 713.乘积小于k的子数组

    给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。 示例 1:输入: nums = [...

  • 209#长度最小子数组

    题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组...

网友评论

      本文标题:算法题:给定正整数数组和正整数k。数组中只含有0或1,可以最多k

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