在C ++中找到最近的回文

假设我们有一个数字n，我们必须得到最接近的数，即回文数。因此回文数可以小于或大于绝对差较小的数字。因此，如果数字是145，则结果将是141。

为了解决这个问题，我们将遵循以下步骤-

sn：=n的大小

如果sn与1相同，则-

将n[0]减1并返回大小为n[0]的1s字符串

half_sn：=（sn+1）/2

half_val：=stol（n的子串从索引0到half_sn

定义一个候选数组={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删除最后一个元素

rev：=将c转换为字符串

如果snmod2不为零，则-

反转阵列转速

在候选人末尾插入c

对候选数组进行排序

val：=n为整数

对于候选人中的每个候选人-

min_diff：=差异

ans：=将候选者转换为字符串

忽略以下部分，跳至下一个迭代

如果候选人与val相同，则-

diff：=绝对|候选–val|

如果diff<min_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