Hard

题目描述

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

给定两个用字符串表示的正整数 left 和 right，返回包含在区间 [left, right] 内的超级回文数的个数。

示例 1：

输入：left = "4", right = "1000"
输出：4
解释：4, 9, 121, 484 是超级回文数。
注意 676 不是超级回文数：26 * 26 = 676，但是 26 不是回文数。

示例 2：

输入：left = "1", right = "2"
输出：1

提示：

  • 1 <= left.length, right.length <= 18
  • left 和 right 只包含数字
  • left 和 right 没有前导零
  • left 和 right 表示 [1, 10^18 - 1] 范围内的整数
  • left <= right

解题思路

解题思路

这道题要求找到在给定范围内的超级回文数，即既是回文数又是某个回文数的平方的数。

核心观察： 由于 right 最大为 10^18，所以回文数的平方根最大约为 10^9。我们不需要检查所有可能的数，而是构造所有可能的回文数，然后检查它们的平方是否也是回文数且在给定范围内。

优化策略：

  1. 构造回文数：我们只需要构造回文数的一半，然后镜像得到完整的回文数
  2. 分类讨论：分别处理奇数长度和偶数长度的回文数
    • 奇数长度：如 12321，由 123 构造而来
    • 偶数长度：如 1221，由 12 构造而来
  3. 边界控制：由于平方根最大约为 10^9，我们只需要枚举到 10^5 左右的回文数根

算法步骤：

  1. 从 1 开始枚举回文数的"种子"（回文数的前半部分）
  2. 根据种子构造奇数长度和偶数长度的回文数
  3. 计算每个回文数的平方
  4. 检查平方数是否也是回文数且在给定范围内
  5. 统计符合条件的数量

时间复杂度主要取决于需要枚举的回文数个数，约为 O(√W)，其中 W 是右边界的值。

代码实现

class Solution {
public:
    int superpalindromesInRange(string left, string right) {
        long long L = stoll(left), R = stoll(right);
        int count = 0;
        
        // 枚举回文数的根（前半部分）
        for (int i = 1; i <= 100000; i++) {
            string s = to_string(i);
            
            // 构造奇数长度的回文数
            string odd = s;
            for (int j = s.length() - 2; j >= 0; j--) {
                odd += s[j];
            }
            long long palindrome = stoll(odd);
            long long square = palindrome * palindrome;
            if (square > R) break;
            if (square >= L && isPalindrome(square)) {
                count++;
            }
            
            // 构造偶数长度的回文数
            string even = s;
            for (int j = s.length() - 1; j >= 0; j--) {
                even += s[j];
            }
            palindrome = stoll(even);
            square = palindrome * palindrome;
            if (square > R) break;
            if (square >= L && isPalindrome(square)) {
                count++;
            }
        }
        
        return count;
    }
    
private:
    bool isPalindrome(long long num) {
        string s = to_string(num);
        string rev = s;
        reverse(rev.begin(), rev.end());
        return s == rev;
    }
};

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        L, R = int(left), int(right)
        count = 0
        
        def is_palindrome(num):
            s = str(num)
            return s == s[::-1]
        
        # 枚举回文数的根（前半部分）
        for i in range(1, 100001):
            s = str(i)
            
            # 构造奇数长度的回文数
            odd = s + s[-2::-1]
            palindrome = int(odd)
            square = palindrome * palindrome
            if square > R:
                break
            if square >= L and is_palindrome(square):
                count += 1
            
            # 构造偶数长度的回文数
            even = s + s[::-1]
            palindrome = int(even)
            square = palindrome * palindrome
            if square > R:
                break
            if square >= L and is_palindrome(square):
                count += 1
        
        return count

public class Solution {
    public int SuperpalindromesInRange(string left, string right) {
        long L = long.Parse(left), R = long.Parse(right);
        int count = 0;
        
        // 枚举回文数的根（前半部分）
        for (int i = 1; i <= 100000; i++) {
            string s = i.ToString();
            
            // 构造奇数长度的回文数
            string odd = s;
            for (int j = s.Length - 2; j >= 0; j--) {
                odd += s[j];
            }
            long palindrome = long.Parse(odd);
            long square = palindrome * palindrome;
            if (square > R) break;
            if (square >= L && IsPalindrome(square)) {
                count++;
            }
            
            // 构造偶数长度的回文数
            string even = s;
            for (int j = s.Length - 1; j >= 0; j--) {
                even += s[j];
            }
            palindrome = long.Parse(even);
            square = palindrome * palindrome;
            if (square > R) break;
            if (square >= L && IsPalindrome(square)) {
                count++;
            }
        }
        
        return count;
    }
    
    private bool IsPalindrome(long num) {
        string s = num.ToString();
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        string rev = new string(arr);
        return s == rev;
    }
}

/**
 * @param {string} left
 * @param {string} right
 * @return {number}
 */
var superpalindromesInRange = function(left, right) {
    const leftNum = BigInt(left);
    const rightNum = BigInt(right);
    let count = 0;
    
    function isPalindrome(s) {
        let i = 0, j = s.length - 1;
        while (i < j) {
            if (s[i] !== s[j]) return false;
            i++;
            j--;
        }
        return true;
    }
    
    function generatePalindromes(len, isOdd) {
        const palindromes = [];
        const half = Math.floor(len / 2);
        const start = Math.pow(10, half - 1);
        const end = Math.pow(10, half) - 1;
        
        for (let i = start; i <= end; i++) {
            const left = i.toString();
            const right = left.split('').reverse().join('');
            const palindrome = isOdd ? left + right.slice(1) : left + right;
            palindromes.push(palindrome);
        }
        return palindromes;
    }
    
    for (let len = 1; len <= 9; len++) {
        const palindromes = [];
        if (len === 1) {
            for (let i = 1; i <= 9; i++) {
                palindromes.push(i.toString());
            }
        } else {
            palindromes.push(...generatePalindromes(len, len % 2 === 1));
        }
        
        for (const pal of palindromes) {
            const square = BigInt(pal) * BigInt(pal);
            if (square > rightNum) break;
            if (square >= leftNum && isPalindrome(square.toString())) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(√W × log W)，其中 W 是右边界值，√W 是需要枚举的回文数个数，log W 是每次回文检查的时间
空间复杂度O(log W)，用于存储数字的字符串表示