c++ - 最近回文数

Question

我碰到一个常见的面试问题之一，就是找到最接近的回文数。假设输入为127，则输出为131，如果为125，则输出为121。

我可以提出逻辑，但是在某些情况下，例如91、911，我的逻辑会失败。在这些输入中，它的值为99、919，但正确的输出是88和909。

算法步骤为:

将数字转换为字符串。

以相反的顺序将上半部分复制到后半部分

转换为数字并测量绝对值。与原始编号diff1

的差异

将1添加到一半字符串，然后以相反的顺序将上半部分复制到后半部分

转换为数字并测量绝对值。与原始数字diff2

的区别

如果diff1小于diff2，则返回第一个数字，否则返回第二个数字

Answer 1

这实际上是一个有趣的问题。显然，要使这不仅仅是暴力破解，您要做的就是使用最高有效的数字并将其放在最低有效的数字位置以形成回文。 (我将回文和原始之间的差异称为“距离”)

从这开始，我要说的是，我们可以忽略数字中最低的一半，因为这实际上并不重要(确定距离时很重要，但这仅是全部)。

我将使用一个抽象数字: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，那么我们将从 C中减去1。假设 V = C-1。因此，我们有了 ABVVBA，就像上面我们将测试的: ABCDEF - ABCCBA > ABCDEF - ABVVBA，您将拥有相同的解决方案。

诀窍是 ABCDEF总是介于 ABTTBA和 ABVVBA之间，而这些数字之间的唯一其他回文是 ABCCBA。因此，您只有3个解决方案。如果将 ABCDEF与 ABCCBA比较，则只需检查2。

我认为您很难适应任何大小的数字。如果是奇数个数字，则只需输入 ABCBA， ABVBA和 ABTBA等等。

因此，就像您的示例一样:让911。

忽略最后1个，我们只取前半部分(向上取整)。所以是91X。

用9替换X。我们有919。这是中点。

我们知道我们的原始911小于919，因此请从中间数字中减去1，以便获得第二个(下限)909。

比较911 - 919和911 - 909

返回差异最小的那个。

因此，这为我们提供了一个恒定时间算法:)
正如评论中指出的那样，这在最坏的情况下不是固定的时间(哎呀)，但肯定比暴力破解更好。

这似乎是您所拥有的，但是我认为我希望能详细说明该问题，因为这在您看来似乎是一个很小的编程错误。