题目都比较简单，太久没做题了有点生疏反应有点慢，做题时间有点长。
一、给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
题解：设字符串长度为n，构造另一个串为原串的回文串，求两个串的最长公共子序列的长度len即可，n-len即为答案。
ps：代码是O(n^2)的，求长度也可以用O(n*log(n))那个做法：传送门。
链接：https://www.nowcoder.com/profile/8937197/test/6617481/44802 来源：牛客网 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; char c[1005],d[1005]; int data[1005][1005]; int main() { while(scanf("%s",c)!=EOF) { int len=strlen(c); for(int i=0;i<len;i++) d[i]=c[len-1-i]; memset(data,0,sizeof(data)); for(int i=0;i<len;i++) for(int j=0;j<len;j++) if(c[i]==d[j]) data[i+1][j+1]=data[i][j]+1; else data[i+1][j+1]=max(data[i][j+1],data[i+1][j]); printf("%d\n",len-data[len][len]); } return 0; }
二、小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。
你能帮帮小Q吗？
题解：先输出小写再输出大写就行了，我居然还写了好久，实在是太久没写题了。
链接：https://www.nowcoder.com/profile/8937197/test/6617481/44803#summary 来源：牛客网 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char c[1005]; int main() { while(scanf("%s",c)!=EOF) { int len=strlen(c); int pos=len-1; for(int i=len-1;i>=0;i--) { if(c[i]>=‘A‘&&c[i]<=‘Z‘) { char tmp=c[i]; for(int j=i;j<pos;j++) c[j]=c[j+1]; c[pos]=tmp; pos--; } } puts(c); } return 0; }
三、小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？
题解：首先肯定是排序，然后处理一下，开两个数组一个存数的大小，一个存数的数目。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N=1e5+5; int n,cnt; ll data[N]; ll sum[N],type[N]; int main() { while(scanf("%d",&n)!=EOF) { memset(data,0,sizeof(data)); memset(sum,0,sizeof(sum)); memset(type,0,sizeof(type)); cnt=0; for(int i=0; i<n; i++) scanf("%lld",&data[i]); sort(data,data+n); type[cnt]=data[0]; ll mn=1000000000,mx=-1,ansmn=0,ansmx=0; for(int i=1; i<n; i++) if(data[i]==data[i-1]) { sum[cnt]++; if(sum[cnt]>=1) mn=0; } else type[++cnt]=data[i]; for(int i=0;i<=cnt;i++) sum[i]++; //for(int i=0;i<=cnt;i++) //printf("%lld %lld\n",type[i],sum[i]); //printf("%lld\n",mn); if(cnt==0) { ansmn=n*(n-1)/2; ansmx=ansmn; } else { if(mn==1000000000) { for(int i=1; i<=cnt; i++) mn=min(type[i]-type[i-1],mn); for(int i=1; i<=cnt; i++) if(type[i]-type[i-1]==mn) ansmn+=sum[i]*sum[i-1]; } else if(mn==0) { for(int i=0; i<=cnt; i++) ansmn+=sum[i]*(sum[i]-1)/2; } ansmx=sum[cnt]*sum[0]; } printf("%lld %lld\n",ansmn,ansmx); } return 0; } /* 6 45 12 45 32 5 6 */ // 1 2
原文：http://www.cnblogs.com/Ritchie/p/6416767.html