3260. 找到能被 K 整除的最大回文数

Hard

题目描述

给你两个正整数 n 和 k。

如果一个整数 x 满足以下条件，则称其为 k 回文数：

x 是一个回文数
x 能被 k 整除

返回具有 n 位数字的最大 k 回文数（以字符串形式返回）。

注意，该整数不能有前导零。

示例 1：

输入：n = 3, k = 5
输出："595"
解释：595 是具有 3 位数字的最大 k 回文整数。

示例 2：

输入：n = 1, k = 4
输出："8"
解释：4 和 8 是唯一具有 1 位数字的 k 回文整数。

示例 3：

输入：n = 5, k = 6
输出："89898"

约束条件：

1 <= n <= 10^5
1 <= k <= 9

提示：

必须有解，因为我们可以让所有数字都等于 k
使用字符串 DP，存储当前形成数字的模数和长度
是否可以使用整除规则贪心求解？

解题思路

这道题要求找到具有 n 位数字且能被 k 整除的最大回文数。关键思路如下：

核心思想：贪心 + 回文性质 + 整除性验证

回文数性质：回文数的前半部分决定了后半部分，所以我们只需要确定前半部分的数字。
贪心策略：为了得到最大的回文数，我们从高位到低位，尽量选择最大的数字（9），然后验证是否能构成能被 k 整除的回文数。
整除性检验：由于回文数的对称性，我们可以通过以下方式检验：
- 构造完整的回文数
- 计算其对 k 的余数
- 如果余数为 0，则找到答案
具体实现：
- 初始化结果数组，所有位置填充 ‘9’
- 从前半部分开始，逐位尝试从 9 到 0 的数字
- 对于每一位，构造对应的回文数并检查是否能被 k 整除
- 使用回溯的方式找到第一个满足条件的组合
特殊处理：
- 当 n = 1 时，直接遍历 9 到 1 找到能被 k 整除的最大数字
- 确保第一位不为 0（避免前导零）

这种方法的优势是能够快速找到最优解，因为我们按照贪心策略优先选择较大的数字。

代码实现

class Solution {
public:
    string largestPalindrome(int n, int k) {
        if (n == 1) {
            for (int i = 9; i >= 1; i--) {
                if (i % k == 0) {
                    return to_string(i);
                }
            }
        }
        
        vector<char> result(n, '9');
        
        function<bool(int)> dfs = [&](int pos) -> bool {
            if (pos == (n + 1) / 2) {
                // Check if palindrome is divisible by k
                long long num = 0, mod = 1;
                for (int i = n - 1; i >= 0; i--) {
                    num = (num + (result[i] - '0') * mod) % k;
                    mod = (mod * 10) % k;
                }
                return num == 0;
            }
            
            int start = (pos == 0) ? 9 : 9;
            for (int digit = start; digit >= 0; digit--) {
                if (pos == 0 && digit == 0) continue; // No leading zeros
                
                result[pos] = '0' + digit;
                if (pos != n - 1 - pos) {
                    result[n - 1 - pos] = '0' + digit;
                }
                
                if (dfs(pos + 1)) {
                    return true;
                }
            }
            return false;
        };
        
        dfs(0);
        return string(result.begin(), result.end());
    }
};

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        if n == 1:
            for i in range(9, 0, -1):
                if i % k == 0:
                    return str(i)
        
        result = ['9'] * n
        
        def is_divisible():
            num = 0
            mod = 1
            for i in range(n - 1, -1, -1):
                num = (num + int(result[i]) * mod) % k
                mod = (mod * 10) % k
            return num == 0
        
        def dfs(pos):
            if pos == (n + 1) // 2:
                return is_divisible()
            
            for digit in range(9, -1, -1):
                if pos == 0 and digit == 0:  # No leading zeros
                    continue
                
                result[pos] = str(digit)
                if pos != n - 1 - pos:
                    result[n - 1 - pos] = str(digit)
                
                if dfs(pos + 1):
                    return True
            
            return False
        
        dfs(0)
        return ''.join(result)

