ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

洛谷 B2124:判断字符串是否为回文 ← STL stack / 双指针 / reverse

洛谷 B2124:判断字符串是否为回文 ← STL stack / 双指针 / reverse

【题目来源】
https://www.luogu.com.cn/problem/B2124

【题目描述】
输入一个字符串,输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。

【输入格式】
输入一行字符串,长度小于 100。

【输出格式】
如果字符串是回文,输出 yes;否则,输出 no。

【输入样例】
abcdedcba

【输出样例】
yes

【算法分析】
● 双指针算法的核心思想
双指针算法的本质是:用两个指针(索引)在一个 / 多个序列(数组、字符串、链表)中移动,通过指针的 “同向 / 反向 / 相向” 移动,替代暴力枚举的嵌套循环,将时间复杂度从 O (n²) 优化到 O (n)。
● 本题简单的方法是利用函数
reverse(s.begin(),s.end());对字符串 s 进行回文判断。
● 本题利用顺序栈求解的代码,详见:https://blog.csdn.net/hnjzsyjyj/article/details/145522672

【算法代码一:STL stack】

#include <bits/stdc++.h> using namespace std; stack<char> stk; int main() { string s; cin>>s; for(char t:s) stk.push(t); for(char t:s) { if(t==stk.top()) stk.pop(); else { cout<<"no"; return 0; } } cout<<"yes"; return 0; } /* in:abcdedcba out:yes */

【算法代码二:双指针】

#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; int i=0,j=s.size()-1; while(i<j) { if(s[i]==s[j]) i++,j--; else { cout<<"no"; return 0; } } cout<<"yes"; return 0; } /* in:abcdedcba out:yes */

【算法代码三:reverse】

#include <bits/stdc++.h> using namespace std; int main() { string s,t; cin>>s; t=s; reverse(s.begin(),s.end()); if(s==t) cout<<"yes"<<endl; else cout<<"no"<<endl; return 0; } /* in:abcdedcba out:yes */




【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/145522672

https://blog.csdn.net/hnjzsyjyj/article/details/158466396



返回列表