【LeetCode】906、超等回文数

【LeetCode】906、超等回文数

  

一、通过数据量猜解法 罗列 数学 回文

1.1 通过数据量猜解法 罗列 数学 回文

减小数据规模: 先构成回文, 再平方, 再判断是否是范围内的回文数
缩小数据范围: 回文种子 => 回文数(即根号) => 数字(即根号的平方)

1. // go
2. func superpalindromesInRange(left string, right string) (ans int) {
3.     l, _ := strconv.Atoi(left)
4.     r, _ := strconv.Atoi(right) // 规模为10^18, 的数字
5.     limit := int(math.Sqrt(float64(r))) // 规模为10^9, 的数字的根号
6.     seed := 1 // 规模10^5, 的原初种子, 通过 回文 可构成 数字的根号
7.     num := 0
8.     for num <= limit {
9.         // 原初种子 组成 偶数回文串
10.         num = evenEnlarge(seed)
11.         if isPalidromInRange(num*num, l, r) {ans++}
13.         // 原初种子 组成 奇数回文串
14.         num = oddEnlarge(seed)
15.         if isPalidromInRange(num*num, l, r) {ans++}
17.         // 原初种子 变大 继续后续遍历
18.         seed++
19.     }
20.     return
21. }
23. // 是否是范围内的回文数
24. func isPalidromInRange(num, l, r int) bool {
25.     return num >= l && num <= r && isPalinrome(num)
26. }
28. // 把数字x变为偶数回文串, 如123变为123321
29. func evenEnlarge(x int) int {
30.     ans := x
31.     for x > 0 {
32.         ans = ans * 10 + x % 10
33.         x /= 10
34.     }
35.     return ans
36. }
39. // 把数字x变为奇数回文串, 如123变为12321
40. func oddEnlarge(x int) int {
41.     ans := x
42.     x /= 10 // x 先除以10, 如 123 变为 12
43.     for x > 0 {
44.         ans = ans * 10 + x % 10
45.         x /= 10
46.     }
47.     return ans
48. }
50. // 数字x是否为回文数
51. func isPalinrome(x int) bool {
52.     if x < 0 {return false}
53.     offset := 1
54.     for x / offset >= 10 {
55.         offset *= 10
56.     }
58.     for x != 0 {
59.         if x/offset != x%10 {return false}
60.         x = (x%offset)/10
61.         offset /= 100
62.     }
63.     return true
64. }

复制代码

参考左神 根据数据量猜解法
1.2 多语言解法

                                    C                         p                         p                         /                         G                         o                         /                         P                         y                         t                         h                         o                         n                         /                         R                         u                         s                         t                         /                         J                         s                         /                         T                         s                              Cpp/Go/Python/Rust/Js/Ts                  Cpp/Go/Python/Rust/Js/Ts

1. // cpp

复制代码

1. // go 同上

复制代码

1. # python

复制代码

1. // rust

复制代码

1. // js

复制代码

1. // ts

复制代码

二、打表法

先算出全部 0 到 10^18 范围内的 超等回文数, 因为总共只有84个数, 非常少, 以是可以提前存储好, 得到一个数组. PS: 此计算过程因为是单独准备的, 以是并不算在题目时间里
然后遍历每个提前存储好的数字, 判断是否 在 [l, r] 范围内即可

