leetcode 564. 寻找最近的回文数(贪心+模拟)

题目描述:

给定一个表示整数的字符串 n ,返回与它最近的回文整数(不包括自身)。如果不止一个,返回较小的那个。

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

示例 1:

输入: n = "123"
输出: "121"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-closest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

最简单的一种构造方法,是用前面元素将后面回文对应的元素进行替换,比如 12345,可以用1替换5,2替换4,得到12321,但是还有一种情况,比如12399,我们采用上述方法替换为12321,但是实际上,12421更接近12399。因此,问题就可以确定在中间元素上

  • 中间元素保持不变;
  • 中间元素+1;
  • 中间元素-1;

因此,我们可以总结出以下的方案:

  • 用原数的前半部分替换后半部分得到的回文整数
  • 用原数的前半部分加一后的结果替换后半部分得到的回文整数
  • 用原数的前半部分减一后的结果替换后半部分得到的回文整数。
  • 还要特别注意两种特殊情况,假如 999的时候,增大中间部分会导致位数增加,得到1001,同样还有101的情况,减小中间部分会导致位数减少,得到99,因此为了防止位数变化导致构造的回文整数错误,因此我们直接构造999..999和100..001这两个备选的答案。

代码:

class Solution {
public:
    vector<long> getCandidates(string n){    //构造备选答案
        int len = n.size();
        vector<long> candidates = {  //避免漏掉两个极端情况
            (long) pow(10,len-1)-1,
            (long) pow(10,len)+1,
        };
        int half = (len+1)/2;
        long pre = stol(n.substr(0,half)); //中间的也取到
        vector<long> preSet={pre-1,pre,pre+1};
        for(auto&num:preSet){
            string p = to_string(num);
            string candidate = p + string(p.rbegin()+(len&1),p.rend()); //注意,这里学到新的一招,string(rbegin(),rend())即可获得逆序
            candidates.emplace_back(stol(candidate));
        }
        return candidates;
    }
    string nearestPalindromic(string n) {
        long cur = stol(n),ans = -1;
        vector<long> candidates = getCandidates(n);
        for(auto&candidate:candidates){  //遍历备选答案
            if(candidate!=cur){
                if(ans==-1||abs(candidate - cur)<abs(ans - cur)|| abs(candidate-cur) == abs(ans - cur)&&candidate<ans){
                    ans = candidate;
                }
            }
        }
        return to_string(ans);
    }
};

上一篇:Django框架(十三)——Auth模块


下一篇:CentOS 7报错:curl#60 - “Peer‘s Certificate has expired.“