• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

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

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

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

示例 1:

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

注意:

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

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 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap