【算法题-困难】超级回文数

困难算法题，超级回文数，使用 JavaScript 语言编写

题目

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数 L 和 R ，请按照从小到大的顺序打印包含在范围 [L, R] 中的所有超级回文数。

注：R包含的数字不超过20位

回文数定义：将该数各个位置的数字反转排列，得到的数和原数一样，例如676，2332，10201。

输入格式

L,R。例如4,1000

输出格式

[L, R]范围内的超级回文数，例如[4, 9, 121, 484]

输入样例

输入样例一：

4,1000

输出样例

[4, 9, 121, 484]

分析

解答

// 这是题目要求的输入格式
let inputs = `
4,1000
`;

inputs = inputs.trim().split(',').map(BigInt);

var superPalindromesInRange = function(left, right) {
  let checkPalindromes = function(num) {
    return Array.from(num.toString()).reverse().join("") === num.toString()
  };

  // 构造奇数、偶数回文数，比如 123 -> 12321, 123321
  let makePalindromes = function(num) {
    let numStr = num.toString();
    let revNumStr = Array.from(numStr).reverse().join("");
    // num: 20000  ->  [2000000002n, 200000002n] 都是回文数
    return [BigInt(numStr + revNumStr), BigInt(numStr + revNumStr.slice(1))];
  };

  let ans = []; 
  // 从 1 开始构造回文数
  // 因为最大就是20位数，所以这里构造回文数肯定不会超 100000，因为 100000 的回文数是 100000000001，它的平方是 10000000000200000000001n，已经超过 20 位数了
  for(let i = 1; i < 100000; i++) {
    let [p1, p2] = makePalindromes(i);
    let pp1 = BigInt(p1 * p1);
    let pp2 = BigInt(p2 * p2);
      
    if(pp1 >= left && pp1 <= right && checkPalindromes(pp1)) {
      ans.push(pp1.toString());
    }

    if(pp2 >= left && pp2 <= right && checkPalindromes(pp2)) {
      ans.push(pp2.toString());
    }
  }
    
  return ans.sort((a, b) => a - b);
};


// 示例
console.log(`[${superPalindromesInRange(inputs[0], inputs[1]).join(', ')}]`);

解释