2023-06-12：如果一個(gè)正整數(shù)自身是回文數(shù)，而且它也是一個(gè)回文數(shù)的平方，那么我們稱這
2023-06-12：如果一個(gè)正整數(shù)自身是回文數(shù)，而且它也是一個(gè)回文數(shù)的平方，那么我們稱這個(gè)數(shù)為超級(jí)回文數(shù)。
現(xiàn)在，給定兩個(gè)正整數(shù) L 和 R （以字符串形式表示），
返回包含在范圍 [L, R] 中的超級(jí)回文數(shù)的數(shù)目。
輸入：L = "4", R = "1000"。
輸出：4。
答案2023-06-12：
該算法的基本思路是從較小的回文數(shù)開始，一步步擴(kuò)大得到超級(jí)回文數(shù)，檢查是否在規(guī)定區(qū)間內(nèi)，直到擴(kuò)大的回文數(shù)超過給定區(qū)間右端點(diǎn)或者已經(jīng)統(tǒng)計(jì)到所有的超級(jí)回文數(shù)。
大體步驟如下：
1.定義函數(shù)?superpalindromesInRange，輸入兩個(gè)正整數(shù)的字符串表示?left?和?right，返回包含在范圍?[L, R]?中的超級(jí)回文數(shù)的數(shù)目。此函數(shù)的返回值為整數(shù)類型?int。
2.將輸入的字符串形式的正整數(shù)?left?和?right?分別轉(zhuǎn)換成整數(shù)類型的變量?l?和?r。
3.將變量?r?開根號(hào)并取整，得到變量?limit。用變量?cnt?記錄超級(jí)回文數(shù)的個(gè)數(shù)，初值為0。
4.變量?seed?初值為1，用于產(chǎn)生超級(jí)回文數(shù)。若當(dāng)前?seed?對(duì)應(yīng)的超級(jí)回文數(shù)已大于?r?的平方根，則跳出循環(huán)；否則進(jìn)行下一步。
5.將變量?seed?進(jìn)行第一次擴(kuò)大，即將?seed?轉(zhuǎn)化為一個(gè)更大的回文數(shù)，保存在變量?enlarge?中。
6.如果?enlarge?的平方數(shù)是超級(jí)回文數(shù)，則將?cnt?加一。
7.將變量?seed?進(jìn)行第二次擴(kuò)大，即將?seed?轉(zhuǎn)化為一個(gè)更大的回文數(shù)，保存在變量?enlarge?中。
8.如果?enlarge?的平方數(shù)是超級(jí)回文數(shù)，則將?cnt?加一。
9.將?seed?加1。
10.回到步驟4，循環(huán)直到?seed?對(duì)應(yīng)的擴(kuò)大回文數(shù)大于?r?的平方根。
11.返回?cnt?作為函數(shù)的結(jié)果。
時(shí)間復(fù)雜度為 $O(\sqrt R\log R\log\log R)$，其中 $R$ 表示?right?的值，因?yàn)槌?jí)回文數(shù)的范圍不超過 $\sqrt R$，而對(duì)于每一個(gè)超級(jí)回文數(shù)，需要判斷其是否在?[L, R]?范圍內(nèi)，這個(gè)判斷需要 $O(\log R)$ 的時(shí)間；同時(shí)，為了判斷一個(gè)數(shù)是否是回文數(shù)，需要將其最高位和最低位一一比較，即需要 $O(\log n)$ 的時(shí)間，最多需要比較 $O(\log n)$ 次，因此判斷回文數(shù)的時(shí)間復(fù)雜度為 $O(\log^2n)$。因此，總時(shí)間復(fù)雜度為 $O(\sqrt R\log R\log^2 R)$。
空間復(fù)雜度為 $O(1)$，因?yàn)槌绦蛑皇褂昧顺?shù)個(gè)變量。
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++完整代碼如下：
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語言完整代碼如下：
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;
}