1. func superpalindromesInRange(left string, right string) (ans int) {
2.     // helper()
3.     arr := []int{121 ,
4.         1 ,
5.         484 ,
6.         4 ,
7.         9 ,
8.         1002001 ,
9.         10201 ,
10.         1234321 ,
11.         12321 ,
12.         14641 ,
13.         4008004 ,
14.         40804 ,
15.         44944 ,
16.         10000200001 ,
17.         100020001 ,
18.         10221412201 ,
19.         102030201 ,
20.         104060401 ,
21.         12102420121 ,
22.         121242121 ,
23.         12345654321 ,
24.         123454321 ,
25.         125686521 ,
26.         40000800004 ,
27.         400080004 ,
28.         404090404 ,
29.         100000020000001 ,
30.         1000002000001 ,
31.         100220141022001 ,
32.         1002003002001 ,
33.         1004006004001 ,
34.         102012040210201 ,
35.         1020304030201 ,
36.         102234363432201 ,
37.         1022325232201 ,
38.         1024348434201 ,
39.         121000242000121 ,
40.         1210024200121 ,
41.         121242363242121 ,
42.         1212225222121 ,
43.         1214428244121 ,
44.         123212464212321 ,
45.         1232346432321 ,
46.         123456787654321 ,
47.         1234567654321 ,
48.         400000080000004 ,
49.         4000008000004 ,
50.         4004009004004 ,
51.         1000000002000000001 ,
52.         10000000200000001 ,
53.         1000220014100220001 ,
54.         10002000300020001 ,
55.         10004000600040001 ,
56.         1002003004003002001 ,
57.         10020210401202001 ,
58.         1002223236323222001 ,
59.         10022212521222001 ,
60.         10024214841242001 ,
61.         1020100204020010201 ,
62.         10201020402010201 ,
63.         1020322416142230201 ,
64.         10203040504030201 ,
65.         10205060806050201 ,
66.         1022123226223212201 ,
67.         10221432623412201 ,
68.         1022345658565432201 ,
69.         10223454745432201 ,
70.         1210000024200000121 ,
71.         12100002420000121 ,
72.         1210242036302420121 ,
73.         12102202520220121 ,
74.         12104402820440121 ,
75.         1212203226223022121 ,
76.         12122232623222121 ,
77.         1212445458545442121 ,
78.         12124434743442121 ,
79.         1232100246420012321 ,
80.         12321024642012321 ,
81.         1232344458544432321 ,
82.         12323244744232321 ,
83.         1234323468643234321 ,
84.         12343456865434321 ,
85.         12345678987654321 ,
86.         4000000008000000004 ,
87.         40000000800000004 ,
88.         40004000900040004}
89.     l, _ := strconv.Atoi(left)
90.     r, _ := strconv.Atoi(right)
91.     for _, v := range arr {
92.         if v >= l && v <= r {ans++}
93.     }
94.     return
95. }
97. func helper() {
98.     limit := int(1e9)
99.     seed := 1 // 规模10^5, 的原初种子, 通过 回文 可构成 数字的根号
100.     num := 0
101.     for num <= limit {
102.         // 原初种子 组成 偶数回文串
103.         num = evenEnlarge(seed)
104.         if isPalidromInRange(num*num) {fmt.Println(num*num, ",")}
106.         // 原初种子 组成 奇数回文串
107.         num = oddEnlarge(seed)
108.         if isPalidromInRange(num*num) {fmt.Println(num*num, ",")}
110.         // 原初种子 变大 继续后续遍历
111.         seed++
112.     }
113. }
115. // 是否是范围内的回文数
116. func isPalidromInRange(num int) bool {
117.     return isPalinrome(num)
118. }
120. // 把数字x变为偶数回文串, 如123变为123321
121. func evenEnlarge(x int) int {
122.     ans := x
123.     for x > 0 {
124.         ans = ans * 10 + x % 10
125.         x /= 10
126.     }
127.     return ans
128. }
131. // 把数字x变为奇数回文串, 如123变为12321
132. func oddEnlarge(x int) int {
133.     ans := x
134.     x /= 10 // x 先除以10, 如 123 变为 12
135.     for x > 0 {
136.         ans = ans * 10 + x % 10
137.         x /= 10
138.     }
139.     return ans
140. }
142. // 数字x是否为回文数
143. func isPalinrome(x int) bool {
144.     if x < 0 {return false}
145.     offset := 1
146.     for x / offset >= 10 {
147.         offset *= 10
148.     }
150.     for x != 0 {
151.         if x/offset != x%10 {return false}
152.         x = (x%offset)/10
153.         offset /= 100
154.     }
155.     return true
156. }

复制代码

参考左神 根据数据量猜解法

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。