public class Solution {
    public string LargestPalindrome(int n, int k) {
        if (n == 1) {
            for (int i = 9; i >= 1; i--) {
                if (i % k == 0) {
                    return i.ToString();
                }
            }
        }
        
        char[] result = new char[n];
        for (int i = 0; i < n; i++) {
            result[i] = '9';
        }
        
        bool IsDivisible() {
            long num = 0, mod = 1;
            for (int i = n - 1; i >= 0; i--) {
                num = (num + (result[i] - '0') * mod) % k;
                mod = (mod * 10) % k;
            }
            return num == 0;
        }
        
        bool Dfs(int pos) {
            if (pos == (n + 1) / 2) {
                return IsDivisible();
            }
            
            for (int digit = 9; digit >= 0; digit--) {
                if (pos == 0 && digit == 0) continue; // No leading zeros
                
                result[pos] = (char)('0' + digit);
                if (pos != n - 1 - pos) {
                    result[n - 1 - pos] = (char)('0' + digit);
                }
                
                if (Dfs(pos + 1)) {
                    return true;
                }
            }
            return false;
        }
        
        Dfs(0);
        return new string(result);
    }
}

var largestPalindrome = function(n, k) {
    if (k === 1 || k === 3 || k === 9) {
        return '9'.repeat(n);
    }
    
    if (k === 2) {
        if (n === 1) return '8';
        if (n === 2) return '88';
        return '8' + '9'.repeat(n - 2) + '8';
    }
    
    if (k === 4) {
        if (n === 1) return '8';
        if (n === 2) return '88';
        if (n === 3) return '888';
        if (n === 4) return '8888';
        return '88' + '9'.repeat(n - 4) + '88';
    }
    
    if (k === 5) {
        if (n === 1) return '5';
        if (n === 2) return '55';
        return '5' + '9'.repeat(n - 2) + '5';
    }
    
    if (k === 6) {
        if (n === 1) return '6';
        if (n === 2) return '66';
        if (n % 2 === 1) {
            return '8' + '9'.repeat((n - 3) / 2) + '8' + '9'.repeat((n - 3) / 2) + '8';
        } else {
            return '8' + '9'.repeat((n - 2) / 2 - 1) + '77' + '9'.repeat((n - 2) / 2 - 1) + '8';
        }
    }
    
    if (k === 7) {
        let result = new Array(n).fill('9');
        
        for (let start = 9; start >= 0; start--) {
            result[0] = start.toString();
            result[n - 1] = start.toString();
            
            for (let i = 1; i < Math.floor(n / 2); i++) {
                for (let d = 9; d >= 0; d--) {
                    result[i] = d.toString();
                    result[n - 1 - i] = d.toString();
                    
                    let num = result.join('');
                    if (parseInt(num) % 7 === 0 && num[0] !== '0') {
                        break;
                    }
                }
            }
            
            if (n % 2 === 1) {
                for (let d = 9; d >= 0; d--) {
                    result[Math.floor(n / 2)] = d.toString();
                    let num = result.join('');
                    if (parseInt(num) % 7 === 0 && num[0] !== '0') {
                        return num;
                    }
                }
            } else {
                let num = result.join('');
                if (parseInt(num) % 7 === 0 && num[0] !== '0') {
                    return num;
                }
            }
        }
        
        // Backtrack approach
        result = new Array(n);
        
        function backtrack(pos) {
            if (pos > Math.floor(n / 2)) {
                let num = result.join('');
                return parseInt(num) % 7 === 0 && num[0] !== '0';
            }
            
            let start = (pos === 0) ? 9 : 9;
            for (let d = start; d >= 0; d--) {
                if (pos === 0 && d === 0) continue;
                
                result[pos] = d.toString();
                if (pos !== n - 1 - pos) {
                    result[n - 1 - pos] = d.toString();
                }
                
                if (backtrack(pos + 1)) {
                    return true;
                }
            }
            return false;
        }
        
        backtrack(0);
        return result.join('');
    }
    
    if (k === 8) {
        if (n === 1) return '8';
        if (n === 2) return '88';
        if (n === 3) return '888';
        if (n === 4) return '8888';
        if (n === 5) return '88888';
        if (n === 6) return '888888';
        return '888' + '9'.repeat(n - 6) + '888';
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(10^(n/2) × n)	最坏情况下需要尝试前半部分的所有可能组合，每次验证需要 O(n) 时间
空间复杂度	O(n)	存储结果字符串和递归栈空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目