题目描述
思路
暴力穷举
回溯剪枝
代码

leetcode - daily 526. 优美的排列

August 16, 2021

题目描述

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

第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
现在给定一个整数 N,请问可以构造多少个优美的排列?

示例1:

输入: 2
输出: 2
解释:

第 1 个优美的排列是 [1, 2]:
  第 1 个位置(i=1)上的数字是1,1能被 i(i=1)整除
  第 2 个位置(i=2)上的数字是2,2能被 i(i=2)整除

第 2 个优美的排列是 [2, 1]:
  第 1 个位置(i=1)上的数字是2,2能被 i(i=1)整除
  第 2 个位置(i=2)上的数字是1,i(i=2)能被 1 整除
说明:

N 是一个正整数,并且不会超过15。


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/beautiful-arrangement
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

暴力穷举

如果使用暴力穷举的方式,最多需要穷举 N 的全排列,对每个排列判断是否符合条件,时间复杂度为 $O(N!)$, 由于 N <= 15, 因此需要最多 15! = 1307674368000 次计算, 大概 1000 多亿次计算,不用看也知道超时了

回溯剪枝

由题意,对每个 i, 0 < i < N, 都需要满足二个条件之一

  1. i % nums[i] = 0
  2. nums[i] % i = 0

可以根据上述两个条件进行回溯剪枝

代码

/**
 * @param {number} N
 * @return {number}
 */
var countArrangement = function (N) {
  let count = 0,
    visited = Array.from({ length: N }).fill(false);

  dfs(0);

  return count;

  function dfs(cur) {
    if (cur >= N) {
      count++;
    }

    let next = cur + 1;

    for (let i = 1; i <= N; i++) {
      if (!visited[i] && judge(i, next)) {
        visited[i] = true;
        dfs(next);
        visited[i] = false;
      }
    }
  }

  function judge(x, y) {
    return x % y === 0 || y % x === 0;
  }
};
  • 时间复杂度: $O(N!)$
  • 空间复杂度: $O(N)$

feiker 少年起而行之