564.寻找最近的回文数
564.寻找最近的回文数
题解
两个解法都差不多，第二种官方解法确实精简
特判
1. n<10, ans=n-1 2. n=10..0 ，ans=n-1，即9..9 3. n=10..1 ，ans=n-2，即9..9 4. n=9..9 ，ans=n+2 ，即10..01
普遍
长度为奇数，取一半多取1位，翻转时，少翻1位，以下3数找与原数最接近的
+0: 99321 取 993，翻转后 99，拼接为 99399 -1: 99321 取 993，-1得 992，翻转后 99，拼接为 99299 +1: 99321 取 993，+1得 994，翻转后 99，拼接为 99499
长度为偶数，取一半，翻转，以下3数找与原数最接近的
+0: 994321 取 994，翻转后 499，拼接为 994499 -1：994321 取 994，-1得 993，翻转后 399，拼接为 993399 +1：994321 取 994，+1得 995，翻转后 599，拼接为 995599
代码
package main import ( "math" "strconv" ) func nearestPalindromic1(n string) string { //特判 intN, _ := strconv.Atoi(n) if intN < 10 { //小于10的数字，就是自身减1 return strconv.Itoa(intN - 1) } if intN == int(math.Pow10(len(n)-1)) { //1000->999, 10->9 return strconv.Itoa(intN - 1) } if intN+1 == int(math.Pow10(len(n))) { //99->101, 999->1001 return strconv.Itoa(intN + 2) } if intN-1 == int(math.Pow10(len(n)-1)) { //11->9, 101->99 return strconv.Itoa(intN - 2) } //奇偶 odd := false if len(n)%2 != 0 { odd = true } ans, absCnt := 0, intN preN, _ := strconv.Atoi(n[:(len(n)+1)/2]) for i := preN - 1; i <= preN+1; i++ { var cntString []byte preString := strconv.Itoa(i) cntString = append(cntString, preString...) j := len(preString) - 1 if odd { j-- } for ; j >= 0; j-- { cntString = append(cntString, preString[j]) } finalN, _ := strconv.Atoi(string(cntString)) if absCnt > abs(finalN-intN) && finalN != intN { ans = finalN absCnt = abs(finalN - intN) } } return strconv.Itoa(ans) } func abs(x int) int { if x < 0 { return -x } return x } func nearestPalindromic2(n string) string { m := len(n) candidates := []int{int(math.Pow10(m-1)) - 1, int(math.Pow10(m)) + 1}//预存99...999和100...001 selfPrefix, _ := strconv.Atoi(n[:(m+1)/2])//取出前面一半 for _, x := range []int{selfPrefix - 1, selfPrefix, selfPrefix + 1} { y := x if m&1 == 1 { y /= 10 } for ; y > 0; y /= 10 { x = x*10 + y%10//翻转前面一半的数值并添加到后面 } candidates = append(candidates, x) } ans := -1 selfNumber, _ := strconv.Atoi(n) for _, candidate := range candidates { if candidate != selfNumber { if ans == -1 ||//第一次 abs(candidate-selfNumber) < abs(ans-selfNumber) ||//当前比现有的答案小 abs(candidate-selfNumber) == abs(ans-selfNumber) && candidate < ans {//当前和现有的一样大，但是当前是较小的那个 ans = candidate } } } return strconv.Itoa(ans) }
