TOC
题目：
给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: "123"
输出: "121"
注意:
n 是由字符串表示的正整数，其长度不超过18。
如果有多个结果，返回最小的那个。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-closest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
我们先看一下回文数字的定义：
- 回文数字
abcdcba，数字长度位n，特点:{i>=j | number[i]==number[j]}。
针对这个特点，其实对于对给定的任意数字，只需要对前半部分做加减或不变，然后高位复制到低位，再做 diff 比较， diff 最小的即满足题目所求 最近回文数。
例如 10981 :
- 第一步，前半部分 109 :
- 保持前半部分不变，然后复制高位，所得回文数为 10901；
- 前半部加一，所得回文数为：11011；
- 前半部减一，所得回文数为：10801；
diff 比较:
- |10981-10901| = 80
- |10981-11011| = 30
- |10981-10801| = 180
最后，得到最接近的回文数为11011
代码实现
func nearestPalindromic(n string) string {
num, _ := strconv.ParseInt(n, 10, 64)
// lower
low := nearest(n, true)
lowN, _ := strconv.ParseInt(low, 10, 64)
// higer
high := nearest(n, false)
highN, _ := strconv.ParseInt(high, 10, 64)
if highN-num >= num-lowN {
return low
}
return high
}
func nearest(n string, low bool) string {
count := len(n)
b := []byte(n)
if len(n) == 0 {
return ""
} else if len(n) == 1 {
b[0] = b[0] - 1
return string(b)
}
realnum, _ := strconv.ParseInt(n, 10, 64)
for count > 0 {
for start := 0; start < count/2; start++ {
b[count-start-1] = b[start]
}
num1, _ := strconv.ParseInt(string(b), 10, 64)
// first lower palindromic number or first higer palindromic number
if (low && num1 < realnum) || (!low && num1 > realnum) {
return string(b)
}
left := count / 2
if count%2 == 1 {
left = count/2 + 1
}
num, _ := strconv.ParseInt(string(b[:left]), 10, 64)
// if lower sub, otherwise add
if low {
num -= 1
} else {
num += 1
}
if num == 0 {
return "9"
}
numStr := strconv.Itoa(int(num))
if len(numStr) != left {
// lower sink, or higer expand
if low {
for i := left; i < count; i++ {
b[i] = '9'
}
b = b[1:]
} else {
b = append([]byte(numStr), string(b[left:])...)
}
}
copy(b, []byte(numStr))
count = len(b)
}
return string(b)
}
「真诚赞赏，手留余香」
真诚赞赏，手留余香
使用微信扫描二维码完成支付
comments powered by Disqus