Chương trình kiểm tra xem danh sách có thể được chia thành danh sách con của k phần tử tăng dần trong C ++ hay không

Giả sử chúng ta có một danh sách các số được gọi là num và một số khác k, chúng ta phải kiểm tra xem danh sách có thể được chia thành các danh sách trong đó mỗi danh sách chứa k giá trị và các giá trị tăng liên tục hay không.

Vì vậy, nếu đầu vào giống như nums =[4, 3, 2, 4, 5, 6], k =3, thì đầu ra sẽ là True, vì chúng ta có thể chia danh sách thành [2, 3, 4] và [ 4, 5, 6]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ

• cho mỗi khóa, nó bằng m

  • tăng m [it] lên 1

• ok:=true

• while (kích thước của m không phải là 0 và ok là true), do -

  • ok:=false

  • đối với mỗi khóa-giá trị, hãy ghép nối nó bằng m

    • nếu (it.key - 1) không phải bằng m, thì -

      • cờ:=true

      • để khởi tạo i:=it.key, khi tôi <=it.key + k - 1, cập nhật (tăng i lên 1), thực hiện -

        • nếu tôi không có mặt ở m, thì -

          • cờ:=false

      • nếu cờ là true, thì -

        • để khởi tạo i:=it.key, khi tôi <=it.key + k - 1, cập nhật (tăng iby 1), thực hiện -

          • (giảm m [i] đi 1)

          • nếu m [i] giống 0 thì -

            • xóa tôi khỏi m

        • ok:=true

        • Ra khỏi vòng lặp

• trả về true khi m trống, ngược lại là false.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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();
      }
};
main(){
   vector<int> v = {4, 3, 2, 4, 5, 6};
   Solution ob;
   cout << ob.solve(v, 3);
}

Đầu vào

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

Đầu ra

1