排序子序列

題目鏈接

題解

1. 貪心 + 模擬
2. 1 2 3 2 2 應該是有兩個排列子序列的，所以i == n-1時ret++
3. 把水平的位置和上升部分，水平位置和下降部分分為一個排列子序列

代碼

#include <iostream>
using namespace std;const int N =1e5 + 10;
int a[N];int main()
{int n;cin >> n;for(int i = 0;i < n;i++) cin >> a[i];// 開始并不知道是上升的還是下降的,加加跳過水平的位置int ret = 0;// 統計最少的排序子序列int i = 0;while(i < n){while(i + 1 < n && a[i] == a[i+1]) i++;if(i == n-1){ret++;break;}if(a[i] > a[i+1]){while(i + 1 < n && a[i] >= a[i+1]) i++;ret++;}else if(a[i] < a[i+1]){while(i + 1 < n && a[i] <= a[i+1]) i++;ret++;}i++;// 為了讓水平的部分跳過}cout << ret << '\n';return 0;
}

消減整數

題目鏈接

題解

1. 貪心 + 數學
2. 第一次必須減1，a = 1，之后的數如果是a的2倍，那么a乘2，每次ret++
3. 貪心：如果這個數模2*a == 0就一直貪心

代碼

#include<iostream>using namespace std;int main()
{int t;cin >> t;while(t--){int h;cin >> h;int ret = 0;int a = 1;while(h){h -= a;ret++;if(h % (2*a) == 0){a *= 2;}}cout << ret << '\n';}return 0;
}

最長公共子序列(二)

題目鏈接

題解

1. 貪心 + 二分
2. 時間復雜度：O(N*logN)
3. 動態規劃的時間復雜度：O(N^2)

代碼

class Solution 
{int dp[100010] = {0};int pos = 0;
public:int LIS(vector<int>& a) {for(auto x : a){if(pos == 0 || x > dp[pos]){dp[++pos] = x;}else {// 二分int l = 1,r = pos;while(l < r){int mid = (l + r) / 2;if(dp[mid] >= x) r = mid;else l = mid + 1; }dp[l] = x;}}    return pos;}
};