Find the Largest Palindrome Divisible by K in Java

给定两个正整数 n 和 k。如果 x 是回文数，则该数被称为 k-回文数。x 可被 k 整除。以字符串形式返回最大的 n 位 k-回文整数。

示例 1

输入

int N = 2

int k = 3

输出

最大的回文数是 "99"。

解释

对于两位数回文数（形式为 aa），能被三整除的最大数字是 99。它满足 99 % 3 == 0 的条件。

示例 2

输入

int N = 5

int k = 11

输出

最大的回文数是 "99999"。

解释

对于五位数回文数，能被十一整除的最大数字是 99999。它满足 99999 % 11 == 0 的条件。

示例 3

输入

int n = 3

int k = 5

输出

最大的回文数是 "595"。

解释

对于三位数回文数，能被五整除的最大数字是 595。它满足 595 % 5 == 0 的条件。

方法：暴力算法

为了最小化普通 字符串 连接的复杂性，代码使用了 StringBuilder。它通过对各种除数（k 值）应用特定逻辑来处理 1、2、4、5、6、7 和 8 等数字的情况。递归方法用于构建回文数，每个方法都会为指定的位数（N）定制回文数。通过使用子字符串操作和模运算，回文数被修改以确保它满足模标准，即在 k == 7 的情况下可被 7 整除。为了保持对称性，程序还处理奇数和偶数长度的情况。总体策略基于递归和贪心方法的组合，用于创建满足可整除性标准的回文数。

算法

步骤 1: 初始化 N（位数）和 k（除数）。

步骤 2: 使用 k 来选择要调用的情况方法

k = 1, 3, 9 时，使用 case139(N)

k = 2 时，使用 case2(N)

k = 4 时，使用 case4(N)

k = 5 时，使用 case5(N)

k = 6 时，使用 case6(N)

k = 8 时，使用 case8(N)

k = 7 或其他值时，使用 case7(N)。

步骤 3: 使用特定模式（例如填充 "8"、重复 "9" 或检查中间值的可整除性）创建回文数。

步骤 4: 更改中间数字或数字，并使用模运算验证 k = 7（或其他困难情况）的可整除性。

步骤 5: 返回最大的有效回文数。

实施

输出

 
The largest Palindrome is given by : 595   

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(1)。

方法：贪心法

代码指定了一个使用贪心方法确定可被 k 整除的 N 位最大回文数的 Java 程序。根据 k 的值，使用几种规则来有效地生成回文数。对于某些 k 值（如 1、3 或 9），使用 '9' 来填充所有数字。为了满足可整除性和回文数标准，它会计算中间数字，并将特定模式（如 "8"、"5" 或 "88"）附加到其他数字上。为了确保大整数的准确性，模运算和 BigInteger 被用于对奇数和偶数长度的回文数进行特殊处理，特别是对于 6 和 7 等除数。为了在满足可整除性要求的同时生成回文数，该算法特别强调模块化和性能。

算法

步骤 1: 初始化 N 作为位数，k 作为除数。

步骤 2: 对于 k = 1, 3, 9：返回一个 N 位的全为 9 的回文数。

步骤 3: 对于 k = 2，如果 N = 1，返回 "8"。

步骤 3.1: 否则，构造一个中间数字为 "9"，开头和结尾为 "8" 的回文数。

步骤 4: 对于 k = 4，如果 N < 4，则返回重复 N 次的 "8"。

步骤 4.1: 否则，构造一个中间数字为 "9"，开头和结尾为 "88" 的回文数。

步骤 5: 对于 k = 5，如果 N = 1，返回 "5"。

步骤 5.1: 否则，构造一个使用中间数字 "9"，开头和结尾为 "5" 的回文数。

步骤 6: 对于 k = 6

在处理奇数和偶数长度的回文数的同时，验证其是否可被三整除。为了可整除性，在两端使用 "8"，并修改中间数字。

步骤 7: 对于 k = 8，如果 N < 7，则返回重复 N 次的 "8"。

步骤 7.1: 否则，构造一个以 "888" 开头和结尾，中间数字为 "9" 的回文数。

步骤 8: 对于 k = 7

使用模运算检查是否可被七整除，并为奇数或偶数 N 生成可能的回文数。为提高精度，请使用 BigInteger。

步骤 9: 使用合适的模式或迭代修改来构建回文数。

步骤 10: 返回结果

实施

输出

 
The largest Palindrome is given by : 595   

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(1)。