【数学】【思维】数学+模拟+贪心——leetcode 寻找最近的回文数

这题要真推算起来还是比较复杂的，但是可以先猜个结论：

　　首先肯定是前面一半复制到后面一半：这是很显然的，所以答案字符串由前面一半所控制

　　我们把前面一半+1，前面一半-1都考虑进去，如果没有进位退位（即字符串长度保持不变的情况下），那么这三个字符串足以覆盖答案出现的范围

　　下面再考虑进位和退位，显然进位的情况必定是100...001，退位的情况必定是999....999

最后把这五个数按和原来的数绝对值差排个序，差最小的就是答案

class Solution {
public:
    #define ll long long
    #define pb push_back
    int len;
    ll ori;
    ll toLL(string n){
        ll res=0;
        for(int i=0;i<n.size();i++)
            if(n[i]<='9' && n[i]>='0')res=res*10,res=res+n[i]-'0';
        return res;
    }
    string toStr(ll x){
        string res="";
        if(x==0)res="0";
        int pos=0;
        while(x){
            pos++;
            res+=x%10+'0';
            x/=10;
        }
        int i=0,j=pos-1;
        while(i<j)swap(res[i],res[j]),++i,--j;
        return res;
    }

    string nearestPalindromic(string n) {
        len=n.size();
        string half,nxt,pre;

        ori=toLL(n);//原式值

        ll halfLL,nxtLL,preLL;

        if(len%2==0){
            for(int i=0;i<len/2;i++)half+=n[i];//截取前半部分
            halfLL=toLL(half);
            nxtLL=halfLL+1;
            preLL=halfLL-1;

            nxt=toStr(nxtLL);
            pre=toStr(preLL);
            //给字符串翻倍
            int t=half.size();
            for(int i=t-1;i>=0;i--)half+=half[i];
            t=nxt.size();
            for(int i=t-1;i>=0;i--)nxt+=nxt[i];
            t=pre.size();
            for(int i=t-1;i>=0;i--)pre+=pre[i];
            halfLL=toLL(half);
            nxtLL=toLL(nxt);
            preLL=toLL(pre);

        }else {
            for(int i=0;i<len/2+1;i++)half+=n[i];//截取前半部分
            halfLL=toLL(half);
            nxtLL=halfLL+1;
            preLL=halfLL-1;

            nxt=toStr(nxtLL);
            pre=toStr(preLL);

            int t=half.size()-1;
            for(int i=t-1;i>=0;i--)half+=half[i];
            t=nxt.size()-1;
            for(int i=t-1;i>=0;i--)nxt+=nxt[i];
            t=pre.size()-1;
            for(int i=t-1;i>=0;i--)pre+=pre[i];
            halfLL=toLL(half);
            nxtLL=toLL(nxt);
            preLL=toLL(pre);
        }

        string x(len-1,'9');
        string y(len+1,'0');
        y[0]=y[len]='1';

        vector<string>v;
        if(x.size())v.pb(x);v.pb(y);
        if(half.compare(n))v.pb(half);
        v.pb(nxt);v.pb(pre);
           sort(v.begin(),v.end(),[&](string &a,string &b){
            ll aa=toLL(a),bb=toLL(b);
            if(abs(aa-ori)==abs(bb-ori))return aa<bb;
            return abs(aa-ori)<abs(bb-ori);
        });

        return v[0];
    }
};