X

LEETCODE 1437. Check If All 1’s Are at Least Length K Places Away 解题思路分析

题目大意:

是否所有 1 都至少相隔 k 个元素

给你一个由若干 01 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素,则返回 True ;否则,返回 False

示例 1:

输入:nums = [1,0,0,0,1,0,0,1], k = 2
输出:true
解释:每个 1 都至少相隔 2 个元素。

示例 2:

输入:nums = [1,0,0,1,0,1], k = 2
输出:false
解释:第二个 1 和第三个 1 之间只隔了 1 个元素。

示例 3:

输入:nums = [1,1,1,1,1], k = 0
输出:true

示例 4:

输入:nums = [0,1,0,1], k = 1
输出:true

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= k <= nums.length
  • nums[i] 的值为 01

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

解题思路分析:

这道题没有什么难度,我们使用一个变量记录上一个1出现的位置,然后循环数组,如果当前数字是1的话,查看与上个1的距离,如果大于k的话,直接返回false。否则,更新上一个1出现的位置为当前位置。当循环结束后,说明所有1之间的距离都不超过k,返回true。

实现代码:

public boolean kLengthApart(int[] nums, int k) {
    int lastOnePosition=-1; // 上一个1出现的位置
    for(int i=0;i<nums.length;i++){
        if(nums[i]==1) { // 当前是数字1
            if(lastOnePosition!=-1){ // 当前1不是首次出现
                // 与上个1的距离大于k,返回false
                if(i-lastOnePosition-1<k) return false;
            }
            lastOnePosition=i; // 更新1出现的位置
        }
    }
    return true;
}

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

Runtime: 1 ms, faster than 100.00% of Java online submissions for Check If All 1’s Are at Least Length K Places Away.

Memory Usage: 49.1 MB, less than 100.00% of Java online submissions for Check If All 1’s Are at Least Length K Places Away.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1437-check-if-all-1s-are-at-least-length-k-places-away-解题思路分析/
Categories: leetcode
kwantong: