数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中查找最接近的回文数
假设我们有一个数字n，我们需要找到最接近它的回文数。这个回文数可以小于或大于n，只要其绝对差值最小即可。例如，如果数字是145，则结果将是141。
为了解决这个问题，我们将遵循以下步骤：
- sn := n的位数
- 如果sn等于1，则：
- 将n[0]减1，并返回一个长度为n[0]的由1组成的字符串
- half_sn := (sn + 1) / 2
- half_val := 将n从索引0到half_sn的子串转换为整数
- 定义一个数组candidates = {10^(sn) – 1, 10^(sn - 1) - 1, 10^(sn - 1) + 1, 10^(sn)+1}
- 定义一个数组fmdc = { half_val, half_val - 1, half_val + 1 }
- 对于fmdc中的每个值c：
- rev := 将c转换为字符串
- 如果sn模2不为零，则：
- 删除rev的最后一个元素
- 反转数组rev
- 将c添加到candidates数组的末尾
- 对candidates数组进行排序
- val := 将n转换为整数
- 对于candidates中的每个候选值：
- 如果候选值等于val，则：
- 忽略以下部分，跳过到下一个迭代
- diff := abs|候选值 – val|
- 如果diff < min_diff，则：
- min_diff := diff
- ans := 将候选值转换为字符串
- 如果候选值等于val，则：
- 返回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
更新于：2020年6月1日
178 次查看
广告