資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告