最近回文数

Posted by Jason on Monday, February 17, 2020

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)
}

「真诚赞赏,手留余香」

Jason Blog

真诚赞赏,手留余香

使用微信扫描二维码完成支付


comments powered by Disqus