本文共 1978 字，大约阅读时间需要 6 分钟。
回文：palindrome
从字符串头尾开始向中间扫描字符串，这只需维护头部和尾部两个扫描指针即可。
时间复杂度O(n)，空间复杂度O(1)。bool IsPalindrome(const char *s, int n) { // 非法输入 if (s == NULL || n < 1) { return false; } const char* front,*back; // 初始化头指针和尾指针 front = s; back = s+ n - 1; while (front < back) { if (*front != *back) { return false; } ++front; --back; } return true; } 从中间向两边扩展。
时间复杂度O(n)，空间复杂度O(1)。bool IsPalindrome2(const char *s, int n) { if (s == NULL || n < 1) { return false; } const char* first, *second; // m定位到字符串的中间位置 int m = ((n >> 1) - 1) >= 0 ? (n >> 1) - 1 : 0; first = s + m; second = s + n - 1 - m; while (first >= s) { if (*first!= *second) { return false; } --first; ++second; } return true; } 函数原型：bool equal(InputIterator1 first1, InputIterator last1, InputIterator2 first2);
函数功能：equal算法逐一比较l两个序列的元素是否相等，只是equal函数的返回值是true/false，不是返回迭代器值。如果迭代器区间[first1, last1]和迭代器区间[first2, first2+(last1-first1)]上的元素相等，返回true，否则返回false。 函数原型：std::vector::rbegin(); 函数功能：返回反向的第一个元素。#include#include #include bool is_palindrome(const string &s); using namespace std; int main() { string str; cin >> str; if (is_palindrome(const string &str)) { cout << "Yes!" << endl; } else { cout << "Not!" << endl; } return 0; } bool is_palindrome(const string &s) { return equal(s.begin(), s.end(), s.rbegin()); }
bool judge(string s) { string temp = s; reverse(temp.begin(), temp.end()); return temp == s;} 1、判断一条单向链表是不是“回文”
分析：对于单链表结构，可以用两个指针从两端或者中间遍历并判断对应字符是否相等。但这里的关键就是如何朝两个方向遍历。由于单链表是单向的，所以要向两个方向遍历的话，可以采取经典的快慢指针的方法，即先位到链表的中间位置，再将链表的后半逆置，最后用两个指针同时从链表头部和中间开始同时遍历并比较即可。 2、判断栈是不是“回文” 分析：对于栈的话，只需要将字符串全部压入栈，然后依次将各字符出栈，这样得到的就是原字符串的逆置串，分别和原字符串各个字符比较，就可以判断了。转载地址：http://yvtai.baihongyu.com/