Medium

题目描述

假设有从 1 到 n 的 n 个整数。如果从这 n 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= n) 满足如下两个条件中的其中一个，我们就称这个数组为一个优美的排列：

  • perm[i] 能够被 i 整除
  • i 能够被 perm[i] 整除

给定一个整数 n，返回可以构造的优美的排列的数量。

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能够被 i = 1 整除
    - perm[2] = 2 能够被 i = 2 整除
第 2 个优美的排列是 [2,1]：
    - perm[1] = 2 能够被 i = 1 整除
    - i = 2 能够被 perm[2] = 1 整除

示例 2：

输入：n = 1
输出：1

提示：

  • 1 <= n <= 15

解题思路

本题需要找到所有满足条件的排列数量，典型的回溯问题。有以下几种解法：

1. 回溯法 最直观的思路是使用回溯法枚举所有可能的排列。对于每个位置 i，尝试放入每个未使用的数字 num，如果满足条件（num % i == 0 或 i % num == 0），则继续递归。

2. 状态压缩动态规划（推荐） 由于 n 最大为 15，可以使用位掩码来表示已使用的数字集合。定义 dp[mask] 表示使用 mask 表示的数字集合能够构成的优美排列数量。状态转移时，枚举下一个可以放置的数字。

3. 优化回溯 在回溯过程中，可以预处理每个位置可以放置的数字，减少不必要的尝试。

由于 n 较小，状态压缩 DP 在时间复杂度上更优，且代码相对简洁。通过位运算快速判断数字是否已使用，避免了额外的 visited 数组。

代码实现

class Solution {
public:
    int countArrangement(int n) {
        vector<int> dp(1 << n, 0);
        dp[0] = 1;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == 0) continue;
            
            int pos = __builtin_popcount(mask) + 1;
            if (pos > n) continue;
            
            for (int i = 1; i <= n; i++) {
                if (mask & (1 << (i - 1))) continue;
                if (i % pos == 0 || pos % i == 0) {
                    dp[mask | (1 << (i - 1))] += dp[mask];
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def countArrangement(self, n: int) -> int:
        dp = [0] * (1 << n)
        dp[0] = 1
        
        for mask in range(1 << n):
            if dp[mask] == 0:
                continue
            
            pos = bin(mask).count('1') + 1
            if pos > n:
                continue
            
            for i in range(1, n + 1):
                if mask & (1 << (i - 1)):
                    continue
                if i % pos == 0 or pos % i == 0:
                    dp[mask | (1 << (i - 1))] += dp[mask]
        
        return dp[(1 << n) - 1]

public class Solution {
    public int CountArrangement(int n) {
        int[] dp = new int[1 << n];
        dp[0] = 1;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == 0) continue;
            
            int pos = System.Numerics.BitOperations.PopCount((uint)mask) + 1;
            if (pos > n) continue;
            
            for (int i = 1; i <= n; i++) {
                if ((mask & (1 << (i - 1))) != 0) continue;
                if (i % pos == 0 || pos % i == 0) {
                    dp[mask | (1 << (i - 1))] += dp[mask];
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

var countArrangement = function(n) {
    const dp = new Array(1 << n).fill(0);
    dp[0] = 1;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
状态压缩DPO(n × 2^n)O(2^n)

相关题目