[Swift]LeetCode564.寻找最近的回文数|FindtheClosestPalindrome

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

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

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

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

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

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

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The 'closest' is defined as absolute difference minimized between two integers.

Example 1:

Input: "123"
Output: "121"

Note:

The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.

给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。

“最近的”定义为两个整数差的绝对值最小。

示例 1:

输入: "123"
输出: "121"

注意:

n 是由字符串表示的正整数，其长度不超过18。
如果有多个结果，返回最小的那个。

Runtime: 16 ms

Memory Usage: 20.3 MB

 1 class Solution {
 2     func nearestPalindromic(_ n: String) -> String {
 3         var arr:[Character] = Array(n) 
 4         var i:Int = 0
 5         var j:Int = arr.count - 1
 6         while(i < j)
 7         {
 8             arr[j] = arr[i]
 9             i += 1
10             j -= 1
11         }
12         var curP:String = String(arr)
13         var preP:String = nearestPalindrom(curP, false)
14         var nextP:String = nearestPalindrom(curP, true)
15         
16         var num:Int = Int(n)!
17         var cur:Int = Int(curP)!
18         var pre:Int = Int(preP)!
19         var next:Int = Int(nextP)!    
20         
21         var d1:Int = abs(num - pre)
22         var d2:Int = abs(num - cur)
23         var d3:Int = abs(num - next)
24         
25         if num == cur
26         {
27             return d1 <= d3 ? preP : nextP
28         }
29         else if num > cur
30         {
31             return d2 <= d3 ? curP : nextP
32         }
33         else
34         {
35             return d1 <= d2 ? preP : curP
36         }
37     }
38     
39     func nearestPalindrom(_ curP:String,_ dir:Bool) -> String
40     {
41         var k:Int = curP.count >> 1
42         var p:Int = curP.count - k
43         var l:Int = Int(curP.subString(0, p))!
44         l += (dir ? 1 : -1)
45         
46         if l == 0 
47         {
48             return k == 0 ? "0" : "9"
49         }
50         var left:String = String(l)
51         var right:String = String(left.reversed())
52         if k > left.count
53         {
54             right.append("9")
55         }
56         return left + right.subString(right.count - k)      
57     }
58 }
59 
60 extension String 
61 {
62     // 截取字符串：指定索引和字符数
63     // - begin: 开始截取处索引
64     // - count: 截取的字符数量
65     func subString(_ begin:Int,_ count:Int) -> String {
66         let start = self.index(self.startIndex, offsetBy: max(0, begin))
67         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
68         return String(self[start..<end]) 
69     }
70     
71     // 截取字符串：从index到结束处
72     // - Parameter index: 开始索引
73     // - Returns: 子字符串
74     func subString(_ index: Int) -> String {
75         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
76         return String(self[theIndex..<endIndex])
77     }
78 }

24ms

  1 class Solution {
  2     func nearestPalindromic(_ n: String) -> String {
  3         let smallArr = ["1":"0","2":"1","3":"2","4":"3","5":"4","6":"5","7":"6","8":"7","9":"8","10":"9","11":"9",]
  4         if let s = smallArr[n]{
  5             return s
  6         }
  7         var half = n.count/2
  8         var mid = 0
  9         if n.count % 2 == 1{
 10             half += 1
 11             mid = 1
 12         }
 13         let backHalf = n.count - half
 14         let a = Int(n.prefix(half)) ?? 1
 15         let b = Int(n.suffix(backHalf)) ?? 0
 16         var r1:Int = Int.max
 17         var r2:Int = Int.max
 18         var r3:Int = Int.max
 19 
 20         //退位的问题  遇到  10..0 || 10..1
 21         if a%10 == 0 && b <= 1{
 22             var res = ""
 23             for _ in 1..<n.count{
 24                 res.append("9")
 25             }
 26             return res
 27         }
 28 
 29         //前位数-1
 30         if a % 10 != 0{
 31             if mid == 1{
 32                 r1 = b + complement(reversed((a - 1) / 10),backHalf)
 33             }else{
 34                 r1 = b + complement(reversed((a - 1)),backHalf)
 35             }
 36         }
 37         //不变
 38         if mid == 1{
 39             r2 = b - reversed(a/10)
 40         }else{
 41             r2 = b - reversed(a)
 42         }
 43         r2 = (r2 > 0) ? r2 : -r2
 44 
 45         var jinwei = false
 46         //前位数+1
 47         if !isTensTimes(a+1){//判断是否会进位
 48             if mid == 1{
 49                 r3 = complement(b,backHalf) + reversed((a + 1)/10)
 50             }else{
 51                 r3 = complement(b,backHalf) + reversed((a + 1))
 52             }
 53         }else{
 54             r3 = complement(b,backHalf) + 1
 55             jinwei = true
 56         }
 57 
 58         if r2 == 0{
 59             r2 = r2 == 0 ? Int.max : r2
 60         }
 61 
 62         var re = 1
 63         if r1 <= r2 && r1 <= r3{
 64             re = -1
 65         }else if r2 <= r3 && r2 <= r1{
 66             re = 0
 67         }
 68 
 69         //拿进位的结果
 70         if re == 1 && jinwei == true{
 71             var res = "1"
 72             for _ in 1..<n.count{
 73                 res.append("0")
 74             }
 75             res.append("1")
 76             return res
 77         }
 78 
 79 
 80         let resultHead = a + re
 81 
 82         var resultBack = String(resultHead)
 83         if n.count % 2 == 1{
 84             resultBack = String(resultBack.prefix(resultBack.count-1))
 85         }
 86         resultBack = String(resultBack.reversed())
 87         return String(resultHead)+resultBack
 88     }
 89 
 90     func complement(_ num:Int,_ length:Int) -> Int {
 91         var big = 1
 92         for _ in 0..<length{
 93             big *= 10
 94         }
 95         return big - num
 96     }
 97 
 98     func reversed(_ num:Int) -> Int{
 99         var s = String(num)
100         s = String(s.reversed())
101         return Int(s)!
102     }
103 
104     //是否是10的倍数
105     func isTensTimes(_ num:Int) -> Bool{
106         let s = String(num)
107         let back = String(s.suffix(s.count-1))
108         let newNum = Int(back)
109         if newNum == 0{
110             return true
111         }
112         return false
113     }
114 }