超级回文数：判断一个数是否为回文数的平方，C++实现两种解法

{/'title/':/'超级回文数：判断一个数是否为回文数的平方，C++实现两种解法/',/'description/':/'本文探讨了超级回文数的概念，即一个数既是回文数，又是回文数的平方。文章提供了两种C++实现方法：暴力法和回文数的构造方法，并分析了两种方法的时间复杂度。/',/'keywords/':/'超级回文数, 回文数, 平方, C++, 暴力法, 回文数构造/',/'content/':/'如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。//n//n现在，给定两个正整数//u00a0L 和//u00a0R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数//n//n请用C++完成编程内容：解法一：暴力法//n//n首先，我们需要判断一个数是否是回文数。可以将这个数转换为字符串，然后判断字符串是否是回文串。//n//n接下来，我们可以遍历范围 [L, R] 中的每个数，判断该数是否是回文数。如果是回文数，则判断该数的平方是否也是回文数。如果都是回文数，则将该数添加到结果集中。//n//n具体实现如下：//n//ncpp//nclass Solution {//npublic://n bool isPalindrome(int num) {//n string s = to_string(num);//n int left = 0, right = s.length() - 1;//n while (left < right) {//n if (s[left++] != s[right--]) {//n return false;//n }//n }//n return true;//n }//n//n int superpalindromesInRange(string L, string R) {//n int count = 0;//n long long left = stoll(L), right = stoll(R);//n for (long long i = 1; i <= 1e5; i++) {//n string s = to_string(i);//n for (int j = s.length() - 2; j >= 0; j--) {//n s += s[j];//n }//n long long num = stoll(s);//n long long square = num * num;//n if (square > right) {//n break;//n }//n if (square >= left && isPalindrome(num) && isPalindrome(square)) {//n count++;//n }//n }//n return count;//n }//n};//n//n//n解法二：回文数的构造//n//n我们可以观察到，一个回文数的平方的长度一定是奇数。因为一个奇数长度的回文数的平方的最高位和最低位一定是1，否则不可能是回文数。//n//n所以，我们只需要从1到1e5遍历所有的奇数长度的回文数，然后判断该回文数的平方是否在范围 [L, R] 中即可。//n//n具体实现如下：//n//ncpp//nclass Solution {//npublic://n bool isPalindrome(long long num) {//n long long temp = num, reverseNum = 0;//n while (temp > 0) {//n reverseNum = reverseNum * 10 + temp % 10;//n temp /= 10;//n }//n return reverseNum == num;//n }//n//n int superpalindromesInRange(string L, string R) {//n int count = 0;//n long long left = stoll(L), right = stoll(R);//n for (int i = 1; i <= 100000; i++) {//n string s = to_string(i);//n string rs = s;//n reverse(rs.begin(), rs.end());//n long long num = stoll(s + rs);//n long long square = num * num;//n if (square > right) {//n break;//n }//n if (square >= left && isPalindrome(square)) {//n count++;//n }//n }//n for (int i = 1; i <= 100000; i++) {//n string s = to_string(i);//n string rs = s.substr(0, s.length() - 1);//n reverse(rs.begin(), rs.end());//n long long num = stoll(s + rs);//n long long square = num * num;//n if (square > right) {//n break;//n }//n if (square >= left && isPalindrome(square)) {//n count++;//n }//n }//n return count;//n }//n};//n//n//n以上两种解法的时间复杂度均为 O(1e5 * logN)，其中 N 是范围 [L, R] 的长度。/