[Swift]LeetCode906.超级回文数|SuperPalindromes

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10609103.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].

Example 1:

Input: L =

Note:

1 <= len(L) <= 18
1 <= len(R) <= 18
L and R are strings representing integers in the range [1, 10^18).
int(L) <= int(R)

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

示例：

输入：L = "4", R = "1000"
输出：4
解释：
4，9，121，以及 484 是超级回文数。
注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。

提示：

1 <= len(L) <= 18
1 <= len(R) <= 18
L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
int(L) <= int(R)

Runtime: 8 ms

Memory Usage: 19.9 MB

 1 class Solution {
 2     let value:[Int] = [0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, 69696, 94249, 698896, 1002001, 1234321, 
 3     4008004, 5221225, 6948496, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 
 4     404090404, 522808225, 617323716, 942060249, 10000200001, 10221412201, 12102420121, 12345654321, 
 5     40000800004, 637832238736, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 
 6     1024348434201, 1086078706801, 1210024200121, 1212225222121, 1214428244121, 1230127210321, 1232346432321, 
 7     1234567654321, 1615108015161, 4000008000004, 4004009004004, 4051154511504, 5265533355625, 9420645460249, 
 8     100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121, 121242363242121, 
 9     123212464212321, 123456787654321, 123862676268321, 144678292876441, 165551171155561, 400000080000004, 
10     900075181570009, 4099923883299904, 10000000200000001, 10002000300020001, 10004000600040001, 10020210401202001, 
11     10022212521222001, 10024214841242001, 10201020402010201, 10203040504030201, 10205060806050201, 
12     10221432623412201, 10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121, 
13     12120030703002121, 12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321, 
14     12341234943214321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004, 94206450305460249]
15     func superpalindromesInRange(_ L: String, _ R: String) -> Int {
16         var l:Int = bound(Int(L) ?? 0)
17         var r:Int = bound(Int(R) ?? 0)
18         var res:Int = 0
19         while(l != r)
20         {
21             var v:Int = value[l]
22             var root:Int = Int(sqrt(Double(v)))
23             var s1:String = String(root)
24             var s2:String = String(s1.reversed())
25             if s2 == s1
26             {
27                 res += 1
28             }
29             l += 1
30         }
31         return res        
32     }
33 
34     func bound(_ target:Int) -> Int
35     {
36         var low = 0
37         var high = value.count - 1
38         var mid = (low + high) >> 1
39         
40         while low <= high {
41             let val = value[mid]
42             if target == val {
43                 return mid
44             } else if target < val {
45                 high = mid - 1
46             } else {
47                 low = mid + 1 
48             }
49             mid = (low + high) >> 1
50         }
51         return low
52     }
53 }

Time Limit Exceeded

 1 class Solution {
 2     func superpalindromesInRange(_ L: String, _ R: String) -> Int {
 3         var l:Int = Int(L) ?? 0
 4         var r:Int = Int(R) ?? 0
 5         var result:Int = 0
 6         var i:Int = Int(sqrt(Double(l)))
 7         while(i * i <= r)
 8         {
 9             var p:Int = nextP(i)
10             if p * p <= r && isP(p * p)
11             {
12                 result += 1
13             }
14             i = p + 1
15         }
16         return result
17     }
18 
19     func nextP(_ l:Int) -> Int
20     {
21         var s:String = String(l)
22         var len:Int = s.count
23         var cands:[Int] = [Int]()
24         let num:Int = Int(pow(10, Double(len))) - 1
25         cands.append(num)
26         var half:String = s.subString(0, (len + 1) / 2)
27         let num0:Int? = Int(half)
28         var nextHalf:String = String(1)
29         if num0 != nil
30         {
31             nextHalf = String(num0! + 1)
32         }
33         var reverse:String = String(half.subString(0, len / 2).reversed())
34         var nextReverse:String = String(nextHalf.subString(0, len / 2).reversed())
35         let num1:Int? = Int(half + reverse)
36         if num1 !=  nil
37         {
38             cands.append(num1!)
39         }
40         let num2:Int? = Int(nextHalf + nextReverse)
41         if num2 !=  nil
42         {
43             cands.append(num2!)
44         }
45         var result:Int = Int.max
46         for i in cands
47         {
48             if i >= l
49             {
50                 result = min(result, i)
51             }
52         }
53         return result
54     }
55 
56     func isP(_ l:Int) -> Bool
57     {
58         var arrS:[Character] = Array(String(l))
59         var i:Int = 0
60         var j:Int = arrS.count - 1
61         while (i < j)
62         {
63             if arrS[i] != arrS[j]
64             {
65                 return false
66             }       
67             i += 1
68             j -= 1     
69         }
70         return true
71     }
72 }
73 
74 extension String {
75     // 截取字符串：指定索引和字符数
76     // - begin: 开始截取处索引
77     // - count: 截取的字符数量
78     func subString(_ begin:Int,_ count:Int) -> String {
79         let start = self.index(self.startIndex, offsetBy: max(0, begin))
80         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
81         return String(self[start..<end]) 
82     }
83 }