leetcode 526. Beautiful Arrangement | 526. 优美的排列（回溯）

r囧r小猫 2022-09-12 10:50 268阅读 0赞

题目

https://leetcode.com/problems/beautiful-arrangement/
在这里插入图片描述

题解

首先分析，全排列一个一个试的话（如下图），时间复杂度O(n^2)，当n=15时，总共87178291200种情况，是肯定会超时的。
在这里插入图片描述

然后想想怎么剪枝。因为当一个位置的一个数字不可用时，后面也就没必要在尝试了。所以这种情况下，剪枝，不用继续往后走。递归如下。
递归函数中，i 是当前填写到的位置，seen 是已经用过的数字。

  1. class Solution { 
  2.     public int countArrangement(int n) { 
  3.         return process(n, 1, new HashSet<>());
  4.     }
  6.     public int process(int n, int i, Set<Integer> seen) { 
  7.         int count = 0;
  8.         if (i > n) return 1;
  9.         for (int j = 1; j <= n; j++) { 
  10.             if (!seen.contains(j) && (i % j == 0 || j % i == 0)) { 
  11.                 seen.add(j);
  12.                 count += process(n, i + 1, seen);
  13.                 seen.remove(j);
  14.             }
  15.         }
  16.         return count;
  17.     }
  18. }

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，268人围观）

还没有评论，来说两句吧...

相关阅读

    相关 526. 优美的排列

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

    我会带着你远行我会带着你远行/ 0 赞/ 260 阅读