LeetCode Problem: Check If All 1’s Are at Least Length K Places Away 詳解

Description

給定一個只包含 0 和 1 的陣列以及非零整數 k，如果所有 1 的間隔至少 k 則回傳 true，否則回傳 false。

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.
[1,0,0,0,1,0,0,1]
 |---3---|--2--|

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.
[1,0,0,1,0,1]
 |--2--|-1-|

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true

Solution

本題解法單純，每次遍歷 nums 時，遇到 1 則用一個 pointer 記住位置，並且求出和上一個 1 的 pointer之距離，若小於 k 則直接回傳 false，如果遍歷到最後代表符合條件，並回傳 true。需要注意的是此題的間隔指的是兩個 1 之間有多少 0，因此計算間隔時應該以 ptr2 - ptr1 - 1 來計算。

完整算法如下(in C++)

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int ptr = -1;
        for (int idx = 0; idx < nums.size(); ++idx)
        {
            if (nums[idx] == 1)
            {
                if (ptr != -1 && idx - ptr - 1 < k) return false;
                else ptr = idx;
            }
            else
            {}
        }

        return true;
    }
};