一、愛麗絲的人偶
題目解析
現在存在
n個玩偶，每個玩偶的身高是1、2、3......n；現在我們要對這些玩偶進行排序（如果x人偶，它左右兩邊的玩偶一個比x高、一個比x矮，那這個玩偶就會爆炸）。
我們不想要任何一個人偶爆炸，題目輸入一個
n，讓我們返回滿足條件的排列。
算法思路
這道題，可以說比較簡單了，我們要讓i人偶比i-1和i+1位置的人偶高或者低；
我們可以這樣去排列：
1, n , 2 , n-1 , 3 , n-2......這樣我們可以發現，任何一個位置，它都是比左右兩個人偶高或者低的；
那這道題我們就可以從1和n開始放置人偶，所以只需要定義兩個變量分別從1和n開始向中間遍歷。
**這里有一個要注意的點：**當我們放置完
l人偶后，l是可能等于r；如果我們不做判斷，那就可能放置兩個身高一樣的人偶：
1 3 2 2。所以我們要進行判斷，如果放置完
l的人偶后，讓l++，再判斷l是否小于等于r：（如果l<=r就放置r，否則就不放置）。
這里我們也沒有必要將數據存儲起來，直接輸出即可。
代碼實現
#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int l = 1,r = n;while(l<=r){cout<<l<<' ';l++;if(l<=r){cout<<r<<' ';r--;}}cout<<endl;return 0;
}
二、集合
題目解析
題目給定兩個集合(數組)
A和B，讓我們求出A和B的交集（A+B）；輸出時要求按照升序輸出。
算法思路
對于這道題，就類似于歸并排序中，合并兩個數組的操作，但是這道題目求的是交集，也就是最后結果中不能存在相同的元素。
思路一：排序+合并數組
對于
A和B，題目并沒有說這兩個數組是有序的，那我們要進行和并數組操作就要先對A和B進行排序；排完序之后，我們使用
l和r分別遍歷兩個數組（注意：要求升序且不能存在重讀元素）如果
l位置元素等于r位置元素就先加入到結果數組中，讓r++（或者l++）；如果
l位置元素大于r位置元素，就將r位置元素加入到結果數組中；如果
l位置元素小于r位置元素，就將l位置元素加入到結果數組中。最后遍歷結束之后，
l或r可能沒有遍歷完，所以要將A或者B中剩余的元素加入到結果數組中。
思路二：set去重+排序
對于這種思路就有一點投機取巧了：
set中是不允許出現重復元素的，并且set底層是紅黑樹，是一個平衡搜索二叉樹；使用迭代器遍歷是有序的。
代碼實現
#include <iostream>
#include <set>
using namespace std;int main() {int n, m;cin >> n >> m;//set去重+排序set<int> ret;int x;for (int i = 0; i < n; i++) {cin >> x;ret.insert(x);}for (int i = 0; i < m; i++) {cin >> x;ret.insert(x);}for (auto& e : ret) {cout << e << ' ';}cout << endl;
}
三、最長回文子序列
題目解析
題目給定一個字符串
str，然后讓我們在這個字符串中找到最長的回文子序列，然后輸出它的長度。
算法思路
對于這道題，初看可能沒什么思路
這里我們可以選取不連續的元素構成子序列，那這如何去找啊？
先說整道題用什么方法去解決：動態規劃
要使用動態規劃去解決這道問題，那我們就要搞清楚狀態表示和狀態轉移方程
狀態表示：
dp[i][j]表示區間[i,j]內最長的回文子序列的長度**狀態轉移方程：**對于狀態轉移方程，這里就要好好的分析一下了：
dp[i][j]表示的是區間[i,j]內最長的回文子序列的長度，但是可能i>j或者i == j或者i<j
i > j：這種情況肯定是不存在區間[i,j]的，那此時dp[i][j] = 0。
i == j：這種情況，區間[i,j]只有一個元素，那此時這一個元素它可以構成一個回文子序列；所有dp[i][j] = 1。
i < j：這種情況，區間[i,j]內是大于等于2個元素的；這時候我們就要看i位置和j位置是否相等了。如果
str[i] == str[j]，區間[i,j]中最長回文子序列的長度就等于[i+1,j-1]中最長回文子序列的長度再加上2。如果
str[i] == str[j]，我們不能直接去找區間[i+1,j-1]內的最長回文子序列 ，因為i+1位置的元素和j位置的元素、i位置的元素和j-1位置的元素是可能相等的；所以我們要找的就是區間[i+1,j]和區間[i,j-1]中最長回文子序列長度的最大值。填表順序： 這里我們填
dp[i][j]時用到了dp[i][j-1]、dp[i+1,j]和dp[i+1,j-1]；那我們填表的順序：從下到上，每一行從左到右。**初始化：**我們在填第
n-1行要用到第n行的數據、填寫第1列時要用到第0列的數據，所以我們要初始化第n行和第0列。**返回：**我們最后要的結果在
dp[0][n-1]里存著（區間[0,n-1]內最長回文子序列的長度），最后輸出dp[0][n-1]即可。
代碼實現
#include <iostream>
using namespace std;
const int N = 1001;
int dp[N][N] = {0};
int main() {string str;cin>>str;for(int i = str.size()-1;i>=0;i--){for(int j = 0;j<str.size();j++){if(i>j)dp[i][j] = 0;else if(i == j)dp[i][j] = 1;else {if(str[i] == str[j])dp[i][j] = dp[i+1][j-1]+2;elsedp[i][j] = max(dp[i+1][j],dp[i][j-1]);}}}cout<<dp[0][str.size()-1]<<endl;return 0;
}
到這里本篇文章內容就結束了
感謝各位的支持
