Question

526. 优美的排列

English Version

题目描述

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

• 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

解法

方法一

class Solution:
  def countArrangement(self, n: int) -> int:
    def dfs(i):
      nonlocal ans, n
      if i == n + 1:
        ans += 1
        return
      for j in match[i]:
        if not vis[j]:
          vis[j] = True
          dfs(i + 1)
          vis[j] = False

    ans = 0
    vis = [False] * (n + 1)
    match = defaultdict(list)
    for i in range(1, n + 1):
      for j in range(1, n + 1):
        if j % i == 0 or i % j == 0:
          match[i].append(j)

    dfs(1)
    return ans

class Solution {
  private int n;
  private int ans;
  private boolean[] vis;
  private Map<Integer, List<Integer>> match;

  public int countArrangement(int n) {
    this.n = n;
    ans = 0;
    vis = new boolean[n + 1];
    match = new HashMap<>();
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (i % j == 0 || j % i == 0) {
          match.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
        }
      }
    }
    dfs(1);
    return ans;
  }

  private void dfs(int i) {
    if (i == n + 1) {
      ++ans;
      return;
    }
    if (!match.containsKey(i)) {
      return;
    }
    for (int j : match.get(i)) {
      if (!vis[j]) {
        vis[j] = true;
        dfs(i + 1);
        vis[j] = false;
      }
    }
  }
}

class Solution {
public:
  int n;
  int ans;
  vector<bool> vis;
  unordered_map<int, vector<int>> match;

  int countArrangement(int n) {
    this->n = n;
    this->ans = 0;
    vis.resize(n + 1);
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (i % j == 0 || j % i == 0)
          match[i].push_back(j);
    dfs(1);
    return ans;
  }

  void dfs(int i) {
    if (i == n + 1) {
      ++ans;
      return;
    }
    for (int j : match[i]) {
      if (!vis[j]) {
        vis[j] = true;
        dfs(i + 1);
        vis[j] = false;
      }
    }
  }
};

func countArrangement(n int) int {
  ans := 0
  match := make(map[int][]int)
  for i := 1; i <= n; i++ {
    for j := 1; j <= n; j++ {
      if i%j == 0 || j%i == 0 {
        match[i] = append(match[i], j)
      }
    }
  }
  vis := make([]bool, n+1)

  var dfs func(i int)
  dfs = func(i int) {
    if i == n+1 {
      ans++
      return
    }
    for _, j := range match[i] {
      if !vis[j] {
        vis[j] = true
        dfs(i + 1)
        vis[j] = false
      }
    }
  }

  dfs(1)
  return ans
}

function countArrangement(n: number): number {
  const vis = new Array(n + 1).fill(0);
  const match = Array.from({ length: n + 1 }, () => []);
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      if (i % j === 0 || j % i === 0) {
        match[i].push(j);
      }
    }
  }

  let res = 0;
  const dfs = (i: number, n: number) => {
    if (i === n + 1) {
      res++;
      return;
    }
    for (const j of match[i]) {
      if (!vis[j]) {
        vis[j] = true;
        dfs(i + 1, n);
        vis[j] = false;
      }
    }
  };
  dfs(1, n);
  return res;
}

impl Solution {
  fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) {
    if i == n + 1 {
      *res += 1;
      return;
    }
    for &j in mat[i].iter() {
      if !vis[j] {
        vis[j] = true;
        Self::dfs(i + 1, n, mat, vis, res);
        vis[j] = false;
      }
    }
  }

  pub fn count_arrangement(n: i32) -> i32 {
    let n = n as usize;
    let mut vis = vec![false; n + 1];
    let mut mat = vec![Vec::new(); n + 1];
    for i in 1..=n {
      for j in 1..=n {
        if i % j == 0 || j % i == 0 {
          mat[i].push(j);
        }
      }
    }

    let mut res = 0;
    Self::dfs(1, n, &mat, &mut vis, &mut res);
    res
  }
}

方法二

class Solution {
  public int countArrangement(int N) {
    int maxn = 1 << N;
    int[] f = new int[maxn];
    f[0] = 1;
    for (int i = 0; i < maxn; ++i) {
      int s = 1;
      for (int j = 0; j < N; ++j) {
        s += (i >> j) & 1;
      }
      for (int j = 1; j <= N; ++j) {
        if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
          f[i | (1 << (j - 1))] += f[i];
        }
      }
    }
    return f[maxn - 1];
  }
}