資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次瀏覽
廣告