我碰到的常见的面试问题，这是找到最接近的回文数之一。说，如果输入是127输出，然后将131，如果它是125，那么它应该得到121作为输出。

I came across one of the common interview question which was to find the closest palindrome number. Say if the input is 127 then output will be 131 and if it is 125 then it should give 121 as output.

我能想出的逻辑，但在某些特定情况下，像91，911。这些投入是给99，919，但正确的输出为88和909我的逻辑失败。

I can come up with the logic but my logic fails on certain cases like 91, 911. In these inputs it give 99 , 919 but the correct output is 88 and 909.

算法步骤如下：

转换成数字符串。 复制上半年下半场以相反的顺序 转换为数字并测量腹肌。与原来的号码DIFF1差 加1，半串，现在上半场复制到下半年以相反的顺序 转换为数字并测量腹肌。与原来的号码DIFF2差 如果DIFF1小于DIFF2返回第一个编号，否则返回第二号

推荐答案

这其实是一个有趣的问题。很明显，你想要做的，使不仅仅是蛮力这更多的是用最显著数字，并把它们放在最显著位的位置，形成一个回文。 （我要去指回文和原之间的差作为距离）

This is actually an interesting problem. Obviously what you want to do to make this more than just a brute force is to use the most significant digits and put them in the least significant digit locations to form a palindrome. (I'm going to refer to the difference between the palindrome and the original as the "distance")

这是我会说我们可以忽视的数字的最低显著的一半，因为它其实并不重要（它的事项决定的距离的时候，但仅此而已）。

From that I'm going to say that we can ignore the least significant half of the numbers because it really doesn't matter (it matters when determining the distance, but that's all).

我要带一个抽象的数字： ABCDEF 。其中A，B，C，D，E，F都是随机数字。又正如我所说的D，E，F的不需要确定回文因为我们要的是第一的数字半反射镜到下半年。显然，我们并不想这样做的其他方式，否则我们会被修改从而从原来的一个更大的距离更显著的数字。

I'm going to take an abstract number: ABCDEF. Where A,B,C,D,E,F are all random digits. Again as I said D,E,F are not needed for determining the palindrome as what we want is to mirror the first half of the digits onto the second half. Obviously we don't want to do it the other way around or we'd be modifying more significant digits resulting in a greater distance from the original.

因此​​，一个回文将 ABCCBA ，但是因为你已经指出，这并不总是你的最短距离。然而，办法仍然是形式 XYZZYX 所以如果我们想减少的，我们正在修改数字的意义，这将意味着我们会想修改C（或中间最位）。

So a palindrome would be ABCCBA, however as you've already stated this doesn't always you the shortest distance. However the "solution" is still of the form XYZZYX so if we think about minimizing the "significance" of the digits we're modifying that would mean we'd want to modify C (or the middle most digit).

让我们退后一步，看看为什么： ABCCBA

Lets take a step back and look at why: ABCCBA

在开始它可能是很有诱惑力的修改 A ，因为它是在最显著位置：最右边。然而，为了修改至少显著我们需要修改最显著。因此， A 是的。 同样可以说 B ，所以 C 最终被我们所选择的数字。 At first it might be tempting to modify A because it's in the least significant position: the far right. However in order to modify the least significant we need to modify the most significant. So A is out. The same can be said for B, so C ends up being our digit of choice.

好了，现在我们要修改我们已经制定了 C 让我们有可能更接近一些，我们需要思考的范围。 ABCDEF 是我们原来的号码，如果 ABCCBA 不是最近的回文，那么可能是什么？根据我们的一点弯路上面我们可以通过修改 C 找到它。因此，有两种情况， ABCDEF 大于 ABCCBA 或小于 ABCCBA 。

Okay so now that we've worked out that we want to modify C to get our potentially closer number we need to think about bounds. ABCDEF is our original number, and if ABCCBA isn't the closest palindrome, then what could be? Based on our little detour above we can find it by modifying C. So there are two cases, ABCDEF is greater than ABCCBA or that is less than ABCCBA.

如果 ABCDEF 大于 ABCCBA 然后让加1 C 。我们会说 T = C + 1 所以现在我们有一些 ABTTBA 。因此，我们将进行测试，以确保 ABCDEF - ABCCBA＆GT; ABCDEF - ABTTBA 如果是这样，我们知道， ABTTBA 是最近的回文。正如任何更多的修改到C只会把我们越来越远。

If ABCDEF is greater than ABCCBA then lets add 1 to C. We'll say T = C+1 so now we have a number ABTTBA. So we'll test to make sure that ABCDEF - ABCCBA > ABCDEF - ABTTBA and if so we know that ABTTBA is the nearest palindrome. As any more modifications to C would just take us more and more distant.

另外，如果 ABCDEF 小于 ABCCBA 然后我们再减去1 Ç 。比方说， V = C-1 。因此，我们有 ABVVBA ，它就像上面我们将测试： ABCDEF - ABCCBA＆GT; ABCDEF - ABVVBA ，你就会有相同的解决方案

Alternately if ABCDEF is less than ABCCBA then we'll subtract 1 from C. Let's say V = C-1. So we have ABVVBA, which just like above we'll test: ABCDEF - ABCCBA > ABCDEF - ABVVBA and you'll have the same solution.

诀窍是， ABCDEF 总是与 ABTTBA 和 ABVVBA 和这些数字之间的唯一其他回文是 ABCCBA 。所以，你只能有3个选项的解决方案。如果你比较 ABCDEF 到 ABCCBA 你只需要检查2。

The trick is that ABCDEF is always between ABTTBA and ABVVBA and the only other palindrome between those numbers is ABCCBA. So you only have 3 options for a solution. and if you compare ABCDEF to ABCCBA you only need to check 2.

我不认为这将是你很难去适应这个任意大小的数字。而在数字为奇数的情况下，你只需 ABCBA ， ABVBA 和 ABTBA 等等...

I don't think it will be hard for you to adapt this to numbers of any size. and in the case of an odd number of digits you'd simply have ABCBA, ABVBA and ABTBA and so on...

所以就像你的例子：让我们911

So just like your examples: lets take 911.

忽略最后的1仅以上半年（四舍五入）。所以91X。 将X替换为9。我们有919，这是出中点。 我们知道，我们原来的911小于919那么减去1从我们中间的数字，所以我们得到我们的第二个（下界）909。 比较 911 - 919 和 911 - 909 返回一个与最小的区别。 Ignore the last 1 we only take the first half (round up). so 91X. Replace X with 9. we have 919. this is out mid point. We know our original 911 is less than 919 so subtract 1 from our middle number so we get our second (lower bound) 909. Compare 911 - 919 and 911 - 909 return the one with the smallest difference.

所以这给了我们一定的时间的算法：）

So this gives us a constant time algorithm :)

这似乎是你有什么，但我想我会阐述，希望能够阐明这个问题光，因为它似乎是你的一部分，否则一个小的编程错误。

This appears to be what you have, but I thought I'd elaborate to hopefully shed light on the issue as it seems to be a small programming error on your part otherwise.