如果一个正整数自身是回文数而且它也是一个回文数的平方那么我们称这个数为超级回文数。现在给定两个正整数 L 和 R 以字符串形式表示返回包含在范围 L R 中的超级回文数请用C++完成编程

解法一：暴力法

首先，我们需要判断一个数是否是回文数。可以将这个数转换为字符串，然后判断字符串是否是回文串。

接下来，我们可以遍历范围 [L, R] 中的每个数，判断该数是否是回文数。如果是回文数，则判断该数的平方是否也是回文数。如果都是回文数，则将该数添加到结果集中。

具体实现如下：

class Solution {
public:
    bool isPalindrome(int num) {
        string s = to_string(num);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }

    int superpalindromesInRange(string L, string R) {
        int count = 0;
        long long left = stoll(L), right = stoll(R);
        for (long long i = 1; i <= 1e5; i++) {
            string s = to_string(i);
            for (int j = s.length() - 2; j >= 0; j--) {
                s += s[j];
            }
            long long num = stoll(s);
            long long square = num * num;
            if (square > right) {
                break;
            }
            if (square >= left && isPalindrome(num) && isPalindrome(square)) {
                count++;
            }
        }
        return count;
    }
};

解法二：回文数的构造

我们可以观察到，一个回文数的平方的长度一定是奇数。因为一个奇数长度的回文数的平方的最高位和最低位一定是1，否则不可能是回文数。

所以，我们只需要从1到1e5遍历所有的奇数长度的回文数，然后判断该回文数的平方是否在范围 [L, R] 中即可。

具体实现如下：

class Solution {
public:
    bool isPalindrome(long long num) {
        long long temp = num, reverseNum = 0;
        while (temp > 0) {
            reverseNum = reverseNum * 10 + temp % 10;
            temp /= 10;
        }
        return reverseNum == num;
    }

    int superpalindromesInRange(string L, string R) {
        int count = 0;
        long long left = stoll(L), right = stoll(R);
        for (int i = 1; i <= 100000; i++) {
            string s = to_string(i);
            string rs = s;
            reverse(rs.begin(), rs.end());
            long long num = stoll(s + rs);
            long long square = num * num;
            if (square > right) {
                break;
            }
            if (square >= left && isPalindrome(square)) {
                count++;
            }
        }
        for (int i = 1; i <= 100000; i++) {
            string s = to_string(i);
            string rs = s.substr(0, s.length() - 1);
            reverse(rs.begin(), rs.end());
            long long num = stoll(s + rs);
            long long square = num * num;
            if (square > right) {
                break;
            }
            if (square >= left && isPalindrome(square)) {
                count++;
            }
        }
        return count;
    }
};

以上两种解法的时间复杂度均为 O(1e5 * logN)，其中 N 是范围 [L, R] 的长度