前几道题太简单了,直接跳过
问题 F: 字符串反转
题目描述
小C很喜欢倒着写单词,现在给你一行小C写的文本,你能把每个单词都反转并输出它们吗?
输入
输入包含多组测试样例。第一行为一个整数T,代表测试样例的数量,后面跟着T个测试样例。
每个测试样例占一行,包含多个单词。一行最多有1000个字符。
每个测试样例占一行,包含多个单词。一行最多有1000个字符。
输出
对于每一个测试样例,你应该输出转换后的文本。
样例输入
3 olleh !dlrow I ekil .bulcmca I evol .mca
样例输出
hello world!
I like acmclub.
I love acm.
第一次提交显示编译错误,什么忽略了函数的返回值 (黑人问号...............)
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 void change(char str[]) 8 { 9 int i,j; 10 j=0; 11 char string[50]; 12 if(strlen(str)==1) 13 { 14 printf("%s",str); 15 return ; 16 } 17 for(i=strlen(str)-1;i>=0;i--) 18 { 19 string[j++]=str[i]; 20 } 21 string[j++]=0; 22 printf("%s",string); 23 return ; 24 } 25 26 int main() 27 { 28 int n; 29 scanf("%d",&n); 30 getchar(); 31 while(n--) 32 { 33 char str[1000]; 34 gets(str); 35 int len=strlen(str); 36 str[len]=' '; 37 len++; 38 str[len]=0; 39 char tem[50]; 40 int j=0; 41 for(int i=0;i<len;i++) 42 { 43 if(str[i]!=' ') 44 { 45 tem[j++]=str[i]; 46 } 47 else if(str[i]==' '&&str[i-1]!=' ') 48 { 49 tem[j++]=0; 50 change(tem); 51 j=0; 52 memset(tem,0,sizeof(tem)); 53 if(i!=len-1) printf(" "); 54 } 55 else 56 printf(" "); 57 } 58 printf("\n"); 59 } 60 return 0; 61 } 62 /************************************************************** 63 Problem: 1095 64 User: 201820222 65 Language: C++ 66 Result: 编译错误 67 ****************************************************************/
第二次 把change中的一个return删了,就能编译了(再次黑人问号),但是显示运行错误。
运行时错误,非法的内存访问,数组越界,指针漂移,调用禁用的系统函数等。
猜测数组开小了。。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 void change(char str[]) 8 { 9 int i,j; 10 j=0; 11 char string[50]; 12 for(i=strlen(str)-1;i>=0;i--) 13 { 14 string[j++]=str[i]; 15 } 16 string[j++]=0; 17 printf("%s",string); 18 return ; 19 } 20 21 int main() 22 { 23 int n; 24 scanf("%d",&n); 25 getchar(); 26 while(n--) 27 { 28 char str[1000]; 29 gets(str); 30 int len=strlen(str); 31 str[len]=' '; 32 len++; 33 str[len]=0; 34 char tem[50]; 35 int j=0; 36 for(int i=0;i<len;i++) 37 { 38 if(str[i]!=' ') 39 { 40 tem[j++]=str[i]; 41 } 42 else if(str[i]==' '&&str[i-1]!=' ') 43 { 44 tem[j++]=0; 45 change(tem); 46 j=0; 47 memset(tem,0,sizeof(tem)); 48 if(i!=len-1) printf(" "); 49 } 50 else 51 printf(" "); 52 } 53 printf("\n"); 54 } 55 return 0; 56 } 57 /************************************************************** 58 Problem: 1095 59 User: 201820222 60 Language: C++ 61 Result: 运行错误 62 ****************************************************************/
第三次,完美。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 void change(char str[]) 8 { 9 int i,j; 10 j=0; 11 char string[1001]; 12 for(i=strlen(str)-1;i>=0;i--) 13 { 14 string[j++]=str[i]; 15 } 16 string[j++]=0; 17 printf("%s",string); 18 return ; 19 } 20 21 int main() 22 { 23 int n; 24 scanf("%d",&n); 25 getchar(); 26 while(n--) 27 { 28 char str[1001]; 29 gets(str); 30 int len=strlen(str); 31 str[len]=' '; 32 len++; 33 str[len]=0; 34 char tem[1001]; 35 int j=0; 36 for(int i=0;i<len;i++) 37 { 38 if(str[i]!=' ') 39 { 40 tem[j++]=str[i]; 41 } 42 else if(str[i]==' '&&str[i-1]!=' ') 43 { 44 tem[j++]=0; 45 change(tem); 46 j=0; 47 memset(tem,0,sizeof(tem)); 48 if(i!=len-1) printf(" "); 49 } 50 else 51 printf(" "); 52 } 53 printf("\n"); 54 } 55 return 0; 56 } 57 /************************************************************** 58 Problem: 1095 59 User: 201820222 60 Language: C++ 61 Result: 正确 62 Time:1 ms 63 Memory:1120 kb 64 ****************************************************************/
虽然这题一波三折,但是很开心,内存耗时都最短。
问题 H: 回文子串(easy)
题目描述
输入一个字符串,输出该串的最长回文子串长度
子串:在原串中连续出现的字符串片段
(腾讯面试题)
子串:在原串中连续出现的字符串片段
(腾讯面试题)
输入
只有一行,包含一个字符串,长度不超过100
输出
输出一个整数,即最长回文子串的长度
样例输入
1abcba2
样例输出
5
直接分奇偶,暴力解决
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 int main() 8 { 9 char str[100]; 10 gets(str); 11 int max=0; 12 for(int i=1;i<strlen(str);i++) 13 { 14 int m=1; 15 for(int j=1;;j++) 16 { 17 if(i-j<0||i+j>strlen(str)) 18 break; 19 else if(str[i-j]==str[i+j]) 20 m+=2; 21 else 22 break; 23 } 24 if(m>max) 25 max=m; 26 } 27 for(int i=1;i<strlen(str)-1;i++) 28 { 29 if(str[i]!=str[i+1]) 30 continue; 31 int m=2; 32 for(int j=1;;j++) 33 { 34 if(i-j<0||i+1+j>strlen(str)) 35 break; 36 else if(str[i-j]==str[i+1+j]) 37 m+=2; 38 else 39 break; 40 } 41 if(m>max) 42 max=m; 43 } 44 printf("%d\n",max); 45 return 0; 46 }
还可以设i,j,从两头遍历,利用reverse,交换i和j中间的字串,存到一个临时的数组中,然后看临时数组和原字符串是否相等,相等此时的j-i+1就应为最大
问题 I: 最长公共子序列
题目描述
给你一个序列X和另一个序列Z,当Z中的所有元素都在X中存在,并且在X中的下标顺序是严格递增的,那么就把Z叫做X的子序列。
例如:Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列,Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y,请问它们的最长公共子序列的长度是多少?
例如:Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列,Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y,请问它们的最长公共子序列的长度是多少?
输入
输入包含多组测试数据。每组输入占一行,为两个字符串,由若干个空格分隔。每个字符串的长度不超过100。
输出
对于每组输入,输出两个字符串的最长公共子序列的长度。
样例输入
abcfbc abfcab
programming contest
abcd mnp
样例输出
4 2 0
这题经典DP,以前看过,不过忘得差不多了,先留着吧,下周复习DP时在看
问题 J: 字符串统计的极限
题目描述
给出一个字符串,仅由大小写字母组成,将其中大写字母按照原始顺序挑出,组成新字符串,输出该串。
输入
一行,字符串。1=<长度<=10000000
输出
纯大写构成的串
样例输入
AAaaBBbb
样例输出
AABB
想法没错,但细节没弄好,不说了,往下看吧,哎
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 int main() 8 { 9 char c;10 c=getchar(); 11 while(c!='\n') 12 { 13 if(c>='A'&&c<='Z') 14 printf("%c",c); 15 c=getchar(); 16 } 17 printf("\n"); 18 return 0; 19 } 20 /************************************************************** 21 Problem: 4388 22 User: 201820222 23 Language: C++ 24 Result: 时间超限 25 ****************************************************************/
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 int main() 8 { 9 char c; 10 while(~scanf("%c",&c)) 11 { 12 if(c>='A'&&c<='Z') 13 printf("%c",c); 14 } 15 printf("\n"); 16 return 0; 17 } 18 /************************************************************** 19 Problem: 4388 20 User: 201820222 21 Language: C++ 22 Result: 时间超限 23 ****************************************************************/
最好玩的是下面的,相同的代码,不同的结果。。。。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 int main() 8 { 9 char ch; 10 while((ch=getchar())!=EOF&&ch!='\n') 11 { 12 if(ch>='A'&&ch<='Z') 13 printf("%c",ch); 14 } 15 printf("\n"); 16 return 0; 17 } 18 /************************************************************** 19 Problem: 4388 20 User: 201820222 21 Language: C++ 22 Result: 编译错误 23 ****************************************************************/
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 5 using namespace std; 6 7 int main() 8 { 9 char ch; 10 while((ch=getchar())!=EOF&&ch!='\n') 11 { 12 if(ch>='A'&&ch<='Z') 13 printf("%c",ch); 14 } 15 printf("\n"); 16 return 0; 17 } 18 /************************************************************** 19 Problem: 4388 20 User: 201820222 21 Language: C++ 22 Result: 正确 23 Time:593 ms 24 Memory:1120 kb 25 ****************************************************************/