資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的擺動子序列
假設我們有一系列數字，如果連續數字之間的差嚴格地在正數和負數之間交替，則稱之為擺動序列。第一個差可以是正數或負數。少於兩個元素的序列微不足道地是一個擺動序列。例如，[1,7,4,9,2,5] 是一個擺動序列，因為如果看到，差值 (6,-3,5,-7,3) 是交替的正數和負數。但是，[1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個是因為它的前兩個差是正數，第二個是因為它的最後一個差是零。
所以我們有一系列整數，我們必須找到最長子序列的長度，該子序列是一個擺動序列。子序列是透過從原始序列中刪除一些數字（最終也為零）獲得的，並將剩餘的數字按其原始順序保留。因此，如果輸入類似於 [1,7,4,9,2,5]，則輸出將為 6，因為整個序列是一個擺動序列。
為了解決這個問題，我們將遵循以下步驟：
n := nums 的大小
如果 n 為 0，則返回 0
設定 up := 1 和 down := 1
對於 i 從 1 到 n – 1 的範圍
如果 nums[i] > nums[i – 1]，則 up := down + 1
否則，當 nums[i] < nums[i – 1] 時，則 down := up + 1
返回 up 和 down 的最大值
示例 (C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(!n) return 0;
int up = 1;
int down = 1;
for(int i = 1; i < n; i++){
if(nums[i] > nums[i - 1]){
up = down + 1;
}
else if(nums[i] < nums[i - 1]){
down = up + 1;
}
}
return max(up, down);
}
};
main(){
Solution ob;
vector<int> v = {1,7,4,9,2,5};
cout << (ob.wiggleMaxLength(v));
}輸入
[1,7,4,9,2,5]
輸出
6
更新於：2020年5月2日
248 次檢視
廣告