回文串的特性(回文算法思路)

什么是回文串?
「回文串」是一个正读和反读都一样的字符串,比如 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

      (0)
      小道研究's avatar小道研究
      上一篇 2024年4月15日 下午2:09
      下一篇 2024年4月15日 下午2:11

      相关推荐

      发表回复

      您的邮箱地址不会被公开。 必填项已用 * 标注