1.给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。
输入描述 :
输入数据有多组，每组包含一个字符串s，且保证 : 1 <= s.length <= 1000.
输出描述 :
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子 :
abcda
google
输出例子 :
2
2
#include <iostream> using namespace std; #include <string> #include <algorithm> #include <memory.h> const int MAX_NUM = 1010; int dp[MAX_NUM][MAX_NUM]; //先求s的反串reverse，然后求他们的最长的公共子序列，要删除的字符个数就能知道 //时间复杂度O(N^2) int getRemoveNumber(string &str) { string s(str); reverse(s.begin(), s.end()); memset(dp, 0, sizeof(dp)); int val = str.length(); int val1 = str.size(); for (int i = 0; i < s.size(); i++) { for (int j = 0; j < s.size(); j++) { if (str[i] == s[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 s.size() - dp[s.size()][s.size()]-1; //size()和length的区别 } int main() { string str; while (getline(cin,str)) { cout << getRemoveNumber(str) << endl; } return 0; } #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; //更简洁的方法实现 int main() { string s; while (cin >> s) { int m = s.size(); vector<vector<int>> dp(m, vector<int>(m, 0)); for (int len = 1; len < m; ++len) for (int i = 0, j = 0; i + len < m; ++i) { j = i + len; if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1; } cout << dp[0][m - 1] << endl; } } //题目描述 // //给定一个字符串，问是否能通过添加一个字母将其变为回文串。 // //输入描述 : //一行一个由小写字母构成的字符串，字符串长度小于等于10。 // // //输出描述 : //输出答案(YESNO). // //输入例子 : // coco // // 输出例子 : //YES #include<iostream> #include<string> #include<algorithm> using namespace std; bool isPalindrome(string str) { string temp = str; reverse(str.begin(), str.end()); return str == temp; } int main() { string str; while (cin >> str) { if (str.size() <= 0 || str.size() == 1) { cout << "YES" << endl; } else { bool temp = true; for (size_t i = 0; i < str.size(); i++) { string strTemp = str; strTemp.erase(strTemp.begin() + i); // tmp = str.substr(0, i) + str.substr(i + 1); if (isPalindrome(strTemp)) { cout << "YES" << endl; temp = false; break; } } if (temp) { cout << "NO" << endl; } } } return 0; } ////LCS实现 #include <stdio.h> #include <string.h> #define MAXLEN 100 void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i, j; for (i = 0; i <= m; i++) c[i][0] = 0; for (j = 1; j <= n; j++) c[0][j] = 0; for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) { c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 0; } else if (c[i - 1][j] >= c[i][j - 1]) { c[i][j] = c[i - 1][j]; b[i][j] = 1; } else { c[i][j] = c[i][j - 1]; b[i][j] = -1; } } } } void PrintLCS(int b[][MAXLEN], char *x, int i, int j) { if (i == 0 || j == 0) return; if (b[i][j] == 0) { PrintLCS(b, x, i - 1, j - 1); printf("%c ", x[i - 1]); } else if (b[i][j] == 1) PrintLCS(b, x, i - 1, j); else PrintLCS(b, x, i, j - 1); } int main(int argc, char **argv) { char x[MAXLEN] = { "ABCBDAB" }; char y[MAXLEN] = { "BDCABA" }; int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); return 0; }
2.小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。
你能帮帮小Q吗？
输入描述 :
输入数据有多组，每组包含一个字符串s，且保证 : 1 <= s.length <= 1000.
输出描述 :
对于每组数据，输出移位后的字符串。
输入例子 :
AkleBiCeilD
输出例子 :
kleieilABCD
#include<iostream> using namespace std; #include <string> //应该从头往后遍历，把连续的大写字母找到，遇到小写字母，交换。 //如果先找到大写字母，马上找连续的小写字母，那遇到连续的大写字母该怎么办呢？ //或者从尾向头遍历，方法类似。 string changeSequenceStr(string &str) { int size = str.size(); /*for (int i = 0; i < size;i++) { if (isupper(str[i])) { int j = i+1; while (islower(str[j])&&j<size) { j++; } if (isupper(str[j])&&j<size) { char temp = str[i]; for (int k = i; k < j; k++) { str[k] = str[k + 1]; } str[j - 1] = temp; } } }*/ for (int i = 0; i < size;i++) { if (isupper(str[i])) { int j = i; while (isupper(str[j])&&j<size) { j++; } if (j==(size-1)&&isupper(str[j])) { break; } if (islower(str[j])&&j<size) { char temp = str[j]; for (int k = j; k > i;k--) { str[k] = str[k - 1]; } str[i] = temp; } } } return str; } int main() { string str; while (getline(cin,str)) { cout << changeSequenceStr(str)<<endl; } return 0; }
3.小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？
输入描述 :
输入包含多组测试数据。
对于每组测试数据：
N - 本组测试数据有n个数
a1, a2...an - 需要计算的数据
保证 :
1 <= N <= 100000, 0 <= ai <= INT_MAX.
输出描述 :
对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
输入例子 :
6
45 12 45 32 5 6
输出例子 :
1 2
//复杂度大
#include <iostream> using namespace std; #include <vector> #include <limits.h> void getMin_Max_N(vector<int> vc,int &minN,int &maxN) { int min=INT_MAX, max=0; for (int i = 0; i < vc.size();i++) { for (int j = 0; j < vc.size();j++) { if (i!=j) { if (vc[i]-vc[j]<min) { min = vc[i] - vc[i]; minN = 1; } if (vc[i] - vc[j] == min) { minN++; } if (vc[i]-vc[j]>max) { max = vc[i] - vc[j]; maxN = 1; } if (vc[i] - vc[j] == max) { maxN++; } } } } } int main() { int N; while (cin>>N) { vector<int> vc(N,0); for (int i = 0; i < N;i++) { cin >> vc[i]; //这种方式输入，必须初始化大小。否则又溢出现象 } int minN = 1, maxN = 1; getMin_Max_N(vc, minN, maxN); cout << minN << " " << maxN << endl; } } //参考： #include <vector> #include <iostream> #include <algorithm> #include <functional> using namespace std; int main() { int n; while (cin >> n) { vector<int> nVec(n); for (int i = 0; i < n; ++i) { cin >> nVec[i]; } if (n == 1) { cout << 0 << " " << 0 << endl; continue; } sort(nVec.begin(), nVec.end()); int nMinDvalueNum = 0; int nMinDvalue = nVec[1] - nVec[0]; int nMaxNum = count(nVec.begin(), nVec.end(), nVec[n - 1]); int nMinNum = count(nVec.begin(), nVec.end(), nVec[0]); for (int i = 1; i < n; ++i) { nMinDvalue = nMinDvalue>(nVec[i] - nVec[i - 1]) ? nVec[i] - nVec[i - 1] : nMinDvalue; } for (int i = 1; i < n; ++i) { for (int j = i - 1; j >= 0; --j) { int temp = nVec[i] - nVec[j]; if (nMinDvalue == temp) { nMinDvalueNum++; } else { break; } } } //最大值和最小值相同 if (nVec[0] == nVec[n - 1]) { int num = 1 << nMaxNum - 1; cout << num << " " << num << endl; } else { cout << nMinDvalueNum << " " << nMaxNum*nMinNum << endl; } } return 0; } #include <iostream> #include <algorithm> #include <vector> #include <functional> using namespace std; int main(){ int n; while (cin >> n){ vector<int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } if (n == 1){ cout << 0 << " " << 0 << endl; continue; } sort(a.begin(), a.end()); int maxnum = count(a.begin(), a.end(), a[n - 1]); int minnum = count(a.begin(), a.end(), a[0]); int max = maxnum*minnum; int minvalue = a[1] - a[0]; for (int i = 1; i < n; i++){ if (a[i] - a[i - 1] < minvalue) minvalue = a[i] - a[i - 1]; } int min = 0; for (int i = 1; i < n; i++){ for (int j = i - 1; j >= 0; j--){ if (a[i] - a[j] == minvalue) min++; else break; } } if (a[0] == a[n - 1]){ int num = a.size()*(a.size() - 1) / 2; cout << num << " " << num << endl; continue; } cout << min << " " << max << endl; } return 0;