最近的回文数

Question

我遇到了一个常见的面试问题,即找到最接近的回文数.假设输入为127,则输出为131,如果为125则输出为121.

我可以提出逻辑,但我的逻辑在某些情况下失败,例如91,911.在这些输入中,它给出99,919,但正确的输出是88和909.

算法步骤是:

• 将数字转换为字符串.
• 以相反的顺序将上半部分复制到后半部分
• 转换为数字并测量abs.与原始数字diff1的差异
• 添加1到半个字符串,现在以相反的顺序将前半部分复制到后半部分
• 转换为数字并测量abs.与原始数字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那么我们将从中减去1 C.让我们说吧V = C-1.所以我们有ABVVBA,就像上面我们将测试一样:ABCDEF - ABCCBA > ABCDEF - ABVVBA你将拥有相同的解决方案.

诀窍是ABCDEF总是在ABTTBA和之间,ABVVBA而且这些数字之间唯一的其他回文是ABCCBA.因此,您只有3个解决方案选项.如果你比较ABCDEF,以ABCCBA你只需要检查2.

我不认为你很难适应任何规模的数字.并在奇数个数字的情况下,你只是有ABCBA,ABVBA和ABTBA等...

就像你的例子一样:让我们拿911.

1. 忽略最后一个我们只采取上半场(向上舍入).所以91X.
2. 将X替换为9.我们有919.这是中点.
3. 我们知道我们原来的911小于919所以从我们的中间数减去1,所以得到第二个(下限)909.
4. 比较911 - 919和911 - 909
5. 返回差异最小的那个.

所以这给了我们一个恒定的时间算法:) 正如评论中指出的那样,在最坏的情况下(oops),这不是恒定时间,但肯定比蛮力方法更好.

这似乎是你所拥有的,但我认为我会详细说明这个问题,因为它似乎是你的一个小编程错误.