WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Leetcode 564. 寻找最近的回文数
Leetcode 564. 寻找最近的回文数

564. 寻找最近的回文数

题意

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

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

示例 1:

输入: “123”
输出: “121”

注意:

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

思路

其实这道题目的思路很简单,假设当前数字的长度为N,值为P,那么我们可以枚举最终答案的长度为N-1、N、N+1。

  1. 假设答案长度为N-1,那么一定是长度为N-1的99…9字符串。
  2. 假设答案长度为N+1,那么一定是一个首位和末尾为1、其他为位置为0、长为N+1的字符串。
  3. 假设答案的长度为N,那么还分两种情况:答案比原数字大、答案比原数字小。
    • 答案比原数字大,我们先构造一个长度为N的99…9字符串T,然后(保证回文的情况下,即同时修改某位和它的回文对应位)从高位往低位开始枚举,在T比P大的情况下依次从高到低让每一位尽可能的小。比如对于第i位,我们把第i位和它回文的第(N+1-i)位,同时减小,直到再减小T的数字就比P小了,然后如此在进行下一位,直到枚举位与他的回文位相遇。
      举一个例子:如果原来的数字是12413,我们先构造99999,然后尝试修改第1、5位得到19991,再尝试修改第2、4位得到12921,最后尝试修改第3位得到12421,就是答案了。
    • 答案比原数字小的情况,我们构造长度为N的00…0字符串T,然后(保证回文的情况下)从高位往地位让每一位尽可能的大。

那么最终的答案就是1、2、3.(a)、3.(b)这四种情况取一个最优情况。

class Solution {
public:
    long long pow10[20];

    long long str2long(string n){
        long long ret=0; int l=n.length();
        for (int i=0; i<l; i++) ret=ret*10+n[i]-'0';
        return ret;
    }

    string long2str(long long v){
        if (v==0) return "0";
        string ret="";
        while(v) ret=((char)(v%10+'0'))+ret, v/=10;
        return ret;
    }

    long long changeBit(long long v, int bit, int dig){
        long long d=v%pow10[bit+1]/pow10[bit];
        return v-d*pow10[bit]+dig*pow10[bit];
    }

    long long Abs(long long x){
        if (x<0) return -x;
        return x;
    }

    void update(long long cmp, long long val, long long &ans){
        if (Abs(cmp-val)<Abs(ans-val) || (Abs(cmp-val)==Abs(ans-val) && cmp<ans)) ans=cmp;
    }

    long long solve(long long val, long long flag){
        int l=0; long long rate=val; while(rate) ++l, rate/=10;

        rate=0; for (int i=0; i<l; i++) rate=changeBit(rate, i, (flag==1?0:9));

        for (int i=0; i<=(l-i-1); i++){
            long long delta=Abs(rate-val);
            int digit=(flag==1?0:9);
            for (int d=(i==0?1:0); d<=9; d++){
                long long now=changeBit(changeBit(rate, i, d), l-i-1, d);
                if ((flag==1 && now<=val) || (flag==-1 && now>=val)){
                    if (delta>Abs(now-val)) digit=d, delta=Abs(now-val);
                }
            }
            rate=changeBit(changeBit(rate, i, digit), l-i-1, digit);
        }

        //printf("%lld\n", rate);
        return rate;
    }

    string nearestPalindromic(string n) {
        pow10[0]=1; for (int i=1; i<20; i++) pow10[i]=pow10[i-1]*10;

        long long val=str2long(n);
        int len=n.length();
        long long ans=0, cmp;

        // 9..9
        cmp=0; for (int i=0; i<len-1; i++) cmp=changeBit(cmp, i, 9);
        update(cmp, val, ans);

        // 10001
        cmp=0; changeBit(cmp, 0, 1); changeBit(cmp, len, 1);
        update(cmp, val, ans);

        // Bigger
        update(solve(val-1, 1), val, ans);

        // Smaller
        update(solve(val+1, -1), val, ans);

        return long2str(ans);

    }
};
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Leetcode 564. 寻找最近的回文数
564. 寻找最近的回文数 题意 给定一个整数 n ,你需要找到与它最近的回文数(不包括自身)。 “最近的”定义为两个整数差的绝对值最小。 示例 1: 输入: "123" 输出: "121" 注意…
扫描二维码继续阅读
2019-01-04
<--! http2https -->