LEETCODE 1493. Longest Subarray of 1’s After Deleting One Element 解题思路分析

题目大意:

删掉一个元素以后全为 1 的最长子数组

给你一个二进制数组 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
解释:你必须要删除一个元素。

示例 4:

输入:nums = [1,1,0,0,1,1,1,0,1]
输出:4

示例 5:

输入:nums = [0,0,0]
输出:0

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1493

解题思路分析:

本题解法很多,这里提供2中思路。

解法一:dfs(递归)

我们从数组首元素开始向后dfs,dfs函数需要使用3个参数,分别为当前下标,是否使用过删除,当前连续长度。递归中,如果当前元素是1,那么我们将长度加一继续递归到下一位。如果当前元素是非1,我们可以将长度变为0,递归到下一位重新寻找最长区间。另外如果当前还未使用删除机会,那么我们可以忽略当前非1位,长度不变递归至下一位。每层递归中都需要使用当前长度更新全局最大长度。

另外,dfs递归中会存在重复路径,因此我们使用一个二维访问数组visited[][]记录已走过的点,避免重复计算。visited[i][j]代表下标为i并且当前删除次数剩余j的情况下是否已经递归过。

实现代码:

boolean[][] visited; // 访问数组
public int longestSubarray(int[] nums) {
    visited=new boolean[nums.length][2]; // 初始化访问数组
    help(nums,0,1,0); // dfs递归
    if(res==nums.length) res--; // 如果全是1,结果减一
    return res;
}
int res=0; // 返回结果
// nums:数组
// index:当前下标
// delete:剩余删除次数
// 当前连续长度
void help(int[] nums, int index, int delete, int count){
    res=Math.max(res,count); // 更新全局最大长度
    if(index==nums.length) return; // 越界
    if(visited[index][delete]) return; // 已访问过
    visited[index][delete]=true; // 设置已访问过
    if(nums[index]==1){ // 当前数为1
        help(nums,index+1,delete,count+1); // 长度加一递归至下一位
    }else{ // 当前数为非1
        help(nums,index+1,1,0); // 将长度清零,递归至下一位重新统计
        if(delete==1){ // 如果当前还未使用删除
            help(nums,index+1,0,count); // 长度不变,递归至下一位
        }
    }
}

本题解法执行时间为18ms。

Runtime: 18 ms, faster than 8.46% of Java online submissions for Longest Subarray of 1’s After Deleting One Element.

Memory Usage: 58.9 MB, less than 50.00% of Java online submissions for Longest Subarray of 1’s After Deleting One Element.


解法二:

设置两个变量:

count1:当前包含一个非1的连续长度。
count2:当前全是1的连续长度。

循环数组每一个数字,如果当前数字是1,count1和count2同时加一,同时使用count1更新全局最大值。重点来了,如果当前数字是非1,则设count1等于count2,count2设为0。最后处理一下全是1的特例即可。

实现代码:

public int longestSubarray(int[] nums) {
    int count1=0;
    int count2=0;
    int res=0;
    for(int n : nums){
        if(n==1){
            count1++;
            count2++;
            res=Math.max(res,count1);
        }else{
            count1=count2;
            count2=0;
        }
    }
    if(res==nums.length) res--;
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 83.32% of Java online submissions for Longest Subarray of 1’s After Deleting One Element.

Memory Usage: 48.6 MB, less than 50.00% of Java online submissions for Longest Subarray of 1’s After Deleting One Element.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1493-longest-subarray-of-1s-after-deleting-one-element-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。