Kiểm tra các số 1 cách nhau ít nhất K vị trí (Check If All 1's Are at Least Length K Places Away) trong C++

Cho mảng nhị phân nums và số nguyên k. Kiểm tra xem mọi cặp số 1 có cách nhau ít nhất k vị trí (tức là số 0 giữa chúng ≥ k).

Ví dụ

Đầu vào: nums = [1,0,0,0,1,0,0,1], k = 2
Đầu ra: true (khoảng cách: 3, 2 đều ≥ 2).

Thuật toán duyệt một lần

1. Biến last = -1 lưu vị trí số 1 gần nhất.
2. Duyệt mảng: nếu nums[i] == 1:
   • Nếu last != -1 và i - last - 1 < k → trả về false.
   • Cập nhật last = i.
3. Kết thúc duyệt → trả về true.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

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

Độ phức tạp

• Thời gian: O(N) - duyệt mảng một lần.
• Không gian: O(1).

Kết quả kiểm thử

Đầu vào: {1,0,0,0,1,0,0,1}, 2
Đầu ra: 1 (true)