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

算法题:给定正整数数组和正整数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函数并打印结果。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容