Bài toán Hand of Straights (Chia bài thành dãy liên tiếp) C++

Cho mảng bài (hand) và số W. Kiểm tra có thể chia bài thành các nhóm kích thước W, mỗi nhóm là W số liên tiếp không.

Ví dụ

Input - hand = [1,2,3,6,2,3,4,7,8], W = 3 Output - true

Giải thích - Có thể chia: [1,2,3], [2,3,4], [6,7,8].

Phương pháp tiếp cận (Map + Tham lam)

• Dùng map<int,int> đếm tần suất mỗi bài
• Lặp khi còn bài:
  • Lấy bài nhỏ nhất còn lại (begin của map)
  • Thử tạo dãy W số liên tiếp từ bài đó
  • Giảm tần suất, xóa key nếu hết
  • Nếu thiếu bài nào → false
• Trả về true nếu chia hết

Ví dụ code C++

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

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        map<int, int> m;
        int n = hand.size();
        if (n % W != 0) return false;
        for (int x : hand) m[x]++;

        while (n) {
            auto it = m.begin();
            int prev = 0;
            for (int i = 0; i < W; i++) {
                while (it->second == 0) it++;
                if ((i > 0 && it->first - 1 == prev) || i == 0) {
                    it->second--;
                    prev = it->first;
                } else {
                    return false;
                }
                it++;
            }
            n -= W;
        }
        return true;
    }
};

int main() {
    vector<int> v = {1,2,3,6,2,3,4,7,8};
    Solution ob;
    cout << ob.isNStraightHand(v, 3);
    return 0;
}

Kết quả

1