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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数字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转换为字符串

    • 如果sn mod 2不为零，则-

    • 反转阵列转速

    • 在候选人末尾插入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

    以上是 在C ++中找到最近的回文 的全部内容， 来源链接： utcz.com/z/317151.html

    回到顶部