数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 中将数组拆分为连续子序列
假设我们有一个按升序排序的数组 nums。当且仅当我们可以将其拆分为一个或多个子序列时，返回 true，使得每个子序列都由连续整数组成，并且长度至少为 3。因此，如果输入类似于 [1,2,3,3,4,4,5,5]，则输出将为 True，因为我们有两个连续序列。它们是 [1,2,3,4,5] 和 [3,4,5]。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个映射 m，并将 nums 的频率存储到 m 中，并将 nums 的大小存储到 m 中。
- cnt := n
- 对于 i 从 0 到 n – 1 的范围
- x := nums[i]
- 如果 m[x] 和 m[x + 1] 和 m[x + 2]
- 将 m[x]、m[x + 1] 和 m[x + 2] 分别减少 1，将 x 增加 3，并将计数减少 3
- 当 m[x] > 0 且 m[x] > m[x – 1]
- 将 cnt 减少 1，将 m[x] 减少 1，并将 x 增加 1
- 如果 cnt 为 0，则返回 true，否则返回 false
- 让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map <int, int> m;
int n = nums.size();
for(int i = 0; i < n; i++){
m[nums[i]]++;
}
int cnt = n;
for(int i = 0; i < n; i++){
int x = nums[i];
if(m[x] && m[x + 1] && m[x + 2]){
m[x]--;
m[x + 1]--;
m[x + 2]--;
x += 3;
cnt -= 3;
while(m[x] > 0 && m[x] > m[x - 1]){
cnt--;
m[x]--;
x++;
}
}
}
return cnt == 0;
}
};
main(){
vector<int> v = {1,2,3,3,4,4,5,5};
Solution ob;
cout << (ob.isPossible(v));
}输入
[1,2,3,3,4,4,5,5]
输出
1
更新于：2020年5月4日
403 次浏览
广告