题目描述
Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.
The closest is defined as the absolute difference minimized between two integers.
给定一个表示整数的字符串 n ,返回与它最近的回文整数(不包括自身)。如果不止一个,返回较小的那个。
“最近的”定义为两个整数差的绝对值最小。
分析
其实是比较5个数的大小
ref{:target=”_blank”}
C++ 代码
class Solution {
public:
typedef long long LL;
string nearestPalindromic(string num) {
int n = num.size();
LL num_ll = stoll(num);
set<LL> res;
string pre = num.substr(0, (n+1)/2);
int pre_num = stoi(pre);
// 从前缀数字拼接回文串, eg 12345 -> 12321, 123456 -> 123321
// 分奇偶数字讨论
for(int i=pre_num-1; i<=pre_num+1; ++i) {
string prev = to_string(i);
string last = prev;
reverse(last.begin(), last.end());
string str;
if(n&1) {
// 奇数
str = prev + last.substr(1);
} else {
str = prev + last;
}
res.insert(stoll(str));
}
// 2个特殊情况, eg. 99 是 1001 修正为 101,比原来的位数多1
LL res4 = pow(10, n) + 1;
res.insert(res4);
// 比原来的位数少1,eg 10 -> 9
LL res5 = pow(10, n-1) - 1;
res.insert(res5);
// 删除本身数字
res.erase(num_ll);
LL min_res = 2e18;
for(auto t : res) {
if(abs(t-num_ll) < abs(min_res-num_ll)) {
min_res = t;
} else if(abs(t-num_ll) == abs(min_res-num_ll)) {
min_res = min(min_res, t);
}
}
return to_string(min_res);
}
};