type
status
date
slug
summary
tags
category
icon
password
题目:超级回文数
如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为超级回文数。
现在,给定两个正整数
L
和 R
(以字符串形式表示),返回包含在范围 [L, R]
中的超级回文数的数目。示例:
提示:
1 <= len(L) <= 18
1 <= len(R) <= 18
L
和R
是表示[1, 10^18)
范围的整数的字符串。
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%的用户
- Author:Zinphy
- URL:https://zouysay.cn/article/a035f9d1-0c0b-42d3-b238-79f64a1b49df
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!