数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告