1437. Check If All 1's Are at Least Length K Places Away

Problem

Given an binary array nums and an integer k, return true if all 1’s are at least k places away from each other, otherwise return false.

https://leetcode.com/problems/check-if-all-1s-are-at-least-length-k-places-away/

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Constraints:

• 1 <= nums.length <= 10⁵
• 0 <= k <= nums.length
• nums[i] is 0 or 1

Test Cases

1
2

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, k, expected', [
    ([1,0,0,0,1,0,0,1], 2, True),
    ([1,0,0,1,0,1], 2, False),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, k, expected):
    assert sol.kLengthApart(nums, k) == expected

Thoughts

如果位置 i 的数字是 1，那么最近的下一个可以是 1 的位置是 pos = i + k + 1，如果从 i + 1 到 pos - 1 中有任何位置是 1 则返回 false。

Code

1
2
3
4
5
6
7
8
9

class Solution:
    def kLengthApart(self, nums: list[int], k: int) -> bool:
        edge = -1
        for i, num in enumerate(nums):
            if num == 0: continue
            if i <= edge: return False
            edge = i + k

        return True

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章