时间复杂度为 O(RlogRloglogR),其中 R 表示 right 的值,因为超级回文数的范围不超过 R,而对于每一个超级回文数,需要判断其是否在 [L, R] 范围内,这个判断需要 O(logR) 的时间;同时,为了判断一个数是否是回文数,需要将其最高位和最低位一一比较,即需要 O(logn) 的时间,最多需要比较 O(logn) 次,因此判断回文数的时间复杂度为 O(log2n)。因此,总时间复杂度为 O(RlogRlog2R)。
空间复杂度为 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 <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;}
复制代码
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;}
评论