我遇到了一个常见的面试问题，即找到最接近的回文数。假设如果输入是 127，那么输出将是 131，如果是 125，那么它应该给出 121 作为输出。
我可以想出逻辑，但我的逻辑在某些情况下失败，例如 91、911。在这些输入中，它给出 99、919，但正确的输出是 88 和 909。
算法步骤是：
这实际上是一个有趣的问题。显然，您想要做的不仅仅是使用蛮力，而是使用最高有效数字并将它们放在最低有效数字位置以形成回文。（我将把回文和原来的区别称为“距离”）
我要说的是，我们可以忽略最不重要的一半数字，因为它真的无关紧要（在确定距离时很重要，但仅此而已）。
我要取一个抽象的数字： ABCDEF。其中 A,B,C,D,E,F 都是随机数字。同样，正如我所说，确定回文不需要 D、E、F，因为我们想要的是将前半部分数字镜像到后半部分。显然我们不想反过来做，否则我们会修改更多有效数字，导致与原始数字的距离更大。
因此，回文将是ABCCBA，但是正如您已经说过的，这并不总是您的最短距离。然而，“解决方案”仍然是形式XYZZYX，所以如果我们考虑最小化我们正在修改的数字的“重要性”，这意味着我们想要修改 C（或最中间的数字）。
让我们退后一步，看看为什么：ABCCBA
A，因为它处于最不重要的位置：最右边。然而，为了修改最不重要的，我们需要修改最重要的。所以A出来了。B，所以C最终成为我们的选择。好的，现在我们已经计算出我们想要修改C以获得我们可能更接近的数字，我们需要考虑边界。ABCDEF是我们的原始数字，如果ABCCBA不是最近的回文数，那可能是什么？根据我们上面的小弯路，我们可以通过修改C. 所以有两种情况，ABCDEF大于ABCCBA或小于ABCCBA。
如果ABCDEF大于ABCCBA则让 1 加到C. 我们会说T = C+1现在我们有一个数字ABTTBA。因此，我们将进行测试以确保，ABCDEF - ABCCBA > ABCDEF - ABTTBA
如果是，我们知道这ABTTBA是最近的回文。因为对 C 的任何更多修改只会让我们越来越遥远。
或者，如果ABCDEF小于，ABCCBA我们将从 中减去 1 C。比方说V = C-1。所以我们有ABVVBA，就像上面我们将测试的一样：ABCDEF - ABCCBA > ABCDEF - ABVVBA你将有相同的解决方案。
诀窍是ABCDEF始终介于ABTTBA和之间，ABVVBA而这些数字之间唯一的另一个回文是ABCCBA。因此，您只有 3 个解决方案选项。如果你比较ABCDEF你ABCCBA只需要检查2。
我不认为你很难适应任何大小的数字。并且在奇数位数的情况下，您只需拥有ABCBA，ABVBA依此ABTBA类推...
就像您的示例一样：让我们拨打 911。
911 - 919和911 - 909所以这给了我们一个恒定时间算法:)
正如评论中所指出的，这在最坏的情况下不是恒定时间（哎呀），但肯定比蛮力方法更好。
这似乎是您所拥有的，但我想我会详细说明以希望阐明这个问题，因为否则它似乎是您的一个小编程错误。
这是 Naveen 和 Don 算法的实现。它使用 Happy Yellow Face 的算法作为测试预言机。
我很高兴看到人们对其进行调整以删除多余的步骤或特殊情况。
gcc 4.7.3：g++ -Wall -Wextra -std=c++0x 最近回文.cpp
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
// I do not have std::to_string.
template <class T>
std::string to_string(const T& v) {
std::stringstream ss;
ss << v;
return ss.str(); }
// Nor do I have std::stoi. :(
int stoi(const std::string& s) {
std::stringstream ss(s);
int v;
ss >> v;
return v; }
bool isPalindrome(int n) {
const auto s = to_string(n);
return s == std::string(s.rbegin(), s.rend()); }
int specNearestPalindrome(int n) {
assert(0 <= n);
int less = n, more = n;
while (true) {
if (isPalindrome(less)) { return less; }
if (isPalindrome(more)) { return more; }
--less; ++more; } }
std::string reflect(std::string& str, int n) {
std::string s(str);
s.resize(s.size() + n);
std::reverse_copy(std::begin(str),
std::next(std::begin(str), n),
std::next(std::begin(s), str.size()));
return s; }
bool isPow10(int n) {
return n < 10 ? n == 1 : (n % 10 == 0) && isPow10(n / 10); }
int nearestPalindrome(int n) {
assert(0 <= n);
if (n != 1 && isPow10(n)) { return n - 1; } // special case
auto nstr = to_string(n);
// first half, rounding up
auto f1 = nstr.substr(0, (nstr.size() + 1) / 2);
auto p1 = stoi(reflect(f1, nstr.size() / 2));
const auto twiddle = p1 <= n ? 1 : -1;
auto f2 = to_string((stoi(f1) + twiddle));
auto p2 = stoi(reflect(f2, nstr.size() / 2));
if (p2 < p1) { std::swap(p1, p2); }
return n - p1 <= p2 - n ? p1 : p2; }
int main() {
std::vector<int> tests = { 0, 1, 6, 9, 10, 11, 12, 71, 74, 79, 99, 100, 999, 1000, 9900, 9999, 999000 };
for (const auto& t : tests) {
std::cout <<
(nearestPalindrome(t) == specNearestPalindrome(t) ? "." : "X");
}
std::cout << std::endl;
return 0; }
这是一个可以工作的通用算法1，尽管使用蛮力：
int findNearestPalindrome(int n) {
int less = n;
int more = n;
while(true) {
if (isPalindrome(less)) return less;
if (isPalindrome(more)) return more;
--less;
++more;
}
}
在isPalindrome()函数中，您需要做的就是将数字转换为字符串，然后将字符串与自身进行比较 reversed。
1 但是，正如 Ted Hopp 评论的那样，这不会检查平局情况。您必须进行一些更改才能使其可识别。
#include <iostream>
#include <cmath>
#include <functional>
#include <limits>
#include <sstream>
// for convience
using namespace std;
using ULL = unsigned long long int;
// calculate the number of digits
auto Len = [](auto num) -> ULL {
return floor(log10(num)) + 1; };
// extract left half of number
auto Halfn = [](auto num, auto olen) {
for (unsigned i = 0; i < olen / 2; num /= 10, ++i);
return num;
};
int main() {
ULL num; cin >> num;
// some basic checking
if (num < 10) {
cerr << "Error, enter a number >= 10";
return 0;
}
if (numeric_limits<ULL>::max() < num) {
cerr << "Error, number too large\n";
return 0;
}
cout << ([](auto num) {
auto olen = Len(num);
auto lhalf = Halfn(num, olen);
function<ULL(ULL)> palin = [olen] (auto lhalf) {
auto half = to_string(lhalf);
// this is the mirror string that needs to be
// appended to left half to form the final
// palindrome
auto tmp = half.substr(0, olen / 2);
// take care of a corner case which
// happens when the number of digits in
// the left half of number decrease, while
// trying to find a lower palindrome
// e.g. num = 100000
// left half = 100 , the value passed to the
// function palin, is 99. if all digits are 9
// then we need to adjust the count of 9,
// otherwise if i simply replicate it, i'll get
// 9999 but one more 9 is required for the
// correct output.
if (olen / 2 > tmp.size() &&
all_of(tmp.begin(), tmp.end(),
[](auto c) { return '9' == c; })) {
tmp += '9';
}
// append, convert and return
half = half + string(tmp.crbegin(),
tmp.crend());
return stoull(half);
};
auto bpalin = palin(lhalf);
auto hpalin = palin(lhalf + 1);
auto lpalin = palin(lhalf - 1);
stringstream ss;
ss << "base palindrome = " << bpalin <<'\n';
ss << "higher palindrome = "<<hpalin <<'\n';
ss << "lower palindrome = " << lpalin <<'\n';
// calculating absolute difference for
// finding the nearest palindrome
auto diffb = labs(bpalin - num);
auto diffh = labs(hpalin - num);
auto diffl = labs(lpalin - num);
auto nearest = (diffb < diffh) ?
(diffb < diffl) ? bpalin : lpalin :
(diffh < diffl) ? hpalin : lpalin;
ss << "nearest palindrome = "
<< nearest << endl;
return move(ss.str());
}(num));
} // end main
class Solution {
public String nearestPalindromic(String n) {
int order = (int) Math.pow(10, n.length()/2);
Long ans = Long.valueOf(new String(n));
Long noChange = mirror(ans);
Long larger = mirror((ans/order)*order + order+1);
Long smaller = mirror((ans/order)*order - 1 );
if ( noChange > ans) {
larger = (long) Math.min(noChange, larger);
} else if ( noChange < ans) {
smaller = (long) Math.max(noChange, smaller);
}
return String.valueOf( ans - smaller <= larger - ans ? smaller :larger) ;
}
Long mirror(Long ans) {
char[] a = String.valueOf(ans).toCharArray();
int i = 0;
int j = a.length-1;
while (i < j) {
a[j--] = a[i++];
}
return Long.valueOf(new String(a));
}
}
Javascript解决方案：
const findNearestPalindrome = n => {
if (!n) return 0;
let lowestPalindorm = lowestPalindromeHelper(n);
let largestPalindrome = largestPalindromeHelper(n);
let closestPalindrome = 0;
closestPalindrome =
Math.floor(n - lowestPalindorm) > Math.floor(largestPalindrome - n)
? largestPalindrome
: lowestPalindorm;
console.log(closestPalindrome);
};
//lowestPalindrome check
const lowestPalindromeHelper = num => {
for (let i = num - 1; i >= 0; i--) {
if (isPalindrome(i.toString())) {
return i;
}
}
};
//largest Palindrome Check
const largestPalindromeHelper = num => {
for (let i = num + 1; i <= Number.MAX_SAFE_INTEGER; i++) {
if (isPalindrome(i.toString())) {
return i;
}
}
};
const isPalindrome = n => {
return (
n ===
n
.split('')
.reverse()
.join('')
);
};
findNearestPalindrome(1234);