超级回文数
00 min
2024-7-18
2024-7-22
type
status
date
slug
summary
tags
category
icon
password
 

题目:超级回文数

 
如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为超级回文数。
现在,给定两个正整数 L 和 R (以字符串形式表示),返回包含在范围 [L, R] 中的超级回文数的数目。
 
示例:
 
提示:
  1. 1 <= len(L) <= 18
  1. 1 <= len(R) <= 18
  1. L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
  1. int(L) <= int(R)
 

题解思路

方法1:暴力枚举

最开始使用最朴素的解法,找出所有回文数x及其x^2也是回文数,且x^2[left,right]之间。但是这种解法并没有通过,显示超时。
 
 
方法2:回文数拼接 如果我们遍历每个数,自己去拼接后面的数形成回文数呢,会不会快一些?这时区分两种情况:
数字总长度为奇数个,如num为1234,拼上后就是1234321 数字总长度为偶数个,如num为123,拼上后就是123321 执行用时:292 ms, 在所有 JavaScript 提交中击败了75.00%的用户 内存消耗:56.5 MB, 在所有 JavaScript 提交中击败了75.00%的用户
 
 
这次稳定在75%的基准了,还有没有可优化的空间,有的。此时我们再做一次剪枝,如果一个数的个数为>3,则不可能是回文数了。
我们加上以下代码:
// num就是原始未拼接回文的字符串,如num=123,拼接回文数后就是123456,这时num[0]实际上就是回文数的个位数 if (num[0] > 3) continue;
 
最终完整代码如下: 执行用时:164 ms, 在所有 JavaScript 提交中击败了100.00%的用户 内存消耗:58 MB, 在所有 JavaScript 提交中击败了25.00%的用户
 
上一篇
最多能完成排序的块 II
下一篇
判断二分图