C++で最も近い回文を見つける

数nがあるとすると、回文である最も近い数を取得する必要があります。したがって、回文は、絶対差が小さい数よりも少ないか、多い可能性があります。したがって、数値が145のような場合、結果は141になります。

これを解決するには、次の手順に従います-

• sn：=nのサイズ
• snが1と同じ場合、-
  • n [0]を1減らし、サイズn[0]の1の文字列を返します
• half_sn：=（sn + 1）/ 2
• half_val：=stol（インデックス0からhalf_snまでのnの部分文字列
• 配列候補を定義する={10^（sn）– 1、10 ^（sn-1）-1、10 ^（sn-1）+ 1、10 ^（sn）+1
• 配列を定義するfmdc={half_val、half_val-1、half_val + 1}
• fmdsの値cごとに
  • rev：=cを文字列に変換
  • sn mod 2がゼロ以外の場合、-
    • revから最後の要素を削除
  • アレイのリビジョンを逆にする
  • 候補の最後にcを挿入
• アレイ候補を並べ替える
• val：=n as integer
• 候補者の候補者ごとに-
  • 候補がvalと同じ場合、-
    • 次の部分を無視し、次の反復にスキップします
  • diff：=abs | candidate – val |
  • diff
  • min_diff：=diff
  • ans：=候補を文字列に変換

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string nearestPalindromic(string n) {
      int sn = n.size();
      if(sn == 1){
      return string(1, --n[0]);
   }
   int half_sn = (sn+1)/2;
   long half_val = stol(n.substr(0, half_sn));
   vector<long> candidates = {pow(10, sn)-1, pow(10, sn-1)-1, pow(10, sn-1)+1, pow(10, sn)+1};
   vector <long> fmdc = {half_val, half_val-1,half_val+1};
   for(long c:fmdc){
      string rev = to_string(c);
      if(sn%2)rev.pop_back();
      reverse(rev.begin(),rev.end());
      candidates.push_back(stol(to_string(c) + rev));
   }
   sort(candidates.begin(), candidates.end());
   string ans;
   long val = stol(n), min_diff = INT_MAX;
   for(long candidate : candidates){
      if(candidate == val)continue;
      long diff = labs(candidate - val);
      if(diff < min_diff){
         min_diff = diff;
         ans = to_string(candidate);
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.nearestPalindromic("145"));
}

入力

“145”

出力

141