0564. Find the Closest Palindrome ================================ 题目信息 -------- :题号: 0564 :难度: Hard :主题: 十进制字符串、回文整数、最近距离、并列规则 :原题: `LeetCode 0564 `_ :重点: 不能返回原数本身、比较绝对差、距离相同取较小整数、结果仍以字符串返回 题目重述 -------- 给定一个表示正整数的字符串 ``n``,寻找与该整数绝对差最小的另一个回文整数,并以字符串形式返回。 候选回文数不能等于 ``n`` 本身。若两个不同回文数与 ``n`` 的距离相同,返回数值较小的那个。输入不含前导零,数值位于 ``[1, 10^18 - 1]``;回文整数的十进制表示从左到右与从右到左相同。 自建示例 -------- 较大的回文更接近: .. code-block:: text 输入:n = "128" 输出:"131" 解释:131 与 128 相差 3,而较近的较小回文 121 相差 7。 距离并列时选择较小值: .. code-block:: text 输入:n = "10" 输出:"9" 解释:回文 9 和 11 都与 10 相差 1,按规则返回较小的 9。 只需比较前缀变化产生的邻近候选 ------------------------------ 回文数的高半段决定低半段。保留 ``n`` 的前半部分,分别将它减 1、保持不变、加 1 后镜像,就得到最接近的同位数回文候选;另外加入 ``99...9`` 和 ``100...001``,覆盖位数减少或增加的边界。用集合去重,并排除等于原数的候选。 比较时先看与原数的绝对差,差值相等则取数值更小者。所有候选都用整数比较,最后再转回字符串。 C++ 实现 -------- .. code-block:: cpp 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(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(n.size()); long long value = std::stoll(n); long long power = 1; for (int i = 0; i < length; ++i) power *= 10; std::set 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|)``。