c++ - 最近回文数

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

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

算法步骤为:

将数字转换为字符串。

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

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

的区别

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

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

的区别

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

最佳答案

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

从这开始，我要说的是，我们可以忽略数字的最低有效部分，因为这实际上并不重要(确定距离时很重要，但仅此而已)。

我将使用一个抽象数字: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

返回差异最小的那个。

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

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