526.优美的排列

链接：526.优美的排列
难度：Medium
标签：位运算、数组、动态规划、回溯、状态压缩
简介：现在给定一个整数 N，请问可以构造多少个优美的排列？。

题解 1 - typescript

• 编辑时间：2021-08-16
• 执行用时：396ms
• 内存消耗：43.6MB
• 编程语言：typescript
• 解法介绍：深度遍历每个位置。

function countArrangement(n: number): number {
  let ans = 0;
  dfs();
  return ans;
  function dfs(list: number[] = [], set = new Set<number>()) {
    if (list.length === n) {
      ans++;
      return;
    }
    for (let i = 1; i <= n; i++) {
      if (!set.has(i) && (i % (list.length + 1) === 0 || (list.length + 1) % i === 0)) {
        set.add(i);
        list.push(i);
        dfs(list, set);
        list.pop();
        set.delete(i);
      }
    }
  }
}

题解 2 - typescript

• 编辑时间：2021-08-16
• 执行用时：148ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：深度遍历每个位置,利用二进制去重。

function countArrangement(n: number): number {
  let ans = 0;
  dfs();
  return ans;
  function dfs(list: number[] = [], mask = 0) {
    if (list.length === n) {
      ans++;
      return;
    }
    for (let i = 1; i <= n; i++) {
      if (
        (mask & (1 << (i - 1))) === 0 &&
        (i % (list.length + 1) === 0 || (list.length + 1) % i === 0)
      ) {
        mask |= 1 << (i - 1);
        list.push(i);
        dfs(list, mask);
        list.pop();
        mask &= ~(1 << (i - 1));
      }
    }
  }
}