Leetcode 564. 寻找最近的回文数

题目

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

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

示例:

输入: "123"
输出: "121"

注意:

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

题解

如果n是小于11的数，则直接返回n-1。 我们先以n的高位为基础构造回文串reverseCur。 我们再获取n的高位，也就是高n.length()/2+n.length()%2位，记为now。如果本身是10的倍数或者为“1”，我们则对其*10后再-1后构造回文串pre；否则，则对其-1后构造回文串pre 我们再以now+1为基础构造回文串next。 离n最近的回文串就可能为reverseCur或pre或next，通过比较距离进行确定。 详细过程见代码

代码

long getMidReverse(string n){
          
   
        //cout<<n<<endl;
        string ans = n;
        int i=0,j=ans.length()-1;
        while(i < j){
          
   
            ans[j] = ans[i];
            i++;
            j--;
        }
        return stol(ans);
    }
    string nearestPalindromic(string n) {
          
   
        long cur = stol(n);
        if(cur<=10) return to_string(cur-1);  
        long reverseCur = getMidReverse(n);			//以本身的高半位为基础构造回文串
        //cout<<reverseCur<<endl;
        int mid = n.length()/2;
        string now = n.substr(0,mid + n.length()%2);
        long pre;		//高半位-1后构造回文串，但对于本身为10的倍数或为1，我们需要*10后再-1
        if(stol(now)%10 == 0 || now=="1")  pre = getMidReverse(to_string(stol(now)*10-1)+string(mid-1,0));		
        else pre = getMidReverse(to_string(stol(now)-1)+string(mid,0));
        long next = getMidReverse(to_string(stol(now)+1)+string(mid,0));
        long ans = pre;
        //cout<<next;
        if(abs(reverseCur-cur)<abs(ans-cur) && reverseCur!=cur) ans = reverseCur;
        if(abs(next-cur)<abs(ans-cur))   ans = next;
        return to_string(ans);
    }