Java 中的下一个最小回文数问题

给定一个表示整数的字符串 n，我们的任务是找到一个回文数并返回最接近的整数（不包括自身）。如果出现平局，则返回较小的一个。通过最小化两个整数之间的绝对差来确定哪个最接近。

示例 1

输入

int N = 1000

输出

下一个最小的回文数是 1001。

解释

对于给定的数字 1000，下一个最小的数字是 1001，它也是一个回文数。因此，下一个最小的回文数是 1001。

示例 2

输入

int N = 8888

输出

下一个最小的回文数是 8998。

解释

对于给定的数字 8888，下一个最小的数字是 8998，它也是一个回文数。因此，下一个最小的回文数是 8998。

示例 3

输入

int N = 1331

输出

下一个最小的回文数是 1441。

解释

对于给定的数字 1331，下一个最小的数字是 1441，它也是一个回文数。因此，下一个最小的回文数是 1441。

从上面的三个例子中，我们看到了三种不同类型的输入。

1. 输入数字是一个具有相同数字的数（示例 2）。
2. 输入整数不是回文数（示例 1）。
3. 输入数字是一个具有所有不同数字的回文数（示例 3）。

方法：朴素方法

为了将其转换为回文数，我们可以取左侧或右侧的镜像。从右侧镜像得到的回文数不一定是下一个较大的回文数。因此，我们需要将左侧的镜像复制到右侧。但是，有不同的情况需要不同的方法。让我们来看一下接下来的步骤。我们将使用两个索引 i 和 j 来开始。i 将指向两个中间元素，或者如果 n 是奇数，则指向围绕中间元素的两个元素。我们每次将 i 和 j 分开一个。

算法

步骤 1: 初始声明函数 isPalindrome。输入参数是整数 N，返回值是 1 如果 N 是回文数，否则返回 0。

步骤 2: 初始化变量 num、k 和 reverse，分别存储输入 N 的数字、当前数字和反转后的数字。

步骤 3: 将 N 的初始值存储在 num 中。

步骤 4: 使用 while 循环反转 N 的数字，然后将结果存储在 reverse 中。

步骤 5: 确定初始数字 num 是否等于其反转。如果相等则返回 1；否则返回 0。

实施

文件名: NextPalindromeNaive.java

输出

The smallest Next Palindrome is :1001

输出

时间复杂度：O(N * |N|)，其中“N”表示输入的数字，空间复杂度：O(1)

方法：高效方法

此方法包含一种算法，可以高效地找出大于给定数字的下一个回文数。通过迭代遍历输入数字的各位，它会检查回文属性并确定是否需要进行任何更改。当需要进位时，它会使用递归方法来处理。为了保持回文数的完整性，重要的是确认数字是否已经是回文数，确定需要增加或减少哪些数字，并相应地修改数字以确保生成下一个回文数。

算法

步骤 1: 声明一个名为“addingOne”的函数，用于将数字表示为字符串，并使用 StringBuilder。

步骤 2: 初始化两个变量，分别表示数字和要递增的数字的索引。

步骤 2.1: 如果索引小于 0，则在 StringBuilder 的开头和结尾附加 '1'，表示需要额外的数字。

步骤 2.2: 如果当前数字是 '9'，则将当前索引处的数字设置为 '0'，然后递归调用自身处理下一个数字。

步骤 2.3: 否则，将当前数字加一，并将其镜像到对应的最后一个数字。

步骤 3: 初始化一个 StringBuilder 来存储数字，以及用于跟踪回文属性的变量。

步骤 4: 遍历输入数字的一半，检查回文属性并确定是否需要进行任何修改。

步骤 5: 如果数字已经是回文数，则通过调用 addingOne 函数来增加数字的中间或中间-1 位（取决于数字的长度）。

步骤 6: 此外，如果整数不是回文数且不需要减法，则运行 addingOne 函数来递增相关数字。

步骤 7: 最后将计算出的回文数作为字符串返回。

实施

文件名: EfficientNextPalindrome.java

输出

The next smallest palindromic value is: 1001

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(N)，其中 N 代表输入字符串的长度。