C++ 程式檢查列表是否可以拆分為包含 k 個遞增元素的子列表

假設我們有一個名為 nums 的數字列表，以及另一個數字 k，我們需要檢查該列表是否可以拆分為多個列表，其中每個列表包含 k 個值，並且這些值是連續遞增的。

因此，如果輸入類似於 nums = [4, 3, 2, 4, 5, 6]，k = 3，則輸出將為 True，因為我們可以將列表拆分為 [2, 3, 4] 和 [4, 5, 6]

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個對映

  • 對於對映中的每個鍵 it

    • 將 m[it] 增加 1

  • ok := true

  • 當 (對映的大小不為 0 且 ok 為 true) 時，執行以下操作：

    • ok := false

    • 對於對映中的每個鍵值對 it

      • 如果 (it.key - 1) 不在對映中，則：

        • flag := true

        • 從 i := it.key 開始，當 i <= it.key + k - 1 時，更新 (i 增加 1)，執行以下操作：

          • 如果 i 不存在於對映中，則：

            • flag := false

        • 如果 flag 為 true，則：

          • 從 i := it.key 開始，當 i <= it.key + k - 1 時，更新 (i 增加 1)，執行以下操作：

            • （將 m[i] 減 1）

            • 如果 m[i] 等於 0，則：

              • 從對映中刪除 i

          • ok := true

          • 退出迴圈

  • 當對映為空時返回 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

更新於: 2020 年 10 月 10 日

96 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告