Chương trình kiểm tra danh sách có thể chia thành các danh sách con k phần tử tăng liên tiếp trong C++

Cho một danh sách số nums và số k. Kiểm tra xem có thể chia danh sách thành các danh sách con, mỗi danh sách chứa đúng k giá trị và các giá trị này tăng liên tiếp (ví dụ: [2,3,4]).

Ví dụ: nums = [4, 3, 2, 4, 5, 6], k = 3 → True, vì có thể chia thành [2, 3, 4] và [4, 5, 6].

Thuật toán

• Dùng map m đếm tần suất từng số.
• Lặp cho đến khi map rỗng hoặc không tìm thấy dãy hợp lệ:
  • Tìm số nhỏ nhất trong map (số không có tiền tố số trước đó trong map).
  • Kiểm tra xem từ số đó có đủ k số liên tiếp không.
  • Nếu có, giảm tần suất của k số đó, xóa khỏi map nếu tần suất về 0.
  • Đánh dấu đã tìm thấy dãy hợp lệ, tiếp tục vòng lặp.
• Trả về true nếu map rỗng, ngược lại false.

Ví dụ triển khai (C++)

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

class Solution {
public:
    bool solve(vector<int> nums, int k) {
        map<int, int> m;
        for (auto& it : nums) m[it]++;
        bool ok = true;
        while (m.size() && ok) {
            ok = false;
            for (auto& it : m) {
                if (!m.count(it.first - 1)) {
                    bool flag = true;
                    for (int i = it.first; i <= it.first + k - 1; i++) {
                        if (!m.count(i)) flag = false;
                    }
                    if (flag) {
                        for (int i = it.first; i <= it.first + k - 1; i++) {
                            m[i]--;
                            if (m[i] == 0) m.erase(i);
                        }
                        ok = true;
                        break;
                    }
                }
            }
        }
        return m.empty();
    }
};

int main() {
    vector<int> v = {4, 3, 2, 4, 5, 6};
    Solution ob;
    cout << ob.solve(v, 3);
    return 0;
}

Đầu vào

{4, 3, 2, 4, 5, 6}

Đầu ra

1