回文串的特性（回文算法思路）

什么是回文串？

「回文串」是一个正读和反读都一样的字符串，比如 level 或 noon 就是回文串。

来，看道题 …

题目：9. 回文数

难度：简单

链接：https://leetcode-cn.com/problems/palindrome-number/

内容：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。例如：121 是回文，而 123 不是。

我思考了一下，想到的解法是用：双指针「头尾」，思路也很简单。

不过，我在解这个题目的时候，刚开始用双指针没解出来 … 因为考虑到了「负数」，然后我去看了看题目，负数就直接返回 false ，那就好解了。

var isPalindrome = function (x) {    //转成数组    const copyX = Array.from(x.toString());    //如果长度为1，直接返回    if (copyX.length === 1) return true;    //定义两个指针    let i = 0, j = copyX.length - 1    while (i <= j) {        //如果头尾两指针数据相等，则 i前进一步，j回退一步；        if (copyX[i] === copyX[j]) {            i++;            j--;            continue;        } else {            return false;        }    }    return true;};

解完以后，觉得还行。

11510 / 11510 个通过测试用例执行用时: 152 ms内存消耗: 46.8 MB

顺手又去看了看力扣的题解，得到了一些启发。

一、普通解法

把数字转成字符串，字符串转成数组，数组反转，反转完后，转成数字，对比：

var isPalindrome = function (x) {    //先转成字符串，然后转成数组，转完数组后反转一下；    const copyX = Array.from(x.toString()).reverse();    //把反转的字符串拼成字符串，随后转成数字；    const result = parseInt(copyX.join(\\\'\\\'), 10)    //对比    if (x === result) {        return true;    } else {        return false;    }};

11510 / 11510 个通过测试用例执行用时: 156 ms内存消耗: 47 MB

这个逻辑应该大家是最先想到的，因为它最符合直觉，对比直觉嘛。

二、取整和余数

这个方法还是很巧妙的，通过取整和余数来获取对应的数字进行比较。

举个例子：1221 这个数字。

通过计算 1221 / 1000，得首位1

通过计算 1221 % 10，可得末位 1

进行比较

再将 22 取出来继续比较 …

我看了力扣题解那么多答案，都是通过取整和余数来对比实现。

双指针多香啊，取什么余啊 …

这个解法，我没尝试，有兴趣的可以试试 …

三、双向删除元素

最后去国际站看了看，真有神人呐，看代码：

var isPalindrome = function(x) {    //转成数组    const arr = String(x).split(\\\'\\\');    //有长度则进入 while 循环    while (arr.length > 1) {        //每次循环都取第一个和最后一个来比对；        if (arr.shift() !== arr.pop()) {            return false;        }    }    return true;};

shift() 和 pop() 方法一出，佩服。

图片授权基于 www.pixabay.com 相关协议

参考资料：

[1]https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921

[2]https://leetcode-cn.com/problems/palindrome-number/solution/hui-wen-shu-by-leetcode-solution/

[3]https://leetcode.com/problems/palindrome-number/discuss/?currentPage=1&orderBy=most_votes&query=

原创文章，作者：小道研究，如若转载，请注明出处：https://www.sudun.com/ask/34585.html