主要思想：
1.先把字母和数字用string存储，字母同意用小写字母存储
2.双指针判断直到指针相遇
bool isPalindrome(string s) {
// 双指针
// #include <ctype.h>
// 记一笔 c++的几个内置函数
//islower(char c) 是否为小写字母
//isupper(char c) 是否为大写字母
//isdigit(char c) 是否为数字
//isalpha(char c) 是否为字母
//isalnum(char c) 是否为字母或者数字
//toupper(char c) 字母小转大
//tolower(char c) 字母大转小
string tmp;
for(auto c:s){
if(islower(c) || isdigit(c)) tmp+=c;
else if(isupper(c)) tmp+=(c+32); // 全转小写
}
// 开始双指针
int i=0, j=tmp.size()-1;
while(i<j){
if(tmp[i]!=tmp[j]) return false;
i++;
j--;
}
return true;
}
主要思路：
int i=0;i<=size()-2;i++暴力法采用双指针两边夹，验证是否是回文子串。
除了枚举字符串的左右边界以外，比较容易想到的是枚举可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。
因此中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
枚举“中心位置”时间复杂度为 O(N)，从“中心位置”扩散得到“回文子串”的时间复杂度为 O(N)，因此时间复杂度可以降到 O(N^2)
// 序列数是奇数s[i] 与 s[i]相等也不影响
string evenStr = expandAroundCenter(s, i,i);
// 序列数是偶数
string oddStr = expandAroundCenter(s,i,i+1);
整体代码如下：
class Solution{
public:
// 从中心扩展检验是否回文
string expandAroundCenter(const string& s, int left, int right){
while(left>=0&&right<s.size()&&s[left]==s[right]){
--left;
++right;
}
// 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
return s.substr(left+1, right-left-1);
}
string longestPalindrome(string s){
// 特判
int size = s.size();
if (size < 2) {
return s;
}
int maxLen = 1;
string res = s.substr(0, 1);
// 中心位置枚举到len-2即可
// 从头开始枚举中心位置 从i=0
for(int i=0;i<s.size()-1;i++){
// 序列数是奇数s[i] 与 s[i]相等也不影响
string evenStr = expandAroundCenter(s, i,i);
// 序列数是偶数
string oddStr = expandAroundCenter(s,i,i+1);
string maxLenStr= oddStr.size()>evenStr.size()?oddStr:evenStr;
if(maxLenStr.length()>maxLen){
maxLen=maxLenStr.size();
res=maxLenStr;
}
}
return res;
}
};
主要考察：
gets的输入
gets(): gets()函数用来从标准输入设备（键盘）读取字符串直到换行符结束，但换行符会被丢弃，然后在末尾添加’\0’字符。其调用格式为：
gets(s);
其中s为字符串变量（字符串数组名或字符串指针）。
gets(s)函数与scanf("%s",s)相似，但不完全相同，使用scanf("%s",s) 函数输入字符串时存在一个问题，就是如果输入了空格会认为字符串结束，空格后的字符将作为下一个输入项处理，但gets()函数将接收输入的整个字符串直到遇到换行为止。
也就是说：gets()函数读取到\n（我们输入的回车）于是停止读取，但是它不会把\n包含到字符串里面去。然而，和它配合使用的puts函数，却在输出字符串的时候自动换行。
#include <iostream>
#include <string.h>
using namespace std;
int main(){
char str[5001]; // 题目要求，长度小于5000
// 输入字符串
//cin >> str; // 错误遇到空格不读了
// cin不接受空格和TAB等符号的输入，遇到这些键，字符串会终止，而gets()则接受连续的输入，包括空格，TAB
// 计算最后一个单词的长度
gets(str);
//cout << str << endl;
int len = 0;
// Returns the length of the C string str(包括空格，但是不包括the terminating null character)
for(int i = strlen(str)-1; str[i]!=' ' && i>=0; i--){
len++;
}
cout << len << endl;
return 0;
}
本地考察两个：
#include <iostream>
using namespace std;
const int N = 10010; // 定义数组长度防止溢出
char str[N];
int main(){
// 输入字符串 只有数字和字母
// cin>>str;
gets(str);
char x;
cin >> x;
int count = 0; // 保证遍历到字符串的末端
for(int i = 0; str[i]!='\0'; i++){
if(str[i]==x || str[i]==x+32 || str[i]==x-32) // 大小写
count++;
}
cout << count << endl;
return 0;
}
主要考察对库函数的调用：
getline(cin, inputLine);
其中 cin 是正在读取的输入流，而 inputLine 是接收输入字符串的 string 变量的名称
为了cin的问题(遇到空格不读取，此外前导空格也不读取)，可以使用一个叫做 getline 的 C++ 函数。此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中
append()方法的应用
#include <iostream>
using namespace std;
int main(){
string str;
while(getline(cin, str)){
// 循环 输出前八个 截取9~自最后的
while(str.size() >8){
cout << str.substr(0, 8) << endl; // 从0开始，读取8个长度
str = str.substr(8); // 从str[8]开始截取后面的，因为第一次[0]~[7]已经cout
}
// 当长度小于8时，后面补0
cout << str.append(8-str.size(), '0') << endl;
}
return 0;
}
主要思路:
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
string str;
getline(cin, str);
// 翻转句子所有字符
reverse(str.begin(), str.end()); // end()是队尾元素
// 翻转单个单词
for(int i =0; i<str.size(); i++){
int j = i;
// 通过i，j定位单词首尾
while(j<str.size() &&str[j]!=' ') j++; // 跳出循环时，j定位到相邻两个单词空格
reverse(str.begin()+i, str.begin()+j);
// 定位到下一个单词
i=j;
}
cout << str << endl;
}
主要思路：
利用自定义排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 自定义bool排序
bool cmp(const string& s1, const string& s2){
return s1<s2;
}
int main(){
int n;
cin >> n; // 接受第一行一个正整数n
vector<string> res;
while(n--){
string word;
cin >> word; // 接收每行字符串/每次接收一行
res.push_back(word);
}
sort(res.begin(), res.end(), cmp);
for(auto x:res) cout << x << endl;
return 0;
}
主要思路：
#include <iostream>
#include <string.h>
using namespace std;
int main(){
// 处理输入
string str;
// 多个测试用例，所以用while来测试
while(cin>>str){
// 进行加密
for(int i=0; i<str.size();i++){
// 小写字母转换
// 1--1， abc--2, def--3, ghi--4, jkl--5, mno--6, pqrs--7, tuv--8 wxyz--9, 0--0,
if(str[i]>='a' && str[i]<='c'){
str[i]='2';
}
else if(str[i]>='d' && str[i]<='f'){
str[i]='3';
}
else if(str[i]>='g' && str[i]<='i'){
str[i]='4';
}
else if(str[i]>='j' && str[i]<='l'){
str[i]='5';
}
else if(str[i]>='m' && str[i]<='o'){
str[i]='6';
}
else if(str[i]>='p' && str[i]<='s'){
str[i]='7';
}
else if(str[i]>='t' && str[i]<='v'){
str[i]='8';
}
else if(str[i]>='w' && str[i]<='z'){
str[i]='9';
}
if(str[i]=='Z')
str[i]='a';
else if(str[i]>='A' && str[i]<='Y'){
str[i]+=32+1;
}
}
cout << str <<endl;
}
return 0;
}
主要思路：
#include <iostream>
#include <unordered_map> // 出现统计次数就想起hash
#include <algorithm>
#include <climits> // INT_MAX
using namespace std;
int main(){
string str;
//当 cin>> 从缓冲区中读取数据时，若缓冲区中第一个字符是空格、tab或换行这些分隔符时，
//cin>> 会将其忽略并清除，继续读取下一个字符，若缓冲区为空，则继续等待
while(cin>>str){ // 有很多组测试用例输入
unordered_map<char, int> hash;
int muninum = INT_MAX;
for(int i =0; i<str.size(); i++){
hash[str[i]]++; // 初始化
}
for(int i =0; i<str.size(); i++){
muninum = min(hash[str[i]], muninum);
}
for(int i =0; i<str.size(); i++){
if(hash[str[i]]>muninum){
cout << str[i];
}
}
cout << endl;
}
}
主要思路：
#include <iostream>
#include <vector>
using namespace std;
string String_Sorting(string str){
vector<char> vec; // 用一个 char 型的向量存储按规则排序后的字符串中的字母字符
// 规则一：英文字母从 A 到 Z 排列，不区分大小写
// 规则二：同一个英文字母的大小写同时存在时，按照输入顺序排列
for(int j=0; j<26; j++){
for(int i=0; i<str.size(); i++){
if((str[i]-'a'==j)|| (str[i]-'A')==j){ // 字符相减是ASCII相减
vec.push_back(str[i]); // 将符合规则的字母字符先后写入向量,比如A在a前面，那么A先入列
}
}
}
// 规则三：非英文字母的其它字符保持原来的位置
for(int i=0, k=0;(i<str.size())&&(k<vec.size());i++){
if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){
str[i]=vec[k];
++k;
}
}
return str;
}
int main(){
string str;
while(getline(cin, str)){ // 每一行输入处理，测试用例有很多行
cout <<String_Sorting(str) << endl;
}
return 0;
}
主要思想:
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n; // 字典中单词的个数
// 测试用例有多个，所以在每个测试用例第一个输入用while
while(cin>>n){
vector<string> dic; // 字典
string word;
// 字典初始化
for(int i=0; i<n;i++){
cin>>word;
dic.push_back(word);
}
string target; // 目标单词
cin>>target;
int index; // 输出兄弟单词索引
cin>>index;
// 输入处理完毕，开始处理
// 搜索兄弟单词
vector <string> res; // 记录所有兄弟单词
// 将目标单词和字典单词排序后比较他们是否相等来判断他们是否是兄弟单词
string temp = target;
sort(temp.begin(), temp.end()); // 排序
int lent = target.size(); // 目标单词的长度
// 对字典中的单词做同样的排序操作，并比较
for(int i=0; i<n; i++){
int lendic=dic[i].size();
// 长度不同或者相同，则不是兄弟单词
if((lendic==lent) && (target!=dic[i])){
string tempdic = dic[i];
sort(tempdic.begin(), tempdic.end());
if(temp==tempdic){
res.push_back(dic[i]);
}
}
}
// 现在所有兄弟单词都在res中
// 坑 一定要对res进行字典排序
sort(res.begin(), res.end());
cout<<res.size()<< endl;
// 默认了index - 1 < res.size(), 其实没有
if(index-1<res.size()){
cout<<res[index-1]<<endl;
}
}
return 0;
}
主要思想
比如解密
B<-c: str[i]为c= str[i]-32-1;
a<-B: str[i]为B=str[i]+32-1;
在‘a’和‘A’需要特判
同时对于数字
加密：
‘0’～‘8’ ：str[i]=str[i]+1
在‘9’特判断
解密：
‘1’～‘9’ ：str[i]为1=str[i]-1；
在‘0’特判断
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
// 字符串加密
void Encrypt(string& aucPassword, string& aucResult){
int len = aucPassword.size();
for(int i=0; i<len; i++){
// 遇到大写字母
if(aucPassword[i]=='Z')
aucResult[i]='a';
else if(aucPassword[i]>='A'&&aucPassword[i]<='Y'){
aucResult[i]=aucPassword[i]+32+1; // A->b
}
// 遇到小写字母
else if(aucPassword[i]=='z')
aucResult[i]='A';
else if(aucPassword[i]>='a'&&aucPassword[i]<='y'){
aucResult[i]=aucPassword[i]-32+1; // a->B
}
// 遇到数字
else if(aucPassword[i] == '9')
aucResult[i] = '0';
else if(aucPassword[i] >= '0' && aucPassword[i] < '9'){
aucResult[i]=aucPassword[i]+1; // '0'->'1'
}
}
}
void unEncrypt(string& result, string& password){
// 开始解密
for(int i=0; i<password.size(); i++){
// 遇到大写字母
if(password[i]=='A')
result[i]='z';
else if(password[i]>='B'&&password[i]<='Z'){
result[i]=password[i]+32-1; // a<-B
}
// 遇到小写字母
else if(password[i]=='a')
result[i]='Z';
else if(password[i]>='b'&&password[i]<='z'){
result[i]=password[i]-32-1; // A<-b
}
// 遇到数字
else if(password[i] == '0')
result[i] = '9';
else if(password[i] >= '1' && password[i] <= '9'){
result[i]=password[i]-1;
}
}
}
int main(){
string str1;
string str2;
while(cin >> str1 >> str2){
string result1 = str1; // 初始化size()一样
string result2 = str2; // 初始化size()一样
Encrypt(str1, result1);
unEncrypt(result2, str2);
cout << result1 << '\n' << result2 << endl;
}
return 0;
}
主要思路：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const string helper1 = "0123456789abcdefABCDEF";
const string helper2 = "084C2A6E195D3B7F5D3B7F";
string ProcessString(string& mergestr){
// 奇数 偶数 分别拆开
string strji, strou;
for(int i=0; i<mergestr.size(); i++){
if(i%2==0)
strou +=mergestr[i];
else
strji +=mergestr[i];
}
// 奇数偶数排序
sort(strji.begin(), strji.end());
sort(strou.begin(), strou.end());
// 合并新的
int index=0;
for(int i=0; i<mergestr.size(); i++){
if(i%2==0)
mergestr[i]=strou[i/2];
else
mergestr[i]=strji[i/2];
}
// 开始加密
for(int i=0; i<mergestr.size(); i++){
int idx=helper1.find(mergestr[i]);
if(idx!=-1) // 说明能找到是数字或者a～f A～F
mergestr[i]=helper2[idx];
}
return mergestr;
}
int main(){
string str1, str2;
while(cin>>str1){
cin>>str2;
string mergestr;
mergestr=str1+str2;
mergestr=ProcessString(mergestr);
cout << mergestr<<endl;
}
return 0;
}
主要思路
#include <iostream>
#include <vector>
using namespace std;
int main(){
string str;
while(getline(cin, str)){
vector<string> word; // 保存每个单词
string temp ="";
for(int i=0; i<str.size(); i++){
// 字母才用来保存，间隔符就不用了
if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){
temp+=str[i];
}
else{
// else遇到空格符了
// 此时准备push一个单词
if(temp.size()>0){
word.push_back(temp);
// temp清空
temp="";
}
}
}
// 所有单词都进word了，除了最后一个单词
if(temp.size()>0){
word.push_back(temp);
}
// 倒序输出word
for(int i=word.size()-1; i>0; i--){
cout << word[i] <<' '; // 要保持每一个单词后带一个空格，所以第一个单词没有输出
}
// 输出第一个单词
cout<<word[0]<<endl;
}
return 0;
}
主要思想：
#include <iostream>
using namespace std;
int main(){
string key, s;
while(getline(cin, key)){
getline(cin, s);
// 创建加密表
string alp; // 加密表
// hash表,用数组的0和1,来表示
//1. 首先根据key来创建加密表
int p[26]={0}; // 对应26个字母表
for(int i=0; i<key.size();i++){
// 小写字母
if(key[i]>='a'&&key[i]<='z'){
// hash
if(p[key[i]-'a']==0){
p[key[i]-'a']=1;
alp+=key[i]-32; // 统一大写
}
}
// 大写字母
if(key[i]>='A'&&key[i]<='Z'){
// hash
if(p[key[i]-'A']==0){
p[key[i]-'A']=1;
alp+=key[i]; // 统一大写
}
}
}
// 将字母表剩余字母填充到alp
for(int i=0; i<26;i++){
if(p[i]==0)
alp+= 'A'+i;
}
// 查表输入明文输出暗文: 明文是小写，暗文就对应小写
// s
for(int i=0; i<s.size(); i++){
if(s[i]>='a' && s[i]<='z'){
char c = alp[s[i]-'a']+32; // s[i]-'a'即为在26个字母表中的位置，如果为1则在b即，去alp中索引位置为1的字母，由于alp之前全为大写所以这里要加32变小写
cout << c;
}
if(s[i]>='A' && s[i]<='Z'){
char c = alp[s[i]-'A']; // s[i]-'a'即为在26个字母表中的位置，如果为1则在b即，去alp中索引位置为1的字母
cout << c;
}
}
cout << endl;
}
return 0;
}
// 暴搜法+memo
#include <iostream>
#include <string>
#include <vector>
#include <limits.h>
using namespace std;
int dfs(int i, int j, vector<vector<int>>& memo, string s1, string s2){
//有一个已经到头了(此处已经包括处理了两个都到头的情况)
//dp(i, j)的含义：s1[0,i)左闭右开与s2[0,j)左闭右开, 最少操作数
if(i==-1) return j+1;
if(j==-1) return i+1;
if(memo[i][j]>0) return memo[i][j];
if(s1[i]==s2[j]){
memo[i][j]=dfs(i-1,j-1, memo, s1, s2);
}
else{
int operator1 = dfs(i-1,j, memo, s1, s2)+1;
int operator2 = dfs(i,j-1, memo, s1, s2)+1;
int operator3 = dfs(i-1,j-1, memo, s1, s2)+1;
memo[i][j]=min(operator1, min(operator2, operator3));
}
return memo[i][j];
}
int main(){
string s1;
string s2;
while(cin>>s1>>s2){
// s1->s2
//if(s1.length()==0) return s2.length(); // 加上word2的所有字符
//if(s2.length()==0) return s1.length(); // 删掉word2的所有字符
vector<vector<int>> memo(s1.length(), vector<int>(s2.length()));
cout << dfs(s1.length()-1, s2.length()-1,memo, s1, s2) << endl;
}
return 0;
}
主要思路：
1.m是固定的，返回的子串长度都为m=5
2.因此在str中连续的子串每5个去计数C/G的数量
3.冒泡得到C/G数量最多的一段，然后返回索引，再用substr(index, m)去截取这一段
#include <iostream>
#include <string.h>
#include <limits.h>
#include <vector>
using namespace std;
string maxRatio(string s, int m)
{
int size = s.size();
vector<int> k(size, 0);
vector<int> sum(size, 0);
for (int i = 0; i < s.size(); i++)
{
if (s[i] == 'C' || s[i] == 'G')
{
k[i]++;
}
}
// 统计连续k个元素的段的C或者G值
for (int i = 0; i < s.size() - m; i++)
{
for (int j = 0; j < m; j++)
{
sum[i] += k[i + j];
}
}
// 找C或者G值最大的那一个连续k个元素段
int max = INT_MIN;
int idx = 0;
for (int i = 0; i < s.size(); i++)
{
if (sum[i] > max)
{
max = sum[i];
idx = i;
}
}
return s.substr(idx, m);
}
int main()
{
string str;
int n;
while (getline(cin, str))
{
cin >> n;
cout << maxRatio(str, n) << endl;
}
return 0;
}