5901: [字符串] 回文串
三种方法,(1)纯暴力 (2) 算法笔记上面的方法(3)DP
题目描述: 读入一串字符, 判断是否是回文串."回文串" 是一个正读和反读都一样的字符串, 比如 "level" 或者 "noon" 等等就是回文串.
(1)暴力
设置两个变量, 左边界变量 l, 右边界变量 r; 从第一个字符和最后一个字符开始枚举对比, 判断字符是否相同, 额外需要注意的一点是字符串长度为奇数时枚举出口是 l==r, 偶数时判断 l>r 即可
- #include<iostream>
- #include<cstring>
- #include<math.h>
- #include<stdlib.h>
- #include<cstring>
- #include<cstdio>
- #include<utility>
- #include<algorithm>
- #include<map>
- using namespace std;
- typedef long long ll;
- const int maxn=1005;
- int dp[maxn][maxn];
- int main( )
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- //freopen("a.txt","r",stdin);
- //freopen("a.txt","w",stdout);
- string s;
- cin>>s;
- int len=s.length();
- int l=0,r=len-1;
- int flag=1;
- while(1){
- if(s[l]==s[r]){
- if(l==r||l>r)break;
- l++;
- r--;
- continue;
- }
- else{
- flag=0;
- break;
- }
- }
- if(flag)cout<<"YES";
- else cout<<"NO";
- return 0;
- }
- View Code
(2)算法笔记上面的方法
即只遍历字符串前一半, 设置 len 为字符串长度(但不需要取到 i==len/2)
若出现 for(int i=0;i<len;++i)s[i]!=s[len-1-i]时, 则此字符串非回文串
(3)DP 后补
1001 A+B Format (20 分)
题目描述: 输入两个数字, 相加, 输出格式为每 3 个数字之间一个分号(从个位开始算), 数字<= 三位数不考虑逗号
思路: 将两个数字相加后得到的整型数通过 to_string 函数转为字符串 (必须为正数 -> 方便, 转换前预处理一下就好了), 然后从个位开始判断, 计数变量从 0 开始,%3 为 0 时添加一个逗号, 并将计数变量清零.
- #include<iostream>
- #include<sstream>
- #include<cstring>
- #include<cstdlib>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- const int maxn = 1005;
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- //freopen("a.txt","r",stdin);
- //freopen("a.txt","w",stdout);
- /*double n = 3.1415926;
- string s =std::to_string(n);
- cout <<s[0]<<endl; // 结果是 3
- cout << s<<endl; // 结果是 3.1415926*/
- /*string s1 = "2018.11";
- int a1 = stod(s1);
- cout << a1<<endl;
- /* 数字转字符串 */
- int a, b;
- cin>> a>> b;
- int temp = a + b;
- if (temp <0){
- cout << "-";temp *= -1;
- }
- string s=to_string(temp);
- //cout << s << endl;
- int len = s.length();
- if (len < 4){
- cout << s << endl;
- return 0;
- }
- int cnt = 0;
- string ans;
- for (int i = len-1; i> -1; --i){
- if (cnt % 3 == 0&&cnt!=0){
- ans += ",";
- cnt = 0;
- }
- ans +=s[i];
- cnt++;
- }
- reverse(ans.begin(),ans.end());
- cout <<ans << endl;
- return 0;
- }
- View Code
- 1035 Password (20 分)
题目描述: 输入用户名和密码,@替换 1,% 替换 0,L 替换 l,o 替换 O, 如果所有测试样例都正确 (即不需要替换), 输出(题目所给的那一串, 只需要注意一组正确与多组正确的区别即可) 否则输出错误的样例有几个
思路: 由于需要输出错误样例个数, 所以需要先储存所有样例, 再进行处理, 以结构体数组存储, 结构体成员变量为两个 string, 一个 int 变量, 分别用来存储用户名与密码, 以及此样例是否已修改. 另外设置一个 int 变量来判断是否有样例修改.
- #include<iostream>
- #include<cstring>
- #include<math.h>
- #include<stdlib.h>
- #include<cstring>
- #include<cstdio>
- #include<utility>
- #include<algorithm>
- #include<map>
- using namespace std;
- typedef long long ll;
- const int maxn=1005;
- struct node{
- string s1,s2;
- int flag;
- }star[maxn];
- int main( )
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- //freopen("a.txt","r",stdin);
- //freopen("a.txt","w",stdout);
- int t;
- int flag=1;
- cin>>t;
- for(int j=0;j<t;++j){
- cin>>star[j].s1>>star[j].s2;
- int len=star[j].s2.length();
- for(int i=0;i<len;++i){
- if(star[j].s2[i]=='1')star[j].s2[i]='@',star[j].flag=1,flag=0;
- else if(star[j].s2[i]=='l')star[j].s2[i]='L',star[j].flag=1,flag=0;
- else if(star[j].s2[i]=='0')star[j].s2[i]='%',star[j].flag=1,flag=0;
- else if(star[j].s2[i]=='O')star[j].s2[i]='o',star[j].flag=1,flag=0;
- }
- }
- int cnt=0;
- for(int i=0;i<t;++i){
- if(star[i].flag==1){
- //cout<<star[i].s1<<" "<<star[i].s2<<endl;
- flag=0,++cnt;
- }
- }
- if(flag&&t==1){
- cout<<"There is 1 account and no account is modified"<<endl;
- return 0;
- }
- else if(flag&&t>1){
- cout<<"There are"<<t<<"accounts and no account is modified"<<endl;
- return 0;
- }
- cout<<cnt<<endl;
- for(int i=0;i<t;++i){
- if(star[i].flag==1){
- cout<<star[i].s1<<" "<<star[i].s2<<endl;
- }
- }
- return 0;
- }
- View Code
- 1077 Kuchiguse (20 分)
题目描述: 给定多个字符串求出他们的最长公共后缀(suffix)
思路: 代码中用了两种方法, 第一种看起来比较乱, 第二种比较简洁;
先对字符串进行预处理, 我们还是习惯从第一个字符开始判断, 所以 reverse 一下, 并取一个最小字符串长度, 循环中每次取出一个字符(可取任意字符串的), 设为 now, 判断所有字符串该位置的字符是否相同, 只要有一个字符串在该位置的字符与 now 不同则退出, 若有相同, 则将计数变量 + 1
- #include<iostream>
- #include<cstring>
- #include<math.h>
- #include<stdlib.h>
- #include<cstring>
- #include<cstdio>
- #include<utility>
- #include<algorithm>
- #include<map>
- using namespace std;
- typedef long long ll;
- inline int read(){
- int X=0,w=0;char ch=0;
- while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
- while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
- return w?-X:X;
- }
- /*------------------------------------------------------------------------*/
- const int maxn=105;
- string s[maxn];
- int main( )
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- //freopen("a.txt","r",stdin);
- //freopen("a.txt","w",stdout);
- int t;
- cin>>t;
- getline(cin,s[0]);
- int min_len=999;
- for(int i=0;i<t;++i){
- getline(cin,s[i]);
- //cout<<s[i]<<endl;
- reverse(s[i].begin(),s[i].end());
- int len=s[i].length();
- min_len=min(len,min_len);
- }
- /************************/
- /*********** 方法一 *************/
- /*string now=s[0];
- string ans;
- int flag=1;
- for(int i=1;i<t;++i){
- string temp;
- if(flag==0)break;
- int now_flag=1;// 此次是否匹配成功
- for(int j=0;j<now.length();++j){
- if(s[i][j]==now[j]){
- temp+=now[j];
- ans=temp;
- }
- else if(s[i][j]!=now[j]){
- if(j==0){// 第一个字符匹配不上 , 说明不存在公共后缀
- flag=0;
- break;
- }
- else{
- now=ans;
- break;
- }
- }
- }
- }
- reverse(ans.begin(),ans.end());
- if(flag)cout<<ans<<endl;
- else cout<<"nai"<<endl;*/
- /************************/
- /*********** 方法二 *************/
- string ans;
- int cnt=0;
- int flag=1;
- for(int i=0;i<min_len;++i){
- if(flag==0)break;
- char now=s[0][i];// 第一个字符
- int now_flag=1;
- for(int j=1;j<t;++j){
- if(now!=s[j][i]){// 若有一个字符不相同则退出
- now_flag=0;
- break;
- }
- }
- if(now_flag){// 若所有字符串第 i 位相同, 则计数 + 1
- cnt++;
- }
- else break;
- }
- //reverse(ans.begin(),ans.end());
- if(cnt){
- for(int i=0;i<cnt;++i)ans+=s[0][i];
- reverse(ans.begin(),ans.end());
- cout<<ans<<endl;
- }
- else cout<<"nai"<<endl;
- return 0;
- }
- View Code
- 1077 Kuchiguse (20 分)
题目描述:
思路:
来源: http://www.bubuko.com/infodetail-3387434.html