Hard
题目描述
给你一个正整数数组 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
输出：[]
解释：
由于 nums 的任何排列都不能形成有效的可整除串联，返回空列表。
提示：
1 <= nums.length <= 131 <= nums[i] <= 10^51 <= k <= 100
解题思路
这是一个典型的状态压缩动态规划问题。由于需要找到字典序最小的排列，我们可以使用位掩码DP来解决。
核心思路：
状态定义：
dp[mask][remainder]表示使用了mask对应的数字集合，当前串联数对k的余数为remainder时是否可能。状态转移：对于每个状态，尝试添加一个未使用的数字。假设当前余数为
r，要添加数字num，新的余数为(r * 10^(num的位数) + num) % k。字典序最小：为了确保字典序最小，我们在状态转移时按照数字大小顺序进行尝试，并记录每个状态的前驱，用于最后重构答案。
优化技巧：
- 预计算每个数字的10的幂次模k的值
- 使用位掩码表示已使用的数字集合
- 通过前驱指针重构路径
算法步骤：
- 预处理：计算每个数字对应的10的幂次模k
- 初始化：
dp[0][0] = true - 状态转移：枚举所有可能的mask和remainder，尝试添加新数字
- 答案重构：从目标状态开始，通过前驱指针回溯构建答案
代码实现
class Solution {
public:
vector<int> concatenatedDivisibility(vector<int>& nums, int k) {
int n = nums.size();
vector<int> power(n);
// 预计算每个数字对应的10的幂次模k
for (int i = 0; i < n; i++) {
int len = to_string(nums[i]).length();
power[i] = 1;
for (int j = 0; j < len; j++) {
power[i] = (power[i] * 10) % k;
}
}
// dp[mask][remainder] = 是否可能
vector<vector<bool>> dp(1 << n, vector<bool>(k, false));
// 记录前驱状态用于重构答案
vector<vector<pair<int, int>>> parent(1 << n, vector<pair<int, int>>(k, {-1, -1}));
dp[0][0] = true;
for (int mask = 0; mask < (1 << n); mask++) {
for (int rem = 0; rem < k; rem++) {
if (!dp[mask][rem]) continue;
// 尝试添加每个未使用的数字
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
int newMask = mask | (1 << i);
int newRem = (rem * power[i] + nums[i] % k) % k;
if (!dp[newMask][newRem]) {
dp[newMask][newRem] = true;
parent[newMask][newRem] = {mask, rem};
}
}
}
}
// 检查是否有解
if (!dp[(1 << n) - 1][0]) {
return {};
}
// 重构答案
vector<int> result;
int mask = (1 << n) - 1;
int rem = 0;
while (mask != 0) {
auto [prevMask, prevRem] = parent[mask][rem];
int used = mask ^ prevMask;
int idx = __builtin_ctz(used); // 找到使用的位
result.push_back(nums[idx]);
mask = prevMask;
rem = prevRem;
}
reverse(result.begin(), result.end());
return result;
}
};
class Solution:
def concatenatedDivisibility(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
# 预计算每个数字对应的10的幂次模k
power = []
for num in nums:
length = len(str(num))
p = 1
for _ in range(length):
p = (p * 10) % k
power.append(p)
# dp[mask][remainder] = 是否可能
dp = [[False] * k for _ in range(1 << n)]
# 记录前驱状态用于重构答案
parent = [[(-1, -1)] * k for _ in range(1 << n)]
dp[0][0] = True
for mask in range(1 << n):
for rem in range(k):
if not dp[mask][rem]:
continue
# 尝试添加每个未使用的数字
for i in range(n):
if mask & (1 << i):
continue
new_mask = mask | (1 << i)
new_rem = (rem * power[i] + nums[i] % k) % k
if not dp[new_mask][new_rem]:
dp[new_mask][new_rem] = True
parent[new_mask][new_rem] = (mask, rem)
# 检查是否有解
if not dp[(1 << n) - 1][0]:
return []
# 重构答案
result = []
mask = (1 << n) - 1
rem = 0
while mask != 0:
prev_mask, prev_rem = parent[mask][rem]
used = mask ^ prev_mask
idx = used.bit_length() - 1 # 找到使用的位
result.append(nums[idx])
mask = prev_mask
rem = prev_rem
result.reverse()
return result
public class Solution {
public int[] ConcatenatedDivisibility(int[] nums, int k) {
int n = nums.Length;
int[] power = new int[n];
// 预计算每个数字对应的10的幂次模k
for (int i = 0; i < n; i++) {
int length = nums[i].ToString().Length;
power[i] = 1;
for (int j = 0; j < length; j++) {
power[i] = (power[i] * 10) % k;
}
}
// dp[mask][remainder] = 是否可能
bool[,] dp = new bool[1 << n, k];
// 记录前驱状态用于重构答案
(int, int)[,] parent = new (int, int)[1 << n, k];
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < k; j++) {
parent[i, j] = (-1, -1);
}
}
dp[0, 0] = true;
for (int mask = 0; mask < (1 << n); mask++) {
for (int rem = 0; rem < k; rem++) {
if (!dp[mask, rem]) continue;
// 尝试添加每个未使用的数字
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue;
int newMask = mask | (1 << i);
int newRem = (rem * power[i] + nums[i] % k) % k;
if (!dp[newMask, newRem]) {
dp[newMask, newRem] = true;
parent[newMask, newRem] = (mask, rem);
}
}
}
}
// 检查是否有解
if (!dp[(1 << n) - 1, 0]) {
return new int[0];
}
// 重构答案
List<int> result = new List<int>();
int currentMask = (1 << n) - 1;
int currentRem = 0;
while (currentMask != 0) {
var (prevMask, prevRem) = parent[currentMask, currentRem];
int used = currentMask ^ prevMask;
int idx = 0;
while ((used & (1 << idx)) == 0) idx++;
result.Add(nums[idx]);
currentMask = prevMask;
currentRem = prevRem;
}
result.Reverse();
return result.ToArray();
}
}
var concatenatedDivisibility = function(nums, k) {
const n = nums.length;
const memo = new Map();
function getLength(num) {
return num.toString().length;
}
function powerMod(base, exp, mod) {
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp = Math.floor(exp / 2);
base = (base * base) % mod;
}
return result;
}
function dfs(mask, remainder) {
if (mask === (1 << n) - 1) {
return remainder === 0 ? [] : null;
}
const key = `${mask},${remainder}`;
if (memo.has(key)) {
return memo.get(key);
}
let result = null;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
const newRemainder = (remainder * powerMod(10, getLength(nums[i]), k) + nums[i]) % k;
const subResult = dfs(mask | (1 << i), newRemainder);
if (subResult !== null) {
const candidate = [nums[i], ...subResult];
if (result === null || candidate < result) {
result = candidate;
}
}
}
memo.set(key, result);
return result;
}
const answer = dfs(0, 0);
return answer === null ? [] : answer;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(2^n × k × n) |
| 空间复杂度 | O(2^n × k) |
其中 n 是数组长度，k 是给定的整数。状态数为 2^n × k，每个状态需要尝试 n 个数字的转移。