用html5做的商务网站,乔拓云的品牌推广方案,分析一个网页设计,网站建设如何账务处理博客主页#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 #x1f4af;前言#x1f4af;题目描述输入格式#xff1a;输出格式#xff1a;样例#xff1a; #x1f4af;方法一#xff1a;我的第一种做法思路代码实现解析 #x1f4af;方法二#xff1a;我… 博客主页 [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 前言题目描述输入格式输出格式样例 方法一我的第一种做法思路代码实现解析 方法二我的第二种做法思路代码实现解析改进建议 方法三老师的第一种做法思路代码实现解析优点 方法四老师的第二种做法思路代码实现解析优点缺点 对比分析扩展空间优化和实际应用小结 前言
判断一个字符串是否为回文是编程中常见的问题。回文字符串是指从前往后读与从后往前读都一样的字符串。例如“abcdedcba” 就是回文而 “abcde” 则不是。对于这类问题我们可以采用多种不同的算法来解决。在本篇文章中我们将分析四种不同的做法并进行对比与优化以帮助大家更好地理解如何判断字符串是否为回文。 C 参考手册 题目描述
B2124 判断字符串是否为回文
输入一个字符串判断该字符串是否是回文。回文是指顺读和倒读都一样的字符串。
输入格式
输入一行字符串长度小于100。
输出格式
如果字符串是回文输出 yes否则输出 no。
样例
输入
abcdedcba输出
yes方法一我的第一种做法
思路
我的第一种做法是通过反转字符串来判断回文。首先我们将原字符串反转然后与原字符串进行比较。如果反转后的字符串与原字符串相等则说明原字符串是回文。
代码实现
#include iostream
#include string
using namespace std;int main() {string s;cin s; // 输入字符串int left 0;int right s.size() - 1;// 检查字符串的前半部分是否与后半部分对称while (left right) {if (s[left] ! s[right]) {cout no endl; // 如果有不同字符输出noreturn 0;}left;right--;}cout yes endl; // 如果没有不同字符输出yesreturn 0;
}解析
反转字符串通过双指针方式使用 left 和 right 两个指针分别从字符串的两端开始向中间移动逐个比较字符。时间复杂度O(n)其中 n 是字符串的长度。我们最多需要遍历字符串的前半部分进行字符比较。空间复杂度O(1)仅使用了常数的空间来存储指针 left 和 right。
方法二我的第二种做法
思路
在我的第二种做法中我尝试使用了两次循环首先将字符串反转到一个新的字符串 s2 中然后通过逐字符对比 s2 和原字符串 s1 是否一致来判断回文。
代码实现
#include iostream
#include string
using namespace std;int main() {string s1, s2;while(cin s1) {s2.resize(s1.size()); for(int i s1.size() - 1; i 0; i--) {s2[s1.size() - i - 1] s1[i];}int temp 1;for(int i 0; i s1.size(); i) {if(s2[i] ! s1[i]) {temp 0;break;}}if(temp)cout yes endl;elsecout no endl;}return 0;
}解析
字符串反转首先创建一个 s2 字符串并使用 for 循环反转 s1 字符串的内容存储到 s2 中。回文判断然后通过逐个字符对比 s2 和 s1如果遇到不同的字符则输出 no。存在问题 s2 没有预先调整大小 s2 在反转前没有设置大小可能会导致内存越界。可以通过 resize 来调整其大小。逻辑错误break 的位置存在问题导致判断逻辑不正确跳出循环时判断不够精确。
改进建议
通过双指针法可以优化空间使用并且避免了额外的字符串存储开销。具体改进后我们会在后面介绍。
方法三老师的第一种做法
思路
老师的第一种做法采用了双指针法。这是一种非常高效的方法。通过两个指针分别从字符串的两端开始逐个比较字符如果出现不同的字符就可以直接返回 no否则直到两个指针相遇时输出 yes。
代码实现
#include iostream
#include string
using namespace std;int main() {string s;cin s; // 输入字符串int left 0;int right s.size() - 1;while (left right) {if (s[left] ! s[right]) {cout no endl; // 如果有不同字符输出noreturn 0;}left;right--;}cout yes endl; // 如果没有不同字符输出yesreturn 0;
}解析
双指针法通过两个指针 left 和 right 从字符串的两端向中间逼近。每次比较 s[left] 和 s[right]如果发现不相等直接返回 no否则继续向中间推进。时间复杂度O(n)每次最多需要遍历一次字符串的长度。空间复杂度O(1)只使用了常数空间来存储两个指针。
优点
空间复杂度为 O(1)避免了额外的空间开销。效率高每次只进行一次字符比较比反转字符串的方法更直接且高效。
方法四老师的第二种做法
思路
老师的第二种做法使用了标准库中的 reverse 函数将字符串反转后直接与原字符串进行比较。这是一种简洁的做法但其空间复杂度稍高因为需要额外的存储空间来保存反转后的字符串。
代码实现
#include iostream
#include algorithm
#include string
using namespace std;int main() {string s;cin s;string t s;reverse(t.begin(), t.end()); // 反转字符串if (t s) cout yes endl;elsecout no endl;return 0;
}解析
字符串反转利用 reverse 函数将字符串 s 反转并保存到 t 中。回文判断通过直接比较反转后的字符串 t 和原字符串 s 是否相等来判断回文。
优点
代码简洁通过标准库函数代码更加简洁和易懂。实现简单使用 reverse 可以减少手动反转字符串的工作量。
缺点
空间复杂度为 O(n)因为需要额外的字符串 t 来存储反转后的字符串。
对比分析 空间复杂度 我的第一种做法和老师的第一种做法都使用了 O(1) 空间通过双指针来直接判断回文。我的第二种做法和老师的第二种做法需要额外的 O(n) 空间来存储反转后的字符串。 时间复杂度 所有方法的时间复杂度均为 O(n)其中 n 是字符串的长度。 可读性与简洁性 我的第二种做法和老师的第二种做法通过反转字符串代码简单易懂。我的第一种做法和老师的第一种做法更加高效避免了不必要的空间开销。
扩展空间优化和实际应用
在一些实际应用中空间的使用往往是一个重要的考虑因素。如果我们能够通过优化算法减少空间复杂度将会使得程序更高效。双指针法就是在空间优化方面的一个典型例子它避免了反转字符串时的额外存储。
小结
本文通过分析四种不同的做法来判断字符串是否为回文比较了它们在空间和时间复杂度上的表现。通过这几种做法我们可以发现双指针法在空间和时间上的优势较为明显是最为推荐的解决方案。当然对于小规模的问题使用字符串反转的做法也不失为一种简洁高效的选择。
希望本篇文章能够帮助大家更好地理解字符串回文判断的不同做法并能够根据实际问题选择合适的算法。
