リストをC++でk個の増加する要素のサブリストに分割できるかどうかをチェックするプログラム

numsと呼ばれる数値のリストと別の数値kがあるとすると、各リストにk個の値が含まれ、値が連続して増加するリストにリストを分割できるかどうかを確認する必要があります。

したがって、入力がnums =[4、3、2、4、5、6]、k =3のような場合、リストを[2、3、4]と[に分割できるため、出力はTrueになります。 4、5、6]

これを解決するには、次の手順に従います-

• 1つのマップを定義する

• キーごとにm

  で

  • m[it]を1増やします

• ok：=true

• （mのサイズは0ではなく、okはtrueです）、実行-

  • ok：=false

  • キーと値のペアごとに、m

    で

    • （it.key-1）がmにない場合、-

      • フラグ：=true

      • 初期化i：=it.keyの場合、i <=it.key + k-1の場合、更新（iを1増やします）、do-

        • iがmに存在しない場合、-

          • フラグ：=false

      • フラグがtrueの場合、-

        • 初期化i：=it.keyの場合、i <=it.key + k --1の場合、更新（iby 1を増やす）、実行-

          • （m [i]を1減らします）

          • m [i]が0と同じ場合、-

            • mからiを削除する

        • ok：=true

        • ループから出てきます

• mが空の場合はtrueを返し、それ以外の場合は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();
      }
};
main(){
   vector<int> v = {4, 3, 2, 4, 5, 6};
   Solution ob;
   cout << ob.solve(v, 3);
}

入力

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

出力

1