Java 中通过更改最多 K 位数字构造最大回文数

给定一个输入数字和一个整数 K，任务是通过更改最多 K 个数字来找到最大的回文数。修改涉及将数字中的一个数字替换为另一个数字，但总更改次数不得超过 K。该问题要求开发一种算法，通过策略性地选择要修改的数字，同时保持在给定约束内，从而有效地识别最大的回文数。

示例 1

输入 "12321"

K2

输出：最大的回文数："12321"

解释：输入为 "12321"，最多可以更改 2 位数字。然而，由于该字符串本身已经是回文，因此不需要进行任何更改。

示例 2

输入"45678"

K3

输出：最大的回文数："87678"

解释：输入为 "45678"，最多可以更改 3 位数字。但是，为了获得最大的回文数，我们在进行三次更改后，得到字典序最大的回文数是 "87678"。

示例 3

输入"12345"

K1

输出：最大的回文数："无法实现"

解释：输入为 "12345"，最多可以更改 1 位数字。然而，在这种情况下，通过更改三位数字无法形成回文，并且该字符串不包含任何重复数字，通过更改三位数字会得到字典序较小的数字。

方法 1：使用双指针

该方法涉及使用两个指针，一个从字符串开头开始，另一个从结尾开始。比较对应位置的字符，如果它们不相同，则应将其中一个字符替换为另一个字符，使它们相同。跟踪所做的更改次数，直到指针相遇或达到最大更改次数。

算法

步骤 1：将输入字符串 str 转换为字符数组 chars。

步骤 2：初始化两个指针 left 和 right 分别指向字符数组的开头和结尾。

步骤 3：当 left 小于或等于 right 时，使用 while 循环迭代。

步骤 3.1：如果 left 和 right 位置的字符不相等。

步骤 3.1.1：检查是否不再允许更改（k 达到 0）。如果是，则返回“无法实现”。

步骤 3.1.2：选择 chars[left] 和 chars[right] 中较大的字符，并将这两个位置都更新为选定的字符。

步骤 3.1.3：将可用更改次数 k 减 1。

步骤 3.2：将 left 指针向前移动一步，将 right 指针向后移动一步。

步骤 4：将字符数组 chars 转换回字符串。

步骤 5：返回得到的最​​大回文数。

实施

上述步骤的实现如下所示

输出

Example 1:
Input: 12321, k = 2
Largest Palindrome: 12321
Example 2:
Input: 45678, k = 3
Largest Palindrome: 87678
Example 3:
Input: 12345, k = 1
Largest Palindrome: Not Possible

复杂度分析

时间复杂度： O(n) - 该算法会遍历字符数组一次，进行比较和可能的字符更改。

空间复杂度： O(n) - 该算法使用额外的空间来存储字符数组 chars，其长度等于输入字符串 n 的长度。

方法 2：使用递归

该方法涉及递归探索更改数字的所有可能组合，以找到最大的回文数。从字符串的最左侧和最右侧位置开始，尝试更改数字，直到达到最大更改次数或形成回文数。

算法

步骤 1：创建一个变量 largestPalindrome 来存储找到的最大回文数。

步骤 2：调用 findLargestPalindrome 方法，传入输入字符串 str 和最大数字更改次数 k。

步骤 3：在 findLargestPalindrome 方法内部。

步骤 3.1：将 largestPalindrome 初始化为空字符串。

步骤 3.2：调用 largestPalinRec 方法对 str 的字符数组表示进行递归。

步骤 3.3：如果在递归后 largestPalindrome 仍然为空，则返回“无法实现”，表示通过更改最多 k 个数字无法形成回文数。

步骤 3.4：否则，返回 largestPalindrome。

步骤 4：largestPalinRec 方法。

步骤 4.1：如果左指针 left 大于或等于右指针 right，则表示整个字符串已处理完毕。现在将 largestPalindrome 指定为当前的字符数组。

步骤 4.2：如果 left 和 right 的字符相等，则将指针移向内侧并继续递归。

步骤 4.3：如果 left 和 right 的字符不相等，则检查是否还有剩余的数字更改（k > 0）。

步骤 4.3.1：选择两个字符中较大的一个，并更新两个位置。

步骤 4.3.2：将 k 减 1。

步骤 4.3.3：将指针移向内侧并继续递归。

步骤 5：在 main 方法中，提供了三个示例。

步骤 5.1：示例 1：输入字符串为 "12321"，k 为 2。

步骤 5.2：示例 2：输入字符串为 "45678"，k 为 3。

步骤 5.3：示例 3：输入字符串为 "12345"，k 为 1。

步骤 5.4：打印每个示例的最大回文数。

实施

上述步骤的实现如下所示

输出

Example 1:
Input: 12321, k=2
Largest Palindrome:12321
Example 2:
Input:45678,   k=3
Largest Palindrome: 87678
Example 3:
Input: 12345, k=1
Largest Palindrome: Not Possible

复杂度分析

时间复杂度：此算法的时间复杂度为 O(N)，其中 N 是输入字符串 str 的长度。这是因为在递归期间，我们需要处理字符串中的每个字符一次。

空间复杂度：空间复杂度也为 O(N)。这是因为用于存储字符串的字符数组表示以及递归调用堆栈的空间。