LeetCode 题解工作台
判断连接可整除性
给你一个正整数数组 nums 和一个正整数 k 。 当 nums 的一个 排列 中的所有数字，按照排列顺序 连接其十进制表示 后形成的数可以 被 k 整除时，我们称该排列形成了一个 可整除连接 。 返回能够形成 可整除连接 且 字典序 最小 的排列（按整数列表的形式表示）。如果不存在这样的排列，返回…
4
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个正整数数组 nums 和一个正整数 k。
当 nums 的一个 排列 中的所有数字，按照排列顺序 连接其十进制表示 后形成的数可以 被 k 整除时，我们称该排列形成了一个 可整除连接 。
返回能够形成 可整除连接 且 字典序 最小 的排列（按整数列表的形式表示）。如果不存在这样的排列，返回一个空列表。
示例 1：
输入: nums = [3,12,45], k = 5
输出: [3,12,45]
解释:
| 排列 | 连接后的值 | 是否能被 5 整除 |
|---|---|---|
| [3, 12, 45] | 31245 | 是 |
| [3, 45, 12] | 34512 | 否 |
| [12, 3, 45] | 12345 | 是 |
| [12, 45, 3] | 12453 | 否 |
| [45, 3, 12] | 45312 | 否 |
| [45, 12, 3] | 45123 | 否 |
可以形成可整除连接且字典序最小的排列是 [3,12,45]。
示例 2：
输入: nums = [10,5], k = 10
输出: [5,10]
解释:
| 排列 | 连接后的值 | 是否能被 10 整除 |
|---|---|---|
| [5, 10] | 510 | 是 |
| [10, 5] | 105 | 否 |
可以形成可整除连接且字典序最小的排列是 [5,10]。
示例 3：
输入: nums = [1,2,3], k = 5
输出: []
解释:
由于不存在任何可以形成有效可整除连接的排列，因此返回空列表。
提示：
1 <= nums.length <= 131 <= nums[i] <= 1051 <= k <= 100
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * 2^n * k) due to iterating over all subsets of numbers with DP and computing remainders. Space complexity is O(2^n * k) for memoization of all state transitions. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if recursive DP with bitmasking can cover all permutations efficiently.
- question_mark
Questions how remainder modulo k is updated when concatenating numbers.
- question_mark
Checks if lexicographical order is preserved during state transitions.
常见陷阱
外企场景- error
Failing to precompute modular powers, causing slow remainder calculations.
- error
Not memoizing DP states, leading to exponential runtime.
- error
Ignoring lexicographical order and returning a valid but non-minimal permutation.
进阶变体
外企场景- arrow_right_alt
Return the count of all valid permutations forming divisible concatenations instead of one sequence.
- arrow_right_alt
Allow repeated numbers in nums and find the smallest concatenation divisible by k.
- arrow_right_alt
Change k to a large prime and analyze how bitmask DP scales with modulo operations.