leetcode906.超级回文数

题目

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

现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

示例：

输入：L = "4", R = "1000"
输出：4
解释：
4，9，121，以及 484 是超级回文数。
注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。

提示：

1. 1 <= len(L) <= 18
2. 1 <= len(R) <= 18
3. L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
4. int(L) <= int(R)

解答

• 直接求解

1. 首先，将输入的左右边界转换为长整型。
2. 然后，利用两个循环来生成所有可能的回文数：
   • 第一个循环从1到9，将每个数字作为回文数的中心，生成回文数。
   • 第二个循环从1到9999，将每个数字作为回文数的前半部分，并生成回文数的后半部分。

class Solution {
public:
    int superpalindromesInRange(string left, string right) {
        long long leftVal = stoll(left); // 将左边界转换为长整型
        long long rightVal = stoll(right); // 将右边界转换为长整型

        int count = 0;
        // 第一部分：生成所有可能的回文数的前半部分
        for (int i = 1; i <= 9; ++i) {
            generatePalindromes(to_string(i), leftVal, rightVal, count); // 以i为中心，生成回文数
        }
        
        // 第二部分：生成所有可能的回文数的中间部分
        for (int i = 1; i <= 9999; ++i) {
            string leftPart = to_string(i);
            string rightPart = to_string(i);
            reverse(rightPart.begin(), rightPart.end()); // 反转右半部分
            
            generatePalindromes(leftPart + rightPart, leftVal, rightVal, count); // 以i为中心，生成回文数
            for (int j = 0; j <= 9; ++j) {
                generatePalindromes(leftPart + to_string(j) + rightPart, leftVal, rightVal, count); // 以i为中心，生成回文数
            }
        }
        
        return count;
    }
    
private:
    // 生成回文数并判断是否为超级回文数
    void generatePalindromes(string str, long long leftVal, long long rightVal, int& count) {
        long long num = stoll(str);
        num *= num; // 平方得到回文数
        
        if (num > rightVal) {
            return;
        }
        
        if (num >= leftVal && isPalindrome(to_string(num))) {
            ++count;
        }
    }
    
    // 判断是否为回文数
    bool isPalindrome(string str) {
        int left = 0;
        int right = str.length() - 1;
        
        while (left < right) {
            if (str[left] != str[right]) {
                return false;
            }
            
            ++left;
            --right;
        }
        
        return true;
    }
};