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

题目大意：

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

给你一个由若干 0 和 1 组成的数组 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] 的值为 0 或 1

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： 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-解题思路分析/