超级回文数

906. 超级回文数

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

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

示例：

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

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int superpalindromesInRange(string left, string right) { } };

golang 解法, 执行用时: 148 ms, 内存消耗: 6.6 MB, 提交时间: 2023-07-12 10:03:24

func superpalindromesInRange(left string, right string) int {
	l, _ := strconv.Atoi(left)
	r, _ := strconv.Atoi(right)
	magic := 100000
	result := 0
	// 奇数位数 1234321
	for k := 1; k < magic; k++ {
		sb := strconv.Itoa(k)
		for i := len(sb) - 2; i >= 0; i-- {
			sb += string(sb[i])
		}
		v, _ := strconv.Atoi(sb)
		v *= v
		if v > r {
			break
		}
		if v >= l && isPalindrome(v) {
			result++
		}
	}
	// 偶数位数 12344321
	for k := 1; k < magic; k++ {
		sb := strconv.Itoa(k)
		for i := len(sb) - 1; i >= 0; i-- {
			sb += string(sb[i])
		}
		v, _ := strconv.Atoi(sb)
		v *= v
		if v > r {
			break
		}
		if v >= l && isPalindrome(v) {
			result++
		}
	}
	return result
}

func isPalindrome(num int) bool {
	numStr := strconv.Itoa(num)
	right := len(numStr) - 1
	for i := 0; i <= right/2; i++ {
		if numStr[i] != numStr[right-i] {
			return false
		}
	}
	return true
}

java 解法, 执行用时: 165 ms, 内存消耗: 42.6 MB, 提交时间: 2023-07-12 10:01:26

// 
class Solution {
    public int superpalindromesInRange(String sL, String sR) {
        long L = Long.valueOf(sL);
        long R = Long.valueOf(sR);
        int MAGIC = 100000; // 这个表示超级回文数的开根号后的一半
        int ans = 0;

        // count odd length;
        for (int k = 1; k < MAGIC; ++k) {
            StringBuilder sb = new StringBuilder(Integer.toString(k));
            for (int i = sb.length() - 2; i >= 0; --i)
                sb.append(sb.charAt(i));
            long v = Long.valueOf(sb.toString());
            v *= v;
            if (v > R) break;
            if (v >= L && isPalindrome(v)) ans++;
        }

        // count even length;
        for (int k = 1; k < MAGIC; ++k) {
            StringBuilder sb = new StringBuilder(Integer.toString(k));
            for (int i = sb.length() - 1; i >= 0; --i)
                sb.append(sb.charAt(i));
            long v = Long.valueOf(sb.toString());
            v *= v;
            if (v > R) break;
            if (v >= L && isPalindrome(v)) ans++;
        }

        return ans;
    }

    // 是否回文数字
    public boolean isPalindrome(long x) {
        return x == reverse(x);
    }

    // 数字的逆数
    public long reverse(long x) {
        long ans = 0;
        while (x > 0) {
            ans = 10 * ans + x % 10;
            x /= 10;
        }

        return ans;
    }
}

python3 解法, 执行用时: 56 ms, 内存消耗: 15.8 MB, 提交时间: 2023-07-12 09:56:48

'''
回文数平方仍然为回文数的前提条件就是不能进位, 进位后会导致前后部分必然不同.
已知只有0,1,2,3的平方和不会进位,且3只会在一位的情况下不进位.
所以将9加入列表,并遍历所有的0,1,2组成所有的超级回文数集合
直接寻找左右区间内的超级回文数数量即可求解.
'''

def dfs(n: str, c: int) -> None:
    if c == 0:
        s = int(n) ** 2
        if str(s) == str(s)[::-1]:
            res.append(s)
        return
    if c == i:
        r = range(1, 3)
    else:
        r = range(3)
    for j in r:
        dfs(n + str(j), c - 1)

res = []
for i in range(1, 10):
    dfs('', i)

res.insert(2, 9) # 在索引2处插入9

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        return bisect.bisect_right(res, int(right)) - bisect.bisect_left(res, int(left))

上一题

下一题

详情