2025-10-19：判断连接可整除性。用go语言，给出一个仅含正整数的数组 nums 和一个正整数 k。把 nums 中元素

福大大架构师每日一题

发布于 2025-12-18 14:40:43

130

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-10-19：判断连接可整除性。用go语言，给出一个仅含正整数的数组 nums 和一个正整数 k。

把 nums 中元素按某种顺序排列，然后把这些整数按顺序拼接成一个十进制字符串并看作一个大整数（例如 [12,3,45] 拼成 12345）。

如果这个大整数能被 k 整除，就称该排列是合法的。

要求在所有合法排列里选出按字典序（从左到右逐项比较）最小的那个，并以整数列表的形式返回；若没有任何合法排列，则返回空列表。

1 <= nums.length <= 13。

1 <= nums[i] <= 100000。

1 <= k <= 100。

输入: 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]。

题目来自力扣3533。

1. 程序步骤详解

1.1 排序

首先对 nums 进行升序排序。这是为了在 DFS 枚举时，按数字从小到大的顺序尝试，这样一旦找到解，就是字典序最小的解（因为 DFS 找到的第一个解是按数字从小到大的顺序构造的）。

1.2 预计算 `pow10`

对于每个数字 nums[i]，计算它作为字符串时的长度，然后计算 10^长度，存入 pow10[i]。例如 nums[i] = 45，长度是 2，pow10[i] = 100。这个数组的作用是：当我们把某个数字 nums[j] 拼接到当前数字 x 后面时，相当于 x * pow10[j] + nums[j]。

1.3 DFS + 记忆化搜索

• 状态 (s, x)：
- • s 是一个位掩码（bitmask），表示哪些数字已经被使用（1 表示已用，0 表示未用）。
- • x 是当前已拼接的数字对 k 取模的结果（避免大数运算）。
• 初始状态：s = (1<<n)-1（所有数字都未使用），x = 0。
• 目标状态：s = 0（所有数字都用完）且 x == 0（模 k 为 0，即整除）。

1.4 DFS 过程

1. 如果 s == 0，检查 x == 0，是则返回 true 表示找到解。
2. 如果 vis[s][x] 为 true，说明之前从这个状态出发没找到解，直接返回 false（避免重复搜索）。
3. 标记 vis[s][x] = true。
4. 枚举 s 中为 1 的位（即未使用的数字），按 nums 排序后的顺序（因为循环是从低位到高位，但 nums 已排序，所以先试小的数字）。
- • 移除该位 s' = s ^ (1<<i)
- • 新余数 x' = (x * pow10[i] + nums[i]) % k
- • 递归 dfs(s', x')
- • 如果返回 true，说明找到解，把 nums[i] 加入答案列表，并返回 true。
5. 如果所有枚举都不行，返回 false。

1.5 答案构建与反转

• 因为 DFS 找到解时，是从最后一个数字开始往前加入 ans 的（递归回溯时添加），所以最后需要反转 ans 才能得到正确的顺序。
• 如果 DFS 返回 false，返回 nil。

2. 示例 `nums = [3,12,45], k=5`

1. 排序后 nums = [3,12,45]
2. pow10 = [10, 100, 100]（因为 3 长度 1 → 10^1=10，12 长度 2 → 100，45 长度 2 → 100）
3. DFS 从 s=111b, x=0 开始，尝试：
- • 选 3：s=110b, x = (0*10+3)%5 = 3
  - • 选 12：s=100b, x = (3*100+12)%5 = 312%5 = 2
    - • 选 45：s=000b, x = (2*100+45)%5 = 245%5 = 0 ✅ 找到解
- • 回溯添加顺序：45 → 12 → 3
- • 反转后得到 [3,12,45]

3. 复杂度分析

3.1 时间复杂度

• 状态数：(1<<n) * k，即 2^n * k。
• 每个状态最多尝试 n 种转移。
• 所以时间复杂度为 O(2^n * n * k)。
• 这里 n ≤ 13，k ≤ 100，所以可行。

3.2 额外空间复杂度

• 记忆化数组 vis 大小：2^n * k，即 O(2^n * k)。
• pow10 数组：O(n)。
• DFS 递归栈深度：O(n)。
• 总额外空间复杂度：O(2^n * k)。

总结该算法通过状态压缩 DFS + 记忆化搜索，按排序顺序枚举排列，保证找到的第一个解就是字典序最小的合法排列。时间复杂度 O(2^n * n * k)，空间复杂度 O(2^n * k)。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
    "math/bits"
    "slices"
    "strconv"
)

func concatenatedDivisibility(nums []int, k int) []int {
    slices.Sort(nums)
    n := len(nums)
    pow10 := make([]int, n)
    for i, x := range nums {
        pow10[i] = int(math.Pow10(len(strconv.Itoa(x))))
    }

    ans := make([]int, 0, n)
    vis := make([][]bool, 1<<n)
    for i := range vis {
        vis[i] = make([]bool, k)
    }
    var dfs func(int, int) bool
    dfs = func(s, x int) bool {
        if s == 0 {
            return x == 0
        }
        if vis[s][x] {
            return false
        }
        vis[s][x] = true
        // 枚举在 s 中的下标 i
        for t := uint(s); t > 0; t &= t - 1 {
            i := bits.TrailingZeros(t)
            if dfs(s^1<<i, (x*pow10[i]+nums[i])%k) {
                ans = append(ans, nums[i])
                return true
            }
        }
        return false
    }
    if !dfs(1<<n-1, 0) {
        return nil
    }
    slices.Reverse(ans) // nums[i] 是倒序加入答案的，所以要反转
    return ans
}

func main() {
    nums := []int{3, 12, 45}
    k := 5
    result := concatenatedDivisibility(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from typing import List

def concatenatedDivisibility(nums: List[int], k: int) -> List[int]:
    nums.sort()
    n = len(nums)
    
    # 预计算每个数字的10的幂次
    pow10 = [10 ** len(str(x)) for x in nums]
    
    ans = []
    # 记忆化数组：vis[state][remainder]
    vis = [[False] * k for _ in range(1 << n)]
    
    def dfs(s: int, x: int) -> bool:
        if s == 0:
            return x == 0
        
        if vis[s][x]:
            return False
        
        vis[s][x] = True
        
        # 枚举在状态s中的每个数字
        for i in range(n):
            if s & (1 << i):
                if dfs(s ^ (1 << i), (x * pow10[i] + nums[i]) % k):
                    ans.append(nums[i])
                    return True
        
        return False
    
    if not dfs((1 << n) - 1, 0):
        return None
    
    # 由于是倒序加入答案的，需要反转
    ans.reverse()
    return ans

# 测试代码
if __name__ == "__main__":
    nums = [3, 12, 45]
    k = 5
    result = concatenatedDivisibility(nums, k)
    print(result)