[leetcode564]寻找最近的回文数

发布于 2022-03-03  587 次阅读


https://leetcode-cn.com/problems/find-the-closest-palindrome/

hard题 有点难 自己想了半天没想明白 看y总的思路明白了这道题

属于脑筋急转弯类型的题

给定一个数 求最近的回文数 可大可小 绝对值最小 若有两个相同的 返回较小的那个

思路:根据一个数的前半段进行构造 直接构造回文数

给定 12345 构造成 12321 12421 12221

比如给的12345 最近的是12321 但是给定12399 最近的就是12421

但是如果给定19911 最近的反而是19891

所以说就是这三个数 但是不仅仅是这三个数字 还有两种特殊情况

比如9999 最接近的不是100001 这样会多一位 应该是10001

同理1001 最近的也不是99 而是999

所以一共是五个数 上面三个加上pow(10,n)+1pow(10,n-1)-1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class Solution
{
public:
  string nearestPalindromic(string n)
  {
    //寻找最近的数
    int len = n.size();
    set<ll> st;
    //如9999 最近的是10001
    st.insert((ll)pow(10, len) + 1);
    //如10000 最近的有10001和9999 但是要返回较小的
    st.insert((ll)pow(10, len - 1) - 1);
    //截取前一半 先不管是长度为奇数还是偶数
    ll m = stoll(n.substr(0, (len + 1) / 2));
    //将三个数加到set中
    for (ll i = m - 1; i <= m + 1; i++)
    {
      //构造回文数
      //区分一下偶数还是技术
      string a=to_string(i),b=a;
      reverse(b.begin(),b.end());
      if(len%2){
        st.insert(stoll(a+b.substr(i)));
      }else{
        st.insert(stoll(a+b));
      }
    }
    //由于set内部自动排序 所以两数绝对值之差相等时,会返回较小的
    ll k=stoll(n);
    //防止数字本身是回文数的情况
    st.erase(k);
    ll ans=LONG_LONG_MAX;
    for(ll i:st){
      if(abs(i-k)<abs(ans-k)){
        ans=i;
      }
    }
    return to_string(ans);
  }
};

愿风指引你的道路,愿你的刀刃永远锋利。