查找最近的回文数

问题陈述

给定一个表示整数的字符串 n，返回最接近的（不包括自身）回文整数。如果有平局，则返回较小的那个。

最接近定义为两个整数之间的绝对差最小。

Java 方法 1 使用二分查找

输出

代码解释

• 这个 Java 程序通过对最接近的回文候选数进行二分查找，来查找给定输入的最接近的回文数。 nearestPalindromic 方法将输入字符串转换为 long，然后使用二分查找（bs 方法）来定位两侧最接近的回文数。
• best 方法比较绝对差以确定最接近的回文数。该代码利用高效的逐位重构（reconstruct 方法）来形成回文数。

时间复杂度

• 时间复杂度为 O(log10(N))，其中 N 是输入数字。这是由于对数字范围执行了二分查找（BS 方法）来查找最接近的回文数。逐位重构和比较操作也促成了对数复杂度。

空间复杂度

• 空间复杂度为 O(1)，表示常数空间使用。该程序使用最少的额外空间用于变量，并且不依赖于输入的大小。二分查找的递归性质对空间复杂度贡献很小。

使用贪婪方法的 Java 方法

输出

代码解释

• 该代码通过检查最接近的较小和较大的回文数来确定给定输入整数最接近的回文数。它将输入转换为整数，进行迭代以查找最接近的较小和较大的回文数，并比较距离。
• 该程序返回最接近的回文数。 isPalindrome 方法验证一个字符串是否是回文数。

时间复杂度

• 时间复杂度为常数 O(1)，因为算法迭代固定次数来查找最接近的较小和较大的回文数，并且输入大小不影响迭代次数。

空间复杂度

• 空间复杂度也为常数 O(1)，因为算法使用有限数量的变量，并且不依赖于动态数据结构。无论输入大小如何，内存需求都保持不变，这使得该算法在时间和空间方面都非常高效。