1. Toy模板网首页
  2. > Toy博客

2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中

9月前 作者：福大大架构师每日一题 分类：Toy博客 阅读(51) 违法举报

这篇具有很好参考价值的文章主要介绍了2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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)$，因为程序只使用了常数个变量。

2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中

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)
}

2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中

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);
}

2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中

c++完整代码如下：

#include <iostream>
#include <string>
#include <cmath>

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;
}

2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中

c语言完整代码如下：

#include <stdio.h>
#include <string.h>
#include <math.h>

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;
}

2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中文章来源地址https://www.toymoban.com/news/detail-480257.html

到了这里，关于2023-06-12：如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。 现在，给定两个正整数 L 和 R （以字符串形式表示）， 返回包含在范围 [L, R] 中的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包