1.[编程题] 构造回文
时间限制：1秒 空间限制：32768K
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。
输入描述: 输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述: 对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子1: abcda google
输出例子1: 2 2
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int solution(string s1) { int n = s1.size(); string s2(s1); reverse(s2.begin(), s2.end()); int dp[n+1][n+1]; memset(dp, 0, sizeof(dp)); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(s1[i] == s2[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } } return n - dp[n][n]; } int main() { string s; while(cin>>s) { cout<<solution(s)<<endl; } return 0; }2.[编程题] 算法基础-字符移位
时间限制：1秒 空间限制：32768K
小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。 你能帮帮小Q吗？
输入描述: 输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述: 对于每组数据，输出移位后的字符串。
输入例子1: AkleBiCeilD
输出例子1: kleieilABCD
#include <stdio.h> #include <iostream> using namespace std; int main(){ string s; while(cin>>s){ int len = s.length(); for(int j = len-2;j>=0;--j){ for(int i = 0;i<=j;++i){ if((s[i] >= 'A' && s[i] <= 'Z') && (s[i+1]>='a' && s[i+1]<='z')){ swap(s[i],s[i+1]); } } } cout<<s<<endl; } return 0; }3.[编程题] 有趣的数字
时间限制：1秒 空间限制：32768K
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？
输入描述: 输入包含多组测试数据。 对于每组测试数据： N - 本组测试数据有n个数 a1,a2…an - 需要计算的数据 保证: 1<=N<=100000,0<=ai<=INT_MAX.
输出描述: 对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
输入例子1: 6 45 12 45 32 5 6
输出例子1: 1 2
#include <iostream> #include <algorithm> #include <vector> using namespace std; void solution(int n,vector<int> nums){ int min=0,max=0; sort(nums.begin(),nums.end()); int begin = 0; int end = 0; for(int i = 0;i<n;i++){ if(nums[i] == nums[0]) begin++; else break; } for(int i = n-1;i>=0;i--){ if(nums[i] == nums[n-1]) end++; else break; } max = begin * end; vector<int> temp; for(int i=0;i<n-1;i++){ temp.push_back(nums[i+1]-nums[i]); } sort(temp.begin(),temp.end()); if(temp[0]){ for(int i=0;i<temp.size();i++){ if(temp[0]==temp[i]) min++; else break; } } else{ int count = 1; for(int i = 1;i<n;++i){ if(nums[i] == nums[i-1]) count++; else{ min += count*(count-1)/2; count = 1; } } min += count*(count-1)/2; } cout<<min<<' '<<max<<endl; } int main(){ int n; while(cin>>n) { int temp=0; vector<int>nums; for (int i=0;i<n;i++) { cin>>temp; nums.push_back(temp); } solution(n,nums); } return 0; }