BeautifulArrangement [source code]
public class BeautifulArrangement {
static
/******************************************************************************/
public class Solution {
private int count = 0;
public int countArrangement(int N) {
boolean[] visited = new boolean[N + 1];
boolean[][] table = new boolean[N + 1][N + 1];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (i % j == 0 || j % i == 0) {
table[i][j] = true;
}
helper(N, N, visited, table);
return count;
}
public void helper(int N, int pos, boolean[] visited, boolean[][] table) {
if (pos < 1) {
count++;
return;
}
for (int i = 1; i <= N; i++) {
if (!visited[i] && table[pos][i]) {
visited[i] = true;
helper(N, pos - 1, visited, table);
visited[i] = false;
}
}
}
}
/******************************************************************************/
public static void main(String[] args) {
int[] inputs = {
2, 2,
4, 8,
10, 700,
};
for (int i = 0; i < inputs.length / 2; i++) {
BeautifulArrangement.Solution tester = new BeautifulArrangement.Solution();
int N = inputs[2 * i];
int expected = inputs[1 + 2 * i];
System.out.println(Printer.seperator());
int output = tester.countArrangement(N);
System.out.println(Printer.wrapColor(N, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, expected == output ? "green" : "red"));
}
}
}
又是一个完全没有思路的题目. 即使提示了backtracking, 依然是不知道怎么做: 在这种non graph的context下的DFS还是没有写过;
而且我现在比较困惑的一个问题是, 到底什么样的问题可以说给我们一个信息, 可以用backtrack了? 因为backtrack本身其实是一把屠龙刀, 很多时候属于一个overkill. 比如之前我刚做完的PalindromicSubstrings这个问题, 就没有用backtrack来做. 但是你仔细想想, 那个问题也是一个generate&test的问题啊? 为什么那个问题最后就不适合backtrack呢?
目前稍微总结一下, 感觉真正触发你思考backtrack的动机应该是, existence of many decision points/variables. 比如这个题目, 每个位置到底放什么数字, 你是无法决定的;
那么为什么前面的PalindromicSubstrings, 或者LongestPalindromicSubstring不需要用backtrack? 因为这些问题你仔细想想, 实际上是没有多少个decision points的; 这种问题你强行用backtrack做估计也能做, 但是没有必要, 出题目给你的人的本意肯定不是让你用backtrack来穷搜.
这个是editorial1, 虽然超时了:
public class Solution {
int count = 0;
public int countArrangement(int N) {
int[] nums = new int[N];
for (int i = 1; i <= N; i++)
nums[i - 1] = i;
permute(nums, 0);
return count;
}
public void permute(int[] nums, int l) {
if (l == nums.length - 1) {
int i;
for (i = 1; i <= nums.length; i++) {
if (nums[i - 1] % i != 0 && i % nums[i - 1] != 0)
break;
}
if (i == nums.length + 1) {
count++;
}
}
for (int i = l; i < nums.length; i++) {
swap(nums, i, l);
permute(nums, l + 1);
swap(nums, i, l);
}
}
public void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}
但是这个算法完成了一个generate all permutations的任务. 这个过程其实也是一个backtrack的过程(不信你可以看他实际完成的过程就是用recursion完成的);
另外这里的count同样是用一个increment global count的思路来完成的, 这个跟PalindromicSubstrings的最优解的思路是一样的;
也许这个思路广泛适合于generate&test类的count问题?
这个算法的复杂度是N!, 这个是介于2^N和N^N之间的;
Then, it swaps the current element with every other element in the array, lying towards its right, so as to generate a new ordering of the array elements. After the swapping has been done, it makes another call to permute but this time with the index of the next element in the array. While returning back, we reverse the swapping done in the current function call.
这个就是为什么有最后一个swap recursive call的原因; 这个算法其实并不是一个trivial的算法, 其实是一个有一定recursion, 或者DP性质的一个算法: 如果你先是有长度为N的所有的permutation了(Bottom-Up的方式来思考), 那么你怎么得到N+1长度的所有permutation(like how you do any DP value generation/updating)? 实际的思路就是, decide on which of the total of N+1 elements sit on the posiiton[N] (the new end position, 不过这里这个算法的时候, 这个decision position实际上用的是最左边的position, 一样的意思). 这个swap就是完成了这样一个操作, 每一个被swap出来的element就坐在最左边, 然后剩下的N个在右边使劲折腾;
另外, 这个backtrack用的一个模式是: DFS本身是void的返回值, 然后一个global(或者多个)在traverse的过程中被更新. 这个好像是不少DFS常用的方式. 也许这个方式在backtrack的问题当中更加常见;
很奇怪的是editorial里面并不认为这个算法属于backtrack. 也许是我们这个backtracking只是在generate permutation的过程中使用, 并不是在解决问题的主要算法当中使用的;
另外注意他这里leaf condition的判断, 在leaf位置直接就进行divisibility的判断;
editorial2对此进行了优化:
In the brute force approach, we create the full array for every permutation and then check the array for the given divisibilty conditions. But this method can be optimized to a great extent. To do so, we can keep checking the elements while being added to the permutation array at every step for the divisibility condition and can stop creating it any further as soon as we find out the element just added to the permutation violates the divisiblity condition.
public class Solution {
int count = 0;
public int countArrangement(int N) {
int[] nums = new int[N];
for (int i = 1; i <= N; i++)
nums[i - 1] = i;
permute(nums, 0);
return count;
}
public void permute(int[] nums, int l) {
if (l == nums.length) {
count++;
}
for (int i = l; i < nums.length; i++) {
swap(nums, i, l);
if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0)
permute(nums, l + 1);
swap(nums, i, l);
}
}
public void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}
这个就相当于一个premature exit的操作, 或者说是剪枝. 只有当满足一定的条件才继续向下recurse, 来大幅度的减少实际的搜索空间; 这个也是425上面讲过的技巧;
剪枝也是backtracking/DFS常见的一种优化技巧了, 之前知乎上看到, 面试的时候有直接在Follow-Up里面问这个的;
只能说Google的题目, 真的是难的可以;
这个是editorial3, 也就是editorial最优解:
public class Solution {
int count = 0;
public int countArrangement(int N) {
boolean[] visited = new boolean[N + 1];
calculate(N, 1, visited);
return count;
}
public void calculate(int N, int pos, boolean[] visited) {
if (pos > N) {
count++;
return;
}
for (int i = 1; i <= N; i++) {
if (!visited[i] && (pos % i == 0 || i % pos == 0)) {
visited[i] = true;
calculate(N, pos + 1, visited);
visited[i] = false;
}
}
}
}
The idea behind this approach is simple. We try to create all the permutations of numbers from 1 to N. We can fix one number at a particular position and check for the divisibility criteria of that number at the particular position. But, we need to keep a track of the numbers which have already been considered earlier so that they aren't reconsidered while generating the permutations. If the current number doesn't satisfy the divisibility criteria, we can leave all the permutations that can be generated with that number at the particular position. This helps to prune the search space of the permutations to a great extent. We do so by trying to place each of the numbers at each position.
看这个的介绍, 好像就是直接用backtracking把原来的问题翻译过来的而已: each dicision is: pick a number for this position, position from left to right; 这个就是我们当初类似DPLL的时候的算法;
加上这个visited, 实际上完全就是DPLL那个实现的方式? 这个array其实代表的是一个空的盒子, 用来记录你的decision level;
严格来说好像不是decision level这么简单; visited[i] denotes the fact that ith number is already decided on this subtree.
这个在editorial文章上面有一个很好的动画, 动画上面显示出来的结果就是可以看出来, pos跟i的作用其实是类似的, 都是一个fanning index, 区别在于pos是属于root level的fanning index, 这个fanning index的特殊之处, 也就在于可以用来判断最后的中止条件: root level的fanning结束之后, 就是整个recursion结束的时候, 也就是相当于这个root level fanning用来座位了base case(editorial本来的代码这里还不是base case, 也就是这个if里面居然还是没有return的. 我加了之后照样AC, 而且快了不少, 不过仍然是最慢的一个最优解);
仔细想了一下, 其实这里的这个方法其实是一个针对permutation问题定制化出来的backtracking. 这里的这个boolean array所代表的严格的来说是whether the number has already been placed, 而不是whether the ith position is already filled. 至于position, 其实就是pos这个argument的作用. 我们说过, 看recursion的时候, 一个重要的技巧就是看参数, 尤其是recursive call的时候参数如何变化; 这里的N肯定是没有变化的, 就是一个传递下去的信息; 这个array是一个类似accum的作用, mutable, 而且在推出recursive call的时候还有undo的操作; 至于这个pos, 我们观察它的变化, 就是每下一个level就+1, 这个就类似一个depth的tag;
在backtracking问题, 其实就是用DFS来解决实际的一个搜索问题; 这个跟普通 graph问题不同的一点在于, 在graph问题里面, 每一个node是什么意思都是有一个explicit的定义的; 但是在这样一个实际问题里面, 一个node其实本身是没有任何的actual entity的; 当然我们说了, 既然说它是一个node, 这个node自然要有自己的entity. 在graph问题里面这个entity往往就是通过attribute来表示; 而在这种implicit的DFS/recursion问题里面, 这个node的identity, 或者说的data, 其实就是传给这个call的参数;
所以这个题目里面, pos跟i其实不完全是一样的; pos是the currrent position we want to fill, i则代表which value to consider; at each pos, we consider all i, but only move on (downward) if this i has not yet been used (in other previous positions) and also satisfies the beautiful requirement.
自己visual一下这个tree, 每一个depth其实就是对应一个pos, 从左到右. 当depth超过N的时候, 就是成功结束的时候. 如果在某一个不到N的pos, 我们循环走完了都没有合适的i, 那么就直接上行返回, 这一条path就被放弃了;
一个比较奇怪的事情是, 这个editorial3其实是几个最优解里面最慢的一个, 甚至比editorial2还要慢一倍(两个算法实际上的复杂度都是O(number of valid permutations)).
这个是discussion里面一个关于backtracking的模板:
I would say Practice Makes Perfect.
A general recursive template for backtracking may look like this:
helper (parameters of given data and current recursive level) {
// Handle base cases, i.e. the last level of recursive call
if (level == lastLevel) {
record result;
return sth;
}
// Otherwise permute every possible value for this level.
for (every possible value for this level) {
helper(parameters of given data and next recursive level);
}
return sth;
}
2 points to add to @shawngao's answer -
- In Leetcode, there are many backTrack problems, some of which are good starting points.
Combination Sum, Factor Combinations, Permutations, Permutations II.
More advanced: Evaluate Division, Word Pattern II, Remove Invalid Parentheses, Basic Calculator - When solving a BT problem, pay attention to whether it's a Permutation problem, or a Combination.
The problem here is a permutation.
无论是用什么大的思路, 有一个优化就是从右边开始往左边搜更快, 因为在end的位置, 可以合格的i其实更少. 这个也是符合425的时候学到的东西: most constrained first. 当时学的时候一个教训, 就是如果valid value 在整个domain的占比越低, 那么就more constrianed. 在更高的level砍掉的branching factor更加能够减少整个搜索空间;
You can make it a bit faster by stopping the recursion at k < 2 instead of at k == 0. No need to check whether position 1 can hold the last remaining number. It always can.
这个是另外一个小的优化;
这个是submission的最优解: 7(96):
public class Solution {
public int countArrangement(int N) {
int[] nums = new int[N];
for(int i = 0; i < N; i++)
nums[i] = i + 1;
return helper(N, nums);
}
public int helper(int n, int[] nums){
if(n <= 0){
return 1;
}
int res = 0;
for(int i = 0; i < n; i++){
if(nums[i] % n == 0 || n % nums[i] == 0){
int tmp = nums [i];
nums[i] = nums[n-1];
nums[n-1] = tmp;
res += helper(n-1, nums);
nums[n-1] = nums[i];
nums[i] = tmp;
}
}
return res;
}
}
这个里面是加了一个end to start的优化的; 这里的argument里面的n同样是一个pos的意思: 在each iteration(recursive level, which corresponds to a position to fill), iterate through all possible values. 这个其实原理跟那个permutation-based backtracking是一样的, 不过这里是没有用global了; 不过在这种找leaf的问题当中, 其实count本身也很好做. 只有leaf才能产生1, 那么每一个node都直接讲recurse上来的返回值相加, 就是所有found leaf的数量了;
这个是另外一个: 6(98):
public class Solution {
private int count = 0;
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void helper(int[] nums, int start) {
if (start == 0) {
count++;
return;
}
for (int i = start; i > 0; i--) {
swap(nums, start, i);
if (nums[start] % start == 0 || start % nums[start] == 0) helper(nums, start-1);
swap(nums,i, start);
}
}
public int countArrangement(int N) {
if (N == 0) return 0;
int[] nums = new int[N+1];
for (int i = 0; i <= N; i++) nums[i] = i;
helper(nums, N);
return count;
}
}
这个就是一个很直接的permutation-based backtracking, 加上一个倒序的优化;
这个问题的两个approach说到底, 其实就是对于permutation问题的两种不同是实现思路:
- 给你一个sorted的order, 然后你通过swap out的思路来逐次决定每个位置上的element;
- 给你一个完全Empty的order, 然后你一个一个的pick and fill.
无论是哪一种approach, 站在backtracking的方式上思考问题的时候, 一个首先亟待解决的问题就是, 你怎么选择decision level这个概念; 这里的这两个approach的decision level其实都是position.
这个decision level一般都是体现在recursion的参数里面的: 专门有一个参数来记录当前这个call/node对应的decision level(正好也是tree里面的depth).
discussion还有一个稍微奇葩一点的最优解: https://discuss.leetcode.com/topic/80027/beat-100-so-far-java-simple-solution/7
public class Solution {
Map<Integer, Integer> map = new HashMap();
public int countArrangement(int N) {
List<Integer>[] arr = new List[N + 1]; // idx : possible vals
// construct all possible choices
for (int i = 1; i <= N; i++) {
arr[i] = new ArrayList();
for (int j = 1; j <= N; j++) {
if (i % j == 0 || j % i == 0) {
arr[i].add(j);
}
}
}
return helper(arr, 1, 0);
}
private int helper(List<Integer>[] arr, int i, int vis) {
if (map.containsKey(vis)) return map.get(vis);
if (i == arr.length) return 1;
int count = 0;
for (int v : arr[i]) {
if ((vis >> v & 1) == 1) continue;
count += helper(arr, i + 1, vis ^ (1 << v));
}
map.put(vis, count);
return count;
}
}
Below is Stefan's optimized code. Really impressive.
I optimized it a bit further, using arrays, going downwards, and precalculating the shifts.
public class Solution {
int[] map = new int[1 << 15];
public int countArrangement(int N) {
int[][] arr = new int[N + 1][]; // idx : possible vals
// construct all possible choices
for (int i = 1; i <= N; i++) {
List<Integer> tmp = new ArrayList();
for (int j = 1; j <= N; j++) {
if (i % j == 0 || j % i == 0) {
tmp.add(1 << (j-1));
}
}
arr[i] = new int[tmp.size()];
for (int k = 0; k < arr[i].length; k++)
arr[i][k] = tmp.get(k);
}
Arrays.fill(map, 0, 1 << N, -1);
return helper(arr, N, 0);
}
private int helper(int[][] arr, int i, int vis) {
if (map[vis] >= 0) return map[vis];
if (i == 1) return 1;
int count = 0;
for (int v : arr[i])
if ((vis & v) == 0)
count += helper(arr, i - 1, vis ^ v);
map[vis] = count;
return count;
}
}
大概意思好像就是避免重复的进行mod操作, 所以直接先建一个表, 对于每一个i(无论是index还是value), 把所有和它compatible的value全都存储起来; 然后实际recurse的时候, 只要查表就行了; 这个算法最后的速度是5(99).
这个技巧严格来说就是把memoization应用到recursion上面的一个加速优化而已;
不过这个算法的细节还是有点不太懂, 尤其是这个bit manipulation到底是什么原理. 帖子里留了一个问题, 暂时不在这个上面浪费时间了;
大概把这些算法全都看完了之后尝试自己写一个版本, 主要是用backtracking的版本, 加入倒序优化, 同时加入查表优化(避免多次的mod). 就是上面这个版本;
注意他们这里的table和visited, 初始化的时候给的size, 全都是比N大1, 这个就是因为这个问题上面要反复的进行index和value之间的转换, 所以我们把这些array的size搞大1, 避免反复的进行+1/-1的转换;
另外一个需要考虑的问题: 上面所说的这个倒序优化, 其实是属于variable ordering的范畴. 那么value ordering我们应该怎么决定呢? 好像没什么区别? 不对, 应该有区别, 我们都有visited, 这个东西就是用来记录value ordering的;
value ordering的一个选择的思路就是, 无论是success or fail, 都要return fast. 所以我认为这里的value ordering其实还是应该从小到大, 因为在大index的位置把小的value消耗掉了之后, 就更有可能让下面的(左边的index)更快的fail: 小的value的compatibility整体更高;
所以introducing devices to record variable ordering and value ordering也许可以说是backtracking问题的一个思考上的主基调?
找时间是要把Constraint Processing这本书看一下, 把425课上的核心内容再复习一遍;
自己实现的时候还发生了一个小插曲: 因为这个算法是依赖instance variable的, 所以在我的main的test里面, 我因为我的tester是在test的循环外面new出来的, 所以这个instance var必须针对每一个input重新初始化为0一遍.
当然解决的办法就是把new tester的过程放到循环里面就行了;
最后的速度是10ms (93%), 完全没有我想象中的快; 不过这个题目也差不多就这样了;
Problem Description
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ? i ? N) in this array:
The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
N is a positive integer and will not exceed 15.
Difficulty:Medium
Total Accepted:11.5K
Total Submissions:20.8K
Contributor: CDY_好きだ
Companies
google
Related Topics
backtracking