LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组 - 二分 + 滑动窗口

这篇具有很好参考价值的文章主要介绍了LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组 - 二分 + 滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  1. 删掉一个元素以后全为 1 的最长子数组
    提示
    中等
    90
    相关企业
    给你一个二进制数组 nums ,你需要从中删掉一个元素。

请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组,请返回 0 。

提示 1:

输入:nums = [1,1,0,1]
输出:3
解释:删掉位置 2 的数后,[1,1,1] 包含 3 个 1 。
示例 2:

输入:nums = [0,1,1,1,0,1,1,0,1]
输出:5
解释:删掉位置 4 的数字后,[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。
示例 3:

输入:nums = [1,1,1]
输出:2
解释:你必须要删除一个元素。

提示:

1 <= nums.length <= 105
nums[i] 要么是 0 要么是 1 。

题解

直接二分搜索即可。

class Solution {
public:
    bool check(vector<int>& nums, int d)
    {
        int zero_num = 0;
        for(int i=0;i<d;i++)
        {
            if(nums[i]==0)zero_num ++;
        }
        if(zero_num<=1)return true;
        for(int i=d;i<nums.size();i++)
        {
            if(nums[i]==0)zero_num ++;
            if(nums[i-d]==0)zero_num --;
            if(zero_num<=1)return true;
        }
        return false;
    }
    int longestSubarray(vector<int>& nums) 
    {
        int l = 1, r = nums.size(), fin=1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(check(nums, mid))
            {
                fin = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return fin - 1;
    }
};

LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组 - 二分 + 滑动窗口,LeetCode,二分查找,滑动窗口,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-581082.html

到了这里,关于LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组 - 二分 + 滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • leetcode2765 最长交替子数组

    2765. 最长交替子数组 - 力扣(LeetCode) 题目要求返回所有交替子数组的最长长度,我们可以使用双层循环。外层循环遍历数组每一个的下标,使其作为交替子数组的第一个下标firstIndex。内层循环则从firstIndex往后遍历,判断接下来的元素是否满足交替子数组的条件。如果是那

    2024年01月23日
    浏览(37)
  • 双指针问题——求只包含两个元素的最长连续子序列(子数组)

    你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组  fruits  表示,其中  fruits[i]  是第  i  棵树上的水果  种类  。 你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果: 你只有  两个  篮子,并且每

    2024年02月02日
    浏览(30)
  • LeetCode:718. 最长重复子数组 - Python

    718. 最长重复子数组 问题描述: 给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、 长度最长 的 子数组 的 长度 。 示例 1: 输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出:3 解释:长度最长的公共子数组是 [3,2,1] 。 示例 2: 输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出:

    2024年02月10日
    浏览(33)
  • ( 动态规划) 674. 最长连续递增序列 / 718. 最长重复子数组——【Leetcode每日一题】

    难度:简单 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l r) 确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月05日
    浏览(52)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(48)
  • LeetCode 2501 数组中最长的方波 Java

    方法一,哈希表+枚举 构造哈希集合,记录出现过的数字 枚举遍历 方法二,排序+二分 先排序 遍历时,如果nums[i]*nums[i]nums[n-1]时,可以直接跳出循环 在查找是否存在当前值的平方时,可以采用二分法查找,因为只需要查找是否存在,所以可以用库函数Arrays.binarySearch(int[] nu

    2024年02月11日
    浏览(35)
  • LeetCode 2401.最长优雅子数组 ----双指针+位运算

    数据范围1e5 考虑nlog 或者n的解法,考虑双指针 因为这里要求的是一段连续的数组 想起我们的最长不重复连续子序列 然后结合一下位运算就好了 是一道双指针不错的题目

    2024年02月06日
    浏览(35)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • LeetCode刷题 | 1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和

    给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。 一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后

    2024年02月12日
    浏览(44)
  • 【Py/Java/C++三种语言详解】LeetCode每日一题240123【模拟】LeetCode2765、最长交替子数组

    LeetCode2765、最长交替子数组 给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件,我们称它是一个 交替子数组 : m 大于 1 。 s(1) = s(0) + 1 。 下标从 0 开始的子数组 s 与数组 [s(0), s(1), s(0), s(1),...,s((m-1) % 2)] 一样。也就是说, s(1) - s(0) = 1 ,

    2024年01月24日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包