2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
现在，给定两个正整数 L 和 R （以字符串形式表示），
返回包含在范围 [L, R] 中的超级回文数的数目。
输入：L = "4", R = "1000"。
输出：4。
答案2023-06-12：
该算法的基本思路是从较小的回文数开始，一步步扩大得到超级回文数，检查是否在规定区间内，直到扩大的回文数超过给定区间右端点或者已经统计到所有的超级回文数。
大体步骤如下：
1.定义函数 superpalindromesInRange，输入两个正整数的字符串表示 left 和 right，返回包含在范围 [L, R] 中的超级回文数的数目。此函数的返回值为整数类型 int。
2.将输入的字符串形式的正整数 left 和 right 分别转换成整数类型的变量 l 和 r。
3.将变量 r 开根号并取整，得到变量 limit。用变量 cnt 记录超级回文数的个数，初值为0。
4.变量 seed 初值为1，用于产生超级回文数。若当前 seed 对应的超级回文数已大于 r 的平方根，则跳出循环；否则进行下一步。
5.将变量 seed 进行第一次扩大，即将 seed 转化为一个更大的回文数，保存在变量 enlarge 中。
6.如果 enlarge 的平方数是超级回文数，则将 cnt 加一。
7.将变量 seed 进行第二次扩大，即将 seed 转化为一个更大的回文数，保存在变量 enlarge 中。
8.如果 enlarge 的平方数是超级回文数，则将 cnt 加一。
9.将 seed 加1。
10.回到步骤4，循环直到 seed 对应的扩大回文数大于 r 的平方根。
11.返回 cnt 作为函数的结果。
时间复杂度为 $O(\sqrt R\log R\log\log R)$，其中 $R$ 表示 right 的值，因为超级回文数的范围不超过 $\sqrt R$，而对于每一个超级回文数，需要判断其是否在 [L, R] 范围内，这个判断需要 $O(\log R)$ 的时间；同时，为了判断一个数是否是回文数，需要将其最高位和最低位一一比较，即需要 $O(\log n)$ 的时间，最多需要比较 $O(\log n)$ 次，因此判断回文数的时间复杂度为 $O(\log^2n)$。因此，总时间复杂度为 $O(\sqrt R\log R\log^2 R)$。
空间复杂度为 $O(1)$，因为程序只使用了常数个变量。
go语言完整代码如下：
package main
import (
"fmt"
"math"
"strconv"
)
func superpalindromesInRange(left string, right string) int {
l, _ := strconv.ParseInt(left, 10, 64)
r, _ := strconv.ParseInt(right, 10, 64)
limit := int64(math.Sqrt(float64(r)))
cnt := 0
seed := int64(1)
enlarge := int64(0)
for {
enlarge = enlarge2(seed)
if isValid(enlarge*enlarge, l, r) {
cnt++
}
enlarge = enlarge1(seed)
if isValid(enlarge*enlarge, l, r) {
cnt++
}
seed++
if enlarge >= limit {
break
}
}
return cnt
}
func enlarge1(seed int64) int64 {
var ans int64 = seed
seed /= 10
for seed != 0 {
ans = ans*10 + seed%10
seed /= 10
}
return ans
}
func enlarge2(seed int64) int64 {
var ans int64 = seed
for seed != 0 {
ans = ans*10 + seed%10
seed /= 10
}
return ans
}
func isValid(ans int64, l int64, r int64) bool {
return isPalindrome(ans) && ans >= l && ans <= r
}
func isPalindrome(n int64) bool {
var help int64 = 1
for n/help >= 10 {
help *= 10
}
for n != 0 {
if n/help != n%10 {
return false
}
n = (n % help) / 10
help /= 100
}
return true
}
func main() {
result := superpalindromesInRange("4", "1000")
fmt.Println(result)
}
rust完整代码如下：
fn superpalindromes_in_range(left: String, right: String) -> i32 {
let l: u64 = left.parse().unwrap();
let r: u64 = right.parse().unwrap();
let limit = (r as f64).sqrt() as u64;
let mut cnt = 0;
let mut seed = 1;
let mut enlarge = 0;
loop {
enlarge = enlarge2(seed);
if is_valid(enlarge * enlarge, l, r) {
cnt += 1;
}
enlarge = enlarge1(seed);
if is_valid(enlarge * enlarge, l, r) {
cnt += 1;
}
seed += 1;
if enlarge >= limit {
break;
}
}
cnt
}
fn enlarge1(seed: u64) -> u64 {
let mut ans = seed;
let mut tmp = seed / 10;
while tmp != 0 {
ans = ans * 10 + tmp % 10;
tmp /= 10;
}
ans
}
fn enlarge2(seed: u64) -> u64 {
let mut ans = seed;
let mut tmp = seed;
while tmp != 0 {
ans = ans * 10 + tmp % 10;
tmp /= 10;
}
ans
}
fn is_palindrome(n: u64) -> bool {
let mut help: u64 = 1;
let mut tmp = n;
while tmp / help >= 10 {
help *= 10;
}
while tmp != 0 {
if tmp / help != tmp % 10 {
return false;
}
tmp = (tmp % help) / 10;
help /= 100;
}
true
}
fn is_valid(ans: u64, l: u64, r: u64) -> bool {
is_palindrome(ans) && ans >= l && ans <= r
}
fn main() {
let result = superpalindromes_in_range(String::from("4"), String::from("1000"));
println!("{}", result);
}
c++完整代码如下：
#include
#include
#include
using namespace std;
long long enlarge1(long long seed);
long long enlarge2(long long seed);
bool isPalindrome(long long n);
bool isValid(long long ans, long long l, long long r);
int superpalindromesInRange(string left, string right);
int main() {
int result = superpalindromesInRange("4", "1000");
cout << result << endl;
return 0;
}
long long enlarge1(long long seed) {
long long ans = seed;
seed /= 10;
while (seed != 0) {
ans = ans * 10 + seed % 10;
seed /= 10;
}
return ans;
}
long long enlarge2(long long seed) {
long long ans = seed;
while (seed != 0) {
ans = ans * 10 + seed % 10;
seed /= 10;
}
return ans;
}
bool isPalindrome(long long n) {
long long help = 1;
while (n / help >= 10) {
help *= 10;
}
while (n != 0) {
if (n / help != n % 10) {
return false;
}
n = (n % help) / 10;
help /= 100;
}
return true;
}
bool isValid(long long ans, long long l, long long r) {
return isPalindrome(ans) && ans >= l && ans <= r;
}
int superpalindromesInRange(string left, string right) {
long long l = stoll(left);
long long r = stoll(right);
long long limit = sqrt(r);
int cnt = 0;
long long seed = 1;
long long enlarge = 0;
do {
enlarge = enlarge2(seed);
if (isValid(enlarge * enlarge, l, r)) {
cnt++;
}
enlarge = enlarge1(seed);
if (isValid(enlarge * enlarge, l, r)) {
cnt++;
}
seed++;
} while (enlarge <= limit);
return cnt;
}
c语言完整代码如下：
#include
#include
#include
long long enlarge1(long long seed);
long long enlarge2(long long seed);
int isPalindrome(long long n);
int isValid(long long ans, long long l, long long r);
int superpalindromesInRange(char* left, char* right);
int main() {
int result = superpalindromesInRange("4", "1000");
printf("%d\n", result);
return 0;
}
long long enlarge1(long long seed) {
long long ans = seed;
seed /= 10;
while (seed != 0) {
ans = ans * 10 + seed % 10;
seed /= 10;
}
return ans;
}
long long enlarge2(long long seed) {
long long ans = seed;
while (seed != 0) {
ans = ans * 10 + seed % 10;
seed /= 10;
}
return ans;
}
int isPalindrome(long long n) {
long long help = 1;
while (n / help >= 10) {
help *= 10;
}
while (n != 0) {
if (n / help != n % 10) {
return 0;
}
n = (n % help) / 10;
help /= 100;
}
return 1;
}
int isValid(long long ans, long long l, long long r) {
return isPalindrome(ans) && ans >= l && ans <= r;
}
int superpalindromesInRange(char* left, char* right) {
long long l = atoll(left);
long long r = atoll(right);
long long limit = sqrt(r);
int cnt = 0;
long long seed = 1;
long long enlarge = 0;
do {
enlarge = enlarge2(seed);
if (isValid(enlarge * enlarge, l, r)) {
cnt++;
}
enlarge = enlarge1(seed);
if (isValid(enlarge * enlarge, l, r)) {
cnt++;
}
seed++;
} while (enlarge <= limit);
return cnt;
}
参考阅读
发表评论