0564. Find the Closest Palindrome¶
题目信息¶
- 题号:
0564
- 难度:
Hard
- 主题:
十进制字符串、回文整数、最近距离、并列规则
- 原题:
- 重点:
不能返回原数本身、比较绝对差、距离相同取较小整数、结果仍以字符串返回
题目重述¶
给定一个表示正整数的字符串 n,寻找与该整数绝对差最小的另一个回文整数,并以字符串形式返回。
候选回文数不能等于 n 本身。若两个不同回文数与 n 的距离相同,返回数值较小的那个。输入不含前导零,数值位于 [1, 10^18 - 1];回文整数的十进制表示从左到右与从右到左相同。
自建示例¶
较大的回文更接近:
输入:n = "128"
输出:"131"
解释:131 与 128 相差 3,而较近的较小回文 121 相差 7。
距离并列时选择较小值:
输入:n = "10"
输出:"9"
解释:回文 9 和 11 都与 10 相差 1,按规则返回较小的 9。
只需比较前缀变化产生的邻近候选¶
回文数的高半段决定低半段。保留 n 的前半部分,分别将它减 1、保持不变、加 1 后镜像,就得到最接近的同位数回文候选;另外加入 99...9 和 100...001,覆盖位数减少或增加的边界。用集合去重,并排除等于原数的候选。
比较时先看与原数的绝对差,差值相等则取数值更小者。所有候选都用整数比较,最后再转回字符串。
C++ 实现¶
class Solution {
long long makePalindrome(long long prefix, int length) {
std::string left = std::to_string(prefix);
std::string result = left;
int begin = static_cast<int>(left.size()) -
(length % 2 == 1 ? 2 : 1);
for (int i = begin; i >= 0; --i) result.push_back(left[i]);
return std::stoll(result);
}
public:
std::string nearestPalindromic(std::string n) {
int length = static_cast<int>(n.size());
long long value = std::stoll(n);
long long power = 1;
for (int i = 0; i < length; ++i) power *= 10;
std::set<long long> candidates;
candidates.insert(power + 1);
candidates.insert(power / 10 - 1);
int halfLength = (length + 1) / 2;
long long prefix = std::stoll(n.substr(0, halfLength));
for (long long delta = -1; delta <= 1; ++delta) {
candidates.insert(makePalindrome(prefix + delta, length));
}
long long answer = -1;
for (long long candidate : candidates) {
if (candidate == value || candidate < 0) continue;
if (answer == -1 ||
std::llabs(candidate - value) <
std::llabs(answer - value) ||
(std::llabs(candidate - value) ==
std::llabs(answer - value) &&
candidate < answer)) {
answer = candidate;
}
}
return std::to_string(answer);
}
};
代码分析¶
同位数回文只会随前缀的相邻变化跨过原数附近,两个位数边界候选补足了前缀借位或进位导致的长度变化;因此候选集合覆盖最近回文。排除原数后按距离和数值双重规则选择,候选数量为常数,时间复杂度为 O(|n|),额外空间复杂度为 O(|n|)。