โปรแกรมตรวจสอบว่ารายการสามารถแบ่งเป็นสับลิสต์ที่มี k องค์ประกอบเพิ่มขึ้นติดต่อกันได้หรือไม่ใน C++

สมมติว่าเรามีรายการตัวเลข nums และตัวเลข k เราต้องตรวจสอบว่าสามารถแบ่งรายการนี้ออกเป็นสับลิสต์ได้หรือไม่ โดยแต่ละสับลิสต์มี k ค่า และค่าเหล่านั้นเพิ่มขึ้นติดต่อกัน

เช่น หากอินพุตคือ nums = [4, 3, 2, 4, 5, 6], k = 3 ผลลัพธ์จะเป็น True เนื่องจากสามารถแบ่งได้เป็น [2, 3, 4] และ [4, 5, 6]

ขั้นตอนการแก้ปัญหา

• ใช้ map นับความถี่ของแต่ละตัวเลข
• วนลูปจนกว่า map จะว่าง:
  • หาตัวเลขที่น้อยที่สุดที่ไม่มีตัวเลขก่อนหน้า (it.key - 1) ใน map
  • ตรวจสอบว่ามีตัวเลขติดต่อกัน k ตัว (it.key ถึง it.key + k - 1) ครบหรือไม่
  • ถ้าครบ ให้ลดความถี่ของตัวเลขเหล่านั้นลง 1 และลบออกจาก map ถ้าความถี่เป็น 0
  • ทำซ้ำจนกว่าจะไม่สามารถสร้างกลุ่มได้อีก
• คืนค่า true ถ้า map ว่างเปล่า ไม่เช่นนั้น false

ตัวอย่างโค้ด

#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);
}

อินพุต

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

เอาต์พุต

1