Given an array nums
of 0s and 1s and an integer k
, return True
if all 1’s are at least k
places away from each other, otherwise return 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.
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.
Example 3:
Input: nums = [1,1,1,1,1], k = 0 Output: true
Example 4:
Input: nums = [0,1,0,1], k = 1 Output: true
Constraints:
1 <= nums.length <= 10^5
0 <= k <= nums.length
nums[i]
is0
or1
Solution: Scan the array
Only need to check adjacent ones. This problem should be easy instead of medium.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: bool kLengthApart(vector<int>& nums, int k) { int d = k + 1; // distant enough for (int n : nums) { if (n == 0) { ++d; } else { if (d < k) return false; d = 0; } } return true; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment