本文主要是介绍【笔试训练】day21，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.爱丽丝的人偶
题目意思就是构造一个序列，序列的每个元素要么比左右两个高，要么比左右两个低。
可以看成是一条上下波动的曲线。
我们可以模拟波动的这个过程。
假设有一个数组，里面元素是1-n.遍历每一个位置。用一个指针pos来表示当前检查的位置，从2开始。
从2开始，看左右两边是不是都大于他或者都小于他，如果不是，说明要调整位置。
怎么调整呢？直接跟后面这个数交换就好了。
后面这个数一定比2大，所以交换之后2原来的位置的那个数一定符合要求。因为他比左右两边的数都大了。然后pos后移动。
假设n为7，具体交换过程如下：
代码：
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;int main() {int n;cin>>n;vector<int> v(n+1);for(int i=1;i<=n;i++)v[i]=i;int pos=2;while(pos<n){if(v[pos]>v[pos-1]&&v[pos+1]>v[pos]){swap(v[pos],v[pos+1]);}pos++;}for(int i=1;i<=n;i++)cout<<v[i]<<" ";cout<<endl;return 0;
}
2.集合
考察set的使用
代码：
#include <iostream>
#include<vector>
#include<set>
#include<queue>
using namespace std;int main() {set<int> s;int n,m;cin>>n>>m;for(int i=0;i<n+m;i++){int x;cin>>x;s.insert(x);}for(auto& it:s){cout<<it<<" ";}return 0;
}
// 64 位输出请用 printf("%lld")3.最长回文子序列
递归或者动态规划。递归的话，用一个函数表示fun（l,r）最长的回文子序列是多少。自底向上递归。如果str[l]==str[r],说明fun(l,r)=fun(l+1,r-1)+2。因为，相同的两个字符是一定可以添加到子序列回文串的首尾两端的。如果不相等，那就往长度减一的子序列里面去找，即fun(l+1,r)，或者·fun(l,r-1)。
由于题目已经交上去了，就没写递归版本的代码了。
动态规划其实就是模拟这个思路的。
从长度为1开始，逐渐扩散。
dp[l][r]表示，[l,r]的范围内的回文字符串最长能到多少。不一定这个最长序列包含str[l]和str[r].
状态转移方程与递归方程一致.
代码：
#include <iostream>
#include<string>
#include<vector>
using namespace std;int main() {string str;cin>>str;int n=str.size();vector<vector<int>> f(n+1,vector<int>(n+1));int ans=1;for(int len=1;len<=n;len++){for(int l=0;l+len-1<n;l++){int r=l+len-1;if(len==1){f[l][r]=1;continue;}if(str[l]==str[r]){f[l][r]=f[l+1][r-1]+2;}else{f[l][r]=max(f[l+1][r],f[l][r-1]);}ans=max(ans,f[l][r]);}}cout<<ans<<endl;return 0;
}
这篇关于【笔试训练】day21的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
