算法(37)-回文数总结

回文

 2024/03/15 

回文数

动态规划

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

时间复杂度：O(n^2)
空间复杂度：O(n^2)

双指针法

在遍历中心点的时候，要注意中心点有两种情况，也就是奇数和偶数的场景。

核心代码：

function func(str) {
  const len = str.length;
  let res = '';
  for(let i = 0; i < 2 * len - 1; i++) {
    let left = Math.floor(i / 2);
    let right = left + i % 2;
    let temp = left === right ? -1 : 0;
    while(left >= 0 && right < len && str[left] === str[right]) {
      left--;
      right++;
      temp+=2;
    }
  }
}

时间复杂度：O(n^2)
空间复杂度：O(1)

回文数的判定

纯数字

function reverse(n) {
    let res = 0;
    while (n > 0) {
        res = 10 * res + (n % 10);
        n = Math.floor(n / 10);
    }
    return res;
}

function isPlindrome(n) {
    return n === reverse(n);
}

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/15/2024-03-15-%E7%AE%97%E6%B3%95(37)-%E5%9B%9E%E6%96%87%E6%95%B0%E6%80%BB%E7%BB%93/

发表日期：March 15th 2024, 11:59:56 pm

更新日期：March 17th 2024, 11:37:44 pm

Next Post

算法(38)-栈与队列
Previous Post

算法(36)-超级回文数

CATALOG

1. 回文数
1. 1.1. 动态规划
2. 1.2. 双指针法
2. 回文数的判定
1. 2.1. 纯数字