甲乙小朋友的房子

甲乙小朋友很笨,但甲乙小朋友不会放弃

0%

算法-回溯法

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

八皇后问题

在棋盘上放置8个皇后,使得它们互不攻击,此时每个皇后的攻击范围为同行同列和同 对角线,要求找出所有解,如图7-4所示。

暴力思路:

64选8,有\(C_{64}^8\)种方案。

优化:

因为恰好每行每列各放置一个皇后,那就是一个全排列问题。而0~7的排列一共只有\(8! = 40320\)个。如果枚举的话,也没多少个。

为了方便分析,我们先把问题简化为4皇后问题。

假如皇后现在的位置是(0,2.*,*)

即:

1
2
3
4
1 * * *
* * 1 *
* * * *
* * * *

此时后面两个皇后无论放哪里,都会和前两行的皇后冲突。此时,递归函数将不再递归调用它自身,而是返回上一层。这个就叫回溯。

我们画出四皇后的解答树(每个元素代表第i个皇后放在第j列):

因此,八皇后问题可以这么写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int counter = 0;
int[] C = new int[8]; // C[i]表示第i行的皇后放在了C[i]列
void search(int cur){
if(cur == n){ // n个皇后都不冲突
++counter;
return;
}
for(int i = 0; i < n; ++i){
int ok = 1;
// 尝试把第cur行的皇后放在第i列
C[cur] = i;
// 检查是否和前面皇后冲突
for(int j = 0; j < cur; ++j){
if(C[cur] == C[j]||
cur - C[cur] == j - C[j]||
CUR + C[cur] == j + C[j]){
ok = 0;
break; // 如果冲突,就不再继续搜索
}
if(ok) search(cur + 1);
}
}
}

进一步优化:

骚操作:用二维数组vis[3][]判断当前尝试的皇后是否与其他皇后冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
先看看这个:

0 1 2 3
0 1 * * *
1 * 1 * *
2 * * 1 *
3 * * * 1

我们看看标1的对角线上的i和j有什么关系:

这个对角线i == j

我们看下一个对角线:


0 1 2 3
0 * 1 * *
1 * * 1 *
2 * * * 1
3 * * * *

这个对角线 i == j + 1

其实,这个方向的对角线,只要在一个对角线上,那么 i - j 就是一个定值

那么:

vis[0][i] :第i列是否已有皇后;
vis[1][j + i] : 第j行i列对应的对角线是否已经有皇后(因为同一个对角线上的i + j都是相等的)
vis[2][j - i + n] : 第j行i列对角线是否已经有皇后 (同一对角线上 j - i 是一个定值 , 但可能出现负数,因此加一个n)

boolean[][] vis ;
void search(int cur){
if(cur == n){ // n个皇后都不冲突
++counter;
return;
}
for(int i = 0; i < n; ++i){
// 尝试把第cur行的皇后放在第i列
C[cur] = i;
// 检查是否和前面皇后冲突
if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){
C[cur] = i;
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = true;
search(cur + 1);
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = false;
}
}
}

N-Queens

N皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
List<List<String>> result = new LinkedList<>();
boolean[][] vis ;
/**
* vis[0][i] : 第i列有没有皇后
* vis[1][i + j] : 第 i+j 对角线有无皇后
* vis[2][i - j + n] : 第 i-j 对角线有无皇后**/
private void helper(int row, List<String> pos, int n){
if(row == n){
List<String> one = new LinkedList<>();
one.addAll(pos);
result.add(one);
return;
}
// 尝试将第row行的皇后放入第col列
for(int col = 0; col < n; ++ col){
if(!vis[0][col] && !vis[1][col + row] && !vis[2][col - row + n]){
// 构建第row行的皇后阵列
StringBuilder strBu = new StringBuilder();
int i = 0;
while (i < n){
if(i == col) {
strBu.append("Q");
}else{
strBu.append(".");
}
++i;
}
pos.add(strBu.toString());
vis[0][col] = true;
vis[1][col + row] = true;
vis[2][col - row + n] = true;
helper(row + 1, pos, n);
pos.remove(pos.size() - 1);
vis[0][col] = false;
vis[1][col + row] = false;
vis[2][col - row + n] = false;
}
}
}
public List<List<String>> solveNQueens(int n) {
vis = new boolean[3][2*n];
helper(0,new LinkedList<>(), n);
return result;
}

N-Queens II

求N皇后的所有的可能排列数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
boolean[][] vis ;
/**
* vis[0][i] : 第i列有没有皇后
* vis[1][i + j] : 第 i+j 对角线有无皇后
* vis[2][i - j + n] : 第 i-j 对角线有无皇后**/
private int helper(int row, int n){
if(row == n){
return 1;
}
int counter = 0;
// 尝试将第row行的皇后放入第col列
for(int col = 0; col < n; ++ col){
if(!vis[0][col] && !vis[1][col + row] && !vis[2][col - row + n]){
vis[0][col] = true;
vis[1][col + row] = true;
vis[2][col - row + n] = true;
counter += helper(row + 1, n);
vis[0][col] = false;
vis[1][col + row] = false;
vis[2][col - row + n] = false;
}
}
return counter;
}
public int totalNQueens(int n) {
vis = new boolean[3][2*n];
return helper(0, n);
}

全排列问题

全排列问题主要有以下几个知识点:

  • 暴力枚举、回溯
  • Heap's Algorithm
  • 固定-交换法
  • 字典法
  • 求第k个排列,计算法

Permutations

给一个无重数组,生成这个数组数字的全排列。

暴力循环法

一般最先想到的方法是暴力循环法,即对于每一位,遍历集合中可能的元素,如果在这一位之前出现过了该元素,跳过该元素。例如对于123,第一位可以是 1 或 2 或 3 。当第一位为 1时,第二位再遍历集合,发现 1 不行,因为前面已经出现 1 了,而 2 和 3 可以。当第二位为 2 时 , 再遍历集合,发现 1 和 2都不行,3 可以。可以用递归或循环来实现,但是复杂度为 \(O(n^n)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 // 典型的回溯方法

List<List<Integer>> result;
private void helper(int[] nums, boolean[] used, List<Integer> preArr){
if(preArr.size() == nums.length){
List<Integer> one = new LinkedList<>();
one.addAll(preArr);
result.add(one);
}
for(int i = 0; i < nums.length; ++i){
// 如果nums[i]被用过了,就跳过
if(used[i]) continue;
// 否则,加入到当前序列里
preArr.add(nums[i]);
used[i] = true;
helper(nums,used,preArr);
preArr.remove(preArr.size() - 1);
used[i] = false;
}
}
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
result = new LinkedList<>();
helper(nums,used,new LinkedList<>());
return result;
}

有没有更优雅的解法呢。

当然是有骚操作的。

Heap's Algorithm

Heap's Algorithm 是B. R. Heap在1963提出的一种全排列的算法。核心思想就是每次保持n - 2个元素不动,对剩余的两个元素进行交换。什么意思呢?我们以[a,b,c,d]这四个元素的全排列为例,首先,我们将元素d作为固定元素拿出来,对[a,b,c]进行全排列,而对[a,b,c]进行全排列的过程中,我们又将c作为固定元素拿出来,对元素ab进行交换,这样就得到全排列的两种可能。同理,下一步是我们将b作为固定元素拿出来,对ac进行交换。依次类推。这张图详细地展示了这一种算法思想,请参考

可能有点不好理解。我们先看一下伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 保持第n个元素不动,对前n-1个元素进行全排列
generate(int n, int[] A){
if n == 1 then
output(A)
else
for(i = 0; i < n - 1; ++i){
generate(n-1, A)
if(n%2 == 0){ // 如果n是偶数,交换第i个和最后一个元素
swap(A[i], A[n-1])
}else{// 如果n是奇数,交换第1个和最后一个元素;
swap(A[0], A[n-1])
}
}
generate(n-1, A)
}

然而并不能看懂在干啥。

固定-交换法

还有一种思路,这个更好理解一丢丢:

n个数的全排列,一共有\(n!\)种情况. (n个位置,第一个位置有n种,当第一个位置固定下来之后,第二个位置有n-1种情况...)

全排列的过程:

  • 选择第一个字符
  • 获得第一个字符固定下来之后的所有的全排列
    • 选择第二个字符
    • 获得第一+ 二个字符固定下来之后的所有的全排列

从这个过程可见,这是一个递归的过程。

所以这种方式也是通过固定一个元素,进行剩余元素的交换。缺点是,每次交换过后需要再次交换以回到上一层数组。

代码较为简单些:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void swap(int[] nums,int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
List<List<Integer>> result = new LinkedList<>();
private void helper(int[] nums, int fixed){
if(fixed == nums.length){
List<Integer> one = new ArrayList<>(nums.length);
for(int e : nums){one.add(e);}
result.add(one);
return;
}
// 将fixed依次与后面的元素交换
for(int i = fixed; i < nums.length; ++i){
swap(nums, i, fixed);
helper(nums, fixed + 1);
swap(nums, i, fixed);
}
}
public List<List<Integer>> permute(int[] nums) {
helper(nums,0);
return result;
}

Permutations II

follow up -- 如果输入数组有重复元素,输出全排列

暴力求解

由于这道题有重复元素,因此需要注意重复元素。

最暴力的方式就是先排序,然后当这个元素与上一次循环的元素一样时,跳过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<List<Integer>> result = new LinkedList<>();
boolean[] used;
private void helper(int[] nums,List<Integer> one, int i){
if(i == nums.length){
List<Integer> res = new ArrayList<>(nums.length);
res.addAll(one);
result.add(res);
return;
}
int last = Integer.MIN_VALUE;
for(int j = 0; j < nums.length; ++j){
if(used[j] || (j > 0 && nums[j] == last)) continue; // 注意这里不可以用nums[j] == nums[j - 1] !!!
one.add(nums[j]);
used[j] = true;
helper(nums,one,i + 1);
used[j] = false;
one.remove(one.size() - 1);
last = nums[j];
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
Arrays.sort(nums);
helper(nums,new ArrayList<Integer>(nums.length), 0);
return result;
}

固定-交换法

当然,这道题也可以借用上一题“交换”的想法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private void swap(int[] nums,int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
List<List<Integer>> result = new LinkedList<>();

private void helper(int[] nums, int i){
if(i == nums.length){
List<Integer> res = new ArrayList<>(nums.length);
for(int e : nums){res.add(e);}
result.add(res);
return;
}
for(int j = i ; j < nums.length; ++j){
// 一旦i~j之间有一个元素nums[k]与nums[j]相同,那就不用再交换了(因为nums[k] == nums[j],没有必要再次交换了
boolean stop = false;
for(int k = j - 1; k >= i; --k){
if(nums[k] == nums[j]){
stop = true;break;
}
}
if(stop)continue;
// 将nums[i] 依次与nums[j]交换,然后固定nums[i]
swap(nums, i, j);
helper(nums, i + 1);
swap(nums, i, j);

}

}
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
helper(nums, 0);
return result;
}

follow up - 字典顺序输出全排列

如果我们要求按照字典顺序输出全排列呢?

固定-交换法

假如按照上面固定交换法呢?

我们先看看固定-交换法的执行结果:

输入123,输出为:

1
2
3
4
5
6
0	[1, 2, 3]
1 [1, 3, 2]
2 [2, 1, 3]
3 [2, 3, 1]
4 [3, 2, 1] -- x
5 [3, 1, 2] -- x

我们发现最后两个输出的顺序不是字典顺序。这是因为在之前的交换中,当我们把3固定在首位时,此刻3之后的数字不是顺序了。所以生成有误。

那么我们做出一点改动,即在交换时,我们使用一种shift操作:

1
2
3
1 2 3 4
↓ shift
4 1 2 3

即保持原数组不变,只把后面的提到前面来

当然在递归结束,还要这样shift_back回去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
private void swap(int[] nums,int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void shift(int[] nums, int i, int j){
// 将nums[j]挪到nums[i] , 然后将其余的后移
int temp = nums[j];
while (j > i){
nums[j] = nums[j-1];
--j;
}
nums[i] = temp;
}
private void shiftBack(int[] nums, int i, int j){
// 将nums[i]挪到nums[j] , 然后将其余的左移
int temp = nums[i];
while (i < j){
nums[i] = nums[i + 1];
++i;
}
nums[j] = temp;
}
int counter = 0;
String result;
int k;
private void helper(int[] nums, int i){
if(counter > k){
return;
}
if(i == nums.length){
++counter;
//System.out.println(counter + "\t" + Arrays.toString(nums));
StringBuilder strBu = new StringBuilder();
if(counter == k){
for(int e : nums)strBu.append(e);
result = strBu.toString();
}
return;
}
for(int j = i; j < nums.length; ++j){
shift(nums, i, j);
helper(nums, i + 1);
shiftBack(nums, i ,j);
}
}
public String getPermutation(int n, int k) {
int[] nums = new int[n];
for(int i = 0; i < n; ++i){
nums[i] = i + 1;
}
this.k = k;
helper(nums,0);
return result;

}

然后就万事大吉了!

然而,这种方式非常的慢。

我们还有一种优化,接着看下一题。

Next Permutation

输出指定数组的下一个排列

骚操作,字典法

这个算法的核心思想就是,对于每一种可能排列的情况,我们都想办法使其与某种顺序建立对应关系,这种关系式一一对应的,这样我们就能通过遍历得到的某种顺序来生成全排列,这样就能避免递归过程了。这种按照某种顺序来生成全排列的方法就被称为是字典序。

很显然,最重要的是如何才能找到这样一种一一对应的顺序关系,此处继续用\(a={0,1,2,3}\)来说明字典序算法的过程。

要找到一种顺序关系,我们就首先要定义大小关系,对于两个序列\({0,2,1,3}\)\({0,2,3,1}\)来说,序列\({0,2,3,1}\)要比\({0,2,1,3}\)大,比较的方法是从前到后依次比较相同位置上的元素,如果相同则继续比较下一个元素,直到遇到一个不同的元素,元素值大的序列就大于元素值小的序列。按照这样的大小关系形成的序列的顺序,就是字典序。可以看到,最小的序列一定是\({0,1,2,3}\),最大的序列是\({3,2,1,0}\)。而字典序算法就是从字典序中最小的序列开始,一直不停寻找下一个仅比上一个序列大的序列,直到到达最大的序列。[2]

现在问题变成了,如何从当前状态生成下一个状态?

假设当前排列是\(a[1.....n]\)

  1. \(a\)中找到满足\(a[k] < a[k + 1]\)(升序)的最后一个k。如果不存在,则\(a\)已经是字典序最大序列了。
  2. \(a[k + 1,....,n]\) 中寻找比\(a[k]\) 大的最小值\(a[j]\)。(在\(a[k+1,...,n]\) 中,\(a[k]\) 仅次于\(a[j]\) 的数字。将它们交换后,能保证整个序列是最小增长的)
  3. 交换\(a[k]与a[j]\) ,并将\(a[k,...,n]\) 全部排序

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
private void swap(int[] nums,int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void nextPermutation(int[] nums) {
int n = nums.length;
// 寻找nums的下一个排列
// 寻找最后一个升序nums[q]
int q = -1;
for(int i = 1; i < n; ++i){
if(nums[i - 1] < nums[i]){
q = i - 1 ;
}
}
if(q == -1){ // 此刻nums是最后一个排列
int start = 0, end = n-1;
while (start + 1 < end){
swap(nums,start,end);
++start; --end;
}
if(start + 1 == end){swap(nums,start,end);}
}
else {
// 寻找比nums[q]大的最小值nums[m]
int m = q, min = Integer.MAX_VALUE;
int i = q;
while (i < n) {
if (nums[i] > nums[q] && nums[i] < min) {
min = nums[i];
m = i;
}
++i;
}
// 将nums[q]与nums[m]交换
swap(nums, q, m);
// 将[q + 1 ~ n]倒排
Arrays.sort(nums, q + 1, n);
// 输出nums
}
}

当然有一种优化思路是,优化第1步中:将”从前到后寻找最后一个升序“转化为”从后到前寻找第一个降序“。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public void nextPermutation(int[] nums) {
int n = nums.length;
// 寻找nums的下一个排列
// 寻找最后一个升序nums[q]
int q = nums.length;
for(int i = n - 1; i > 0; --i){
if(nums[i - 1] < nums[i]){
q = i - 1 ;
break;
}
}
if(q == nums.length){ // 此刻nums是最后一个排列
int start = 0, end = n-1;
while (start + 1 < end){
swap(nums,start,end);
++start; --end;
}
if(start + 1 == end){swap(nums,start,end);}
}
else {
// 寻找比nums[q]大的最小值nums[m]
int m = q, min = Integer.MAX_VALUE;
int i = q;
while (i < n) {
if (nums[i] > nums[q] && nums[i] < min) {
min = nums[i];
m = i;
}
++i;
}
// 将nums[q]与nums[m]交换
swap(nums, q, m);
// 将[q + 1 ~ n]倒排
Arrays.sort(nums, q + 1, n);
// 输出nums
}
}

Next Greater Element III

给一个数,输出这个数的所有排列中刚好比这个数稍微大一点的数。

这对我来说还是有点难度的。需要一点技巧。想要生成稍微大一点的数,那就要从低位下手。例如一个数是***132000,那么把1和2交换就可以得到一个稍微大一点的数。而我们需要确保以下几点:

  1. '1' 一定是从右往左看第一个递减的数
  2. '2' 一定是1右边的那个稍微比1大一点点的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 public int nextGreaterElement(int n) {

// 样例 230241 -> 230412

char[] number = (n + "").toCharArray(); // 这简直是骚操作了
// 从个位开始,依次寻找第一次递减的两个数
int i = number.length - 1;
for(i = number.length - 1; i > 0; --i){
if(number[i-1] < number[i] ) break;// 找到number[i-1] = 2
}
if(i == 0) return -1;

// 从(i,number.length)找到比i-1大的最小的数,放在i-1的位置。
// 这样就能确保现在生成的数字是最小的
int smallest = i;
for(int j = i + 1; j < number.length; ++j){
if(number[j] > number[i - 1] && number[j] <= number[smallest])
smallest = j;
}
// 将largestIdx与i-1交换
char temp = number[smallest];
number[smallest] = number[i - 1];
number[i - 1] = temp;
// 将剩下的数字排序
Arrays.sort(number, i, number.length);

// 转化为数字
long val = Long.parseLong(new String(number));
return (val <= Integer.MAX_VALUE) ? (int) val : -1;
}

Permutation Sequence

输出1-n数字组成的数字中的字典序第k个排列

思路一:如果用follow up 的代码,是完全可以的。只是时间非常高。

思路二:字典法,依次输出,时间代价还是很昂贵,还有可能超时

思路三:骚操作

n个数的全排列一共有\(n!\) 个。基于这个性质我们可以计算出某一位对应的数字是几!骚操作啊!

我们用123来举例。它的全排列为:

1
2
3
4
5
6
7
            第一位           第二位
0 123 1 = nums[0/2] 2
1 132 1 = nums[1/2] 3
2 213 2 = nums[2/2] 1
3 231 2 = nums[3/2] 3
4 312 3 = nums[4/2] 1
5 321 3 = nums[5/2] 2 <-- k = 5

因为当第一位确定时,全排列个数为\((n-1)! = 2\) 个。

所以第一位的重复周期是\((n-1)!\) 。那么第k个就是\(\frac{k}{(n-1)!}\)

假如第一位是a1 = 3,那么第一位是1和2的全排列都可以去除了!那就是从3开头的全排列中寻找第\(k' = k - (a1-1) * (n-1)! = k \text{ % } (n-1)! = 5 - 4 = 1\) 个!

而且,当第一位确定时,第二位只剩下\(n - 1\) 个数字可以选择。因此以3开头的只有\((n-2)!\) 种。所以第二位的数字为\(\frac{k`}{(n-2)!}\)

然后我们就找到了规律!

a1 = k / (n - 1)! k1 = k

a2 = k1 / (n - 2)! k2 = k1 % (n - 2)! ...

an-1 = kn-2 / 1! kn-1 = kn-2 / 1!

an = kn-1 / 0! kn = kn-1 % 0!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String getPermutation(int n, int k) {
ArrayList<Integer> candidates = new ArrayList<>(n);
for(int i = 1; i <= n; ++i){
candidates.add(i);
}
// 先存下来n!
int[] factorial = new int[n + 1];
factorial[0] = 1;
factorial[1] = 1; // factorial[i] = i!
for(int i = 2; i <= n; ++i){
factorial[i] = factorial[i-1] * i;
}
// 计算第k位
k = k - 1;
StringBuilder stringBuilder = new StringBuilder();
for(int i = 0; i < n; ++i){
int idx = k / factorial[n-1-i] ;
stringBuilder.append(candidates.get(idx));
candidates.remove(idx); // 注意维护剩余集合
k = k % factorial[n-1-i];
}
return stringBuilder.toString();
}

Binary Watch

有一种二进制的表。其中用4个位数表示小时(0-11),用6个位数表示分钟(0-59)。

给一个n,表示当前亮灯的个数。求可能出现的时刻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private void permutations(int[] candidates, int idx, int num, int sum, List<Integer> result, int limit){
//从候选集里选num个,求相加有多少种结果
if(sum >= limit)return;
if(num == 0){result.add(sum);return;}
if(idx >= candidates.length || candidates.length - idx < num)return;
for(int i = idx; i < candidates.length; ++i){
permutations(candidates, i + 1, num - 1, sum + candidates[i], result, limit);
}
}
private List<String> helper(int h_num, int m_num, int[] h, int[] m){
// h_num个小时灯,m_num个分钟灯
List<Integer> hours = new LinkedList<>();
permutations(h, 0, h_num, 0, hours, 12);
List<Integer> minites = new LinkedList<>();
permutations(m, 0, m_num, 0, minites, 60);
//两两组合
List<String> result = new LinkedList<>();
for(Integer hour : hours){
String hour_str = Integer.toString(hour);
for(Integer minite : minites){
String min_str = minite < 10 ? "0"+Integer.toString(minite) : Integer.toString(minite);
result.add(hour_str + ":" + min_str);
}
}
return result;
}
public List<String> readBinaryWatch(int num) {
int[] h = {1,2,4,8};
int[] m = {1,2,4,8,16,32};
List<String> result = new LinkedList<>();
for(int h_num = 0; h_num < 4; ++h_num){
int m_num = num - h_num;
if(m_num > 6)continue;
result.addAll(helper(h_num, m_num, h, m));
}
return result;
}

Sliding Puzzle

给一个2*3的数组,其中元素是0、1、2、3、4 、5。每次只能将0与周围的4个位置交换。求问给定数组最少交换多少次,可以将数组交换为123450

思路:回溯法 + 记忆化搜索

要点:记忆化搜索里存储的内容是:从原数组走到现在,已经走了多少步!(这一点想了很久都没有想通。自己陷入了怪圈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Map<Integer, Integer> map = new HashMap<>(); // 从原数组走到key,已经走了多少步
int min_move = Integer.MAX_VALUE;
public int slidingPuzzle(int[][] board) {
map.put(123450, 0);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == 0) {
helper(board, i,j, 0);
return min_move == Integer.MAX_VALUE ? -1 : min_move;
}
}
}

}
private void helper(int[][] board, int x, int y, int move) {
// 如果走到key时步数已经大于最小步数了,那就没有必要再继续走了
if (move > min_move) return;
int code = encode(board);
if (code == 123450) {
min_move = move;
return;
}
if (map.containsKey(code)) {
// 如果这次的move步数大于之前另一种方式move到code的步数,那就没有必要再继续走了
if (move > map.get(code)) return;
}
map.put(code, move);
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < 2 && ny >= 0 && ny < 3) {
swap(board, x, y, nx, ny);
helper(board, nx, ny, move + 1);
swap(board, nx, ny, x, y);
}
}
}
private void swap (int[][] board, int i, int j, int ii, int jj) {
int temp = board[i][j];
board[i][j] = board[ii][jj];
board[ii][jj] = temp;
}
private int encode(int[][] board) {
int code = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
code *= 10;
code += board[i][j];
}
}
return code;
}

元素和、组合问题

Combinations

用1-n的数字,每次拿k个。输出所有的组合方式。

相当经典的回溯问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
List<List<Integer>> result = new LinkedList<>();
private void helper(int n, int k, int start, List<Integer> candidates){
if(k == 0){
result.add(new ArrayList<>(candidates));
return;
}
for(int i = start; i <= n; ++i){
candidates.add(i);
helper(n, k - 1, i + 1, candidates);
candidates.remove(candidates.size() - 1);
}
}
public List<List<Integer>> combine(int n, int k) {
helper(n, k, 1, new LinkedList<>());
return result;
}

在leetcode上看到还有一种思路,很快。但总体复杂度其实差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> combine(int n, int k) {
List<Integer> current = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
dfs(result, current, 1, n, k);
return result;
}

void dfs(List<List<Integer>> result, List<Integer> current, int c, int n, int k) {
if (c + k > n + 1) {
return;
}
if (k == 0) {
List<Integer> tmpList = new ArrayList<>(current);
result.add(tmpList);
return;
}
// 使用c这个数字
current.add(c);
dfs(result, current, c + 1, n, k - 1);
current.remove(current.size() - 1);
// 不使用c这个数字
dfs(result, current, c + 1, n, k);
}

Combination Sum

给一个数组和一个target.求数组中的元素和等于target的所有可能。元素可以多次取。

思路:典型的回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<List<Integer>> result = new LinkedList<>();
private void helper(int[] candidates, int target, int start, ArrayList<Integer> added){
if(target < 0)return;
if(target == 0){
List<Integer> aRes = new ArrayList<>(added.size());
aRes.addAll(added);
result.add(aRes);
return;
}
// 从start开始取(start就是上一次使用的元素)
for(int i = start; i < candidates.length; ++i){
added.add(candidates[i]);
helper(candidates, target - candidates[i], i,added);
added.remove(added.size() - 1);
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
helper(candidates,target, 0,new ArrayList<>(candidates.length));
return result;
}

虽然说这道题可以用dp来简化。但是由于重复的边界条件实在是难以处理,所以还是弃用了。

Combination Sum II

给一个有重数组和一个target.求数组中的元素和等于target的所有可能。元素不可以多次取。

这道题与上一题的最大区别就是不能多次取!需要注意的地方就是递归进入时的i需要加一(跳过本元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
List<List<Integer>> result = new LinkedList<>();
private void helper(int[] candidates, int target, int start, List<Integer> selected){
if(target < 0) return;
if(target == 0){
List<Integer> one = new ArrayList<>(selected);
result.add(one);
return;
}
for(int i = start; i < candidates.length; ++i){
if(i > start && candidates[i] == candidates[i - 1])continue; // 去重
if(target - candidates[i] < 0)break;// 剪枝
// 回溯
selected.add(candidates[i]);
helper(candidates, target - candidates[i], i + 1,selected); // 从i + 1处继续
selected.remove(selected.size() - 1);
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
helper(candidates,target, 0, new LinkedList<>());
return result;
}

Combination Sum III

求k个数(0-9的数)的和为n的所有组合。

还是回溯问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<List<Integer>> result = new LinkedList<>();

private void helper(int k, int start, int target, List<Integer> candidates){
if(target < 0 || k < 0) return;
if(target == 0 && k == 0){
result.add(new ArrayList<>(candidates));
return;
}
for(int i = start; i <= 9; ++i){
if(target - i < 0) break; // 剪枝
candidates.add(i);
helper(k - 1,i + 1, target - i, candidates);
candidates.remove(candidates.size() - 1);
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
helper(k,1, n, new LinkedList<>());
return result;
}

当然还可以用另一种思路,就是选或者不选的问题。这种思路类似Combinations的第二种解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<List<Integer>> result = new LinkedList<>();

private void helper(int k, int i, int target, List<Integer> candidates){
if(target == 0 && k == 0){
result.add(new ArrayList<>(candidates));
return;
}
if(k == 0 && target != 0){return;}
if(i > 9 || target < 0 || k < 0) return;
// 选i
candidates.add(i);
helper(k - 1,i + 1, target - i, candidates);
candidates.remove(candidates.size() - 1);
// 不选i
helper(k,i + 1, target, candidates);

}
public List<List<Integer>> combinationSum3(int k, int n) {
helper(k,1, n, new LinkedList<>());
return result;
}

Increasing Subsequences

给一个有重数组,输出所有的递增子序列

思路:回溯法

注意点:由于数组有重,则一定要判断重复!例如数组[1,3,2,3] ,如果不判断重复,就会出现两个[1,3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<List<Integer>> result = new LinkedList<>();
private void helper(int[] nums, int idx,List<Integer> added, int lastAdd, HashSet<Integer> hash){

if(idx >= nums.length){
return;
}

for(int i = idx; i < nums.length; ++i){
if(hash.contains(nums[i]))continue;
if(nums[i] >= lastAdd) {
hash.add(nums[i]);
added.add(nums[i]);
if(added.size() >= 2) {
result.add(new ArrayList<>(added));
}
helper(nums, i + 1, added, nums[i], new HashSet<>());
added.remove(added.size() - 1);
}else
helper(nums, i + 1, added, lastAdd, hash);

}
}
public List<List<Integer>> findSubsequences(int[] nums) {
helper(nums, 0, new LinkedList<>(), Integer.MIN_VALUE, new HashSet<>());
return result;
}

其它问题

Count Numbers with Unique Digits

给一个n。求x的个数,其中\(0<= x <= 10^n\) ,且x的每一位的数字都不相同。

思路:x是n位数,且每位都不相等。

如果n大于10,那\(x > 10^{10}\) 的都不用考虑了

如果n小于等于10,那就考虑0-9能组成多少个n位的数字了!

这道题完全可以用公式完成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n位数的可能有如下:

0 (就是0
1 位数 -> C(9,1) (从1-9里随机挑选一个)
2 位数 -> C(9,1) * C(9,1) (第一位从1-9挑,第二位与第一位不同即可,所以也是9种)
3 位数 -> C(9,1) * C(9,1) * C(8,1) (第一位从1-9挑,第二位与第一位不同,第三位与前两位不同)
...
n 位数

代码:
// * C(9,1) * C(8,1) *....
private int helper(int n, int k){
if(k == 0 || n == 0) return 1;
return k * helper(n - 1, k - 1);
}

public int countNumbersWithUniqueDigits(int n) {
int sum = 1;
for(int i = 1; i <= n; ++i){
sum += 9 * helper(i - 1, 9);
}
return sum;
}

Letter Combinations of a Phone Number

求手机“九宫格”输入数字后组成的字符串的所有可能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
HashMap<Character, String[]> table = new HashMap<>();
private void buildTable(){
table.put('1',new String[0]);
table.put('2',new String[]{"a","b","c"});
table.put('3',new String[]{"d","e","f"});
table.put('4',new String[]{"g","h","i"});
table.put('5',new String[]{"j","k","l"});
table.put('6',new String[]{"m","n","o"});
table.put('7',new String[]{"p","q","r","s"});
table.put('8',new String[]{"t","u","v"});
table.put('9',new String[]{"w","x","y","z"});
table.put('0',new String[]{" "});
table.put('#',new String[]{"#"});
table.put('*',new String[]{"*"});
}
public List<String> letterCombinations(String digits) {
List<String> result = new LinkedList<>();
if(digits.length() == 0) return result;
buildTable();
char[] digits_c = digits.toCharArray();
// 初始化
String[] candicates = table.get(digits_c[0]);
for(String c : candicates){
String aRes = new String(c);
result.add(aRes);
}
// 插入
for(int i = 1; i < digits_c.length; ++i){
candicates = table.get(digits_c[i]);
// 依次将candicates与builder的每个元素组合
List<String> result_curr = new LinkedList<>();
for(String aRes : result){
for(String c : candicates){
String aRes_curr = aRes + c;
result_curr.add(aRes_curr);
}
}
result = result_curr;
}
return result;
}

Generate Parentheses

有n对括号。求所有括号可能的摆放次序(括号必须成对先后出现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
List<String> result = new LinkedList<>();
private void helper(int remain_left, int remain_right, StringBuilder builder){
if(remain_left == 0 && remain_right == 0){
result.add(builder.toString());
return;
}
if(remain_left == 0){
builder.append(')');
helper(remain_left, remain_right - 1, builder);
builder.delete(builder.length() - 1, builder.length());
return;
}
if(remain_left >= remain_right || remain_right == 0){
builder.append('(');
helper(remain_left - 1, remain_right, builder);
builder.delete(builder.length() - 1, builder.length());
return;
}
// 要么放一个左括号
builder.append('(');
helper(remain_left - 1, remain_right, builder);
builder.delete(builder.length() - 1, builder.length());
// 要么放一个右括号
builder.append(')');
helper(remain_left, remain_right - 1, builder);
builder.delete(builder.length() - 1, builder.length());

}
public List<String> generateParenthesis(int n) {
helper(n,n,new StringBuilder());
return result;
}

优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<String> result = new LinkedList<>();
private void helper(int remain_left, int remain_right, StringBuilder builder){
if(remain_left == 0 && remain_right == 0){
result.add(builder.toString());
return;
}
if(remain_left > 0){ // 只要左括号有富裕,就可以放
builder.append('(');
helper(remain_left - 1, remain_right, builder);
builder.delete(builder.length() - 1, builder.length());
}
if(remain_left < remain_right) { // 左括号比右括号多时,才可以放右括号
builder.append(')');
helper(remain_left, remain_right - 1, builder);
builder.delete(builder.length() - 1, builder.length());
}
}
public List<String> generateParenthesis(int n) {
helper(n,n,new StringBuilder());
return result;
}

Valid Sudoku

判断当前给出的数独格子是否符合数独要求(只要判断当前已经填入的空格是否符合要求即可)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
boolean[][] eachRow = new boolean[10][10];
boolean[][] eachCol = new boolean[10][10];
boolean[][] eachSquare = new boolean[10][10];


public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < board.length; ++i){
for(int j = 0; j < board[0].length; ++j){
if(board[i][j] == '.') continue;
if(eachCol[j][board[i][j] - '0'] ||
eachRow[i][board[i][j] - '0'] ||
eachSquare[i/3 + 3*(j/3)][board[i][j] - '0']) return false;
eachCol[j][board[i][j] - '0'] = true;
eachRow[i][board[i][j] - '0'] = true;
eachSquare[i/3 + 3*(j/3)][board[i][j] - '0'] = true;
}
}
return true;
}

Sudoku Solver

\(9 \times 9\) 的数独,填入数字1-9,要求行列不重复,且每个宫内不重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
boolean[][][] used;
/**used[0][i][q] : 第i列,数字q是否被使用
* used[1][i][q] : 第i行,数字q是否被使用
* used[2][i][q] : 第i个宫中数字q是否被使用
* **/
private boolean helper(char[][] board, int filled){
if(filled == board.length * board.length){
return true;
}
for(int i = 0; i < board.length; ++i){
for(int j = 0; j < board.length; ++j){
if(board[i][j] != '.') continue;
//尝试给board[i][j]填入数字q
for(int q = 1; q <= 9; ++q){
if(used[0][i][q] || used[1][j][q] || used[2][j/3 + 3 * (i/3)][q]) continue;
board[i][j] = (char)(q + 48);
used[0][i][q] = true;
used[1][j][q] = true;
used[2][j/3 + 3 * (i/3)][q] = true;
if(helper(board, filled + 1))return true;
board[i][j] = '.';
used[0][i][q] = false;
used[1][j][q] = false;
used[2][j/3 + 3 * (i/3)][q] = false;
}
//这个剪枝很重要
//board[i][j]填任何数字都不行
return false;
}
}
return false;
}
public void solveSudoku(char[][] board) {
used = new boolean[3][board.length][10];
//初始化
int filled = 0;
for(int i = 0; i < board.length; ++i){
for(int j = 0; j < board.length; ++j){
if(board[i][j] == '.')continue;
used[0][i][board[i][j]-48] = true;
used[1][j][board[i][j]-48] = true;
used[2][j/3 + 3 * (i/3)][board[i][j]-48] = true;
++filled;
}
}
helper(board,filled);
}

Beautiful Arrangement

给1-N的数字,填入长度为N的数组。令数组的idx从1开始。要求:idx能整除nums[idx]或nums[idx]能整除idx。求所有的可能数。

思路:一开始想多了。其实用暴力遍历就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int counter = 0;
private void helper(int idx, boolean[] used, int N){
if(idx == used.length){
++counter;
}
for(int i = 1; i <= N; ++i){
if(used[i])continue;
if(idx % i == 0 || i % idx == 0){
used[i] = true;
helper(idx + 1, used, N);
used[i] = false;
}
}
}
public int countArrangement(int N) {
boolean[] used = new boolean[N + 1];
helper(1, used, N);

return counter;
}

Wildcard Matching

给两个字符串,其中一个含有*或?*代表可匹配任意多个字符。?代表可匹配任意元素。求两个字符串是否能完全匹配

思路:回溯,碰到不行的就回退

最后几个样例会超时,所以我又用了dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private int helper(String s, String p, int s_idx, int p_idx){
if(s_idx >= s.length() && p_idx >= p.length()) return 1;
if(p_idx >= p.length()) return -1;
if(s_idx >= s.length()){
while (p_idx < p.length()) {
if (p.charAt(p_idx) == '*')
++p_idx;
else return -1;
}
return 1;
}

if(dp[s_idx][p_idx] != 0) return dp[s_idx][p_idx];

char s_element = s.charAt(s_idx);
char p_element = p.charAt(p_idx);

if(p_element == '?'){
dp[s_idx][p_idx] = helper(s, p, s_idx + 1, p_idx + 1);
}else if(p_element == '*'){
// 跳过连续的******
while (p_idx < p.length() - 1){
if(p.charAt(p_idx + 1) == '*') ++p_idx;
else break;
}
dp[s_idx][p_idx] = helper(s, p, s_idx, p_idx + 1);
if(dp[s_idx][p_idx] == -1)
dp[s_idx][p_idx] = helper(s, p, s_idx + 1, p_idx);
}else if(p_element == s_element){
dp[s_idx][p_idx] = helper(s, p, s_idx + 1, p_idx + 1);
}else
dp[s_idx][p_idx] = -1;
return dp[s_idx][p_idx];
}
int[][] dp;
public boolean isMatch(String s, String p) {
dp = new int[s.length()][p.length()];
return helper(s, p, 0, 0) == 1;
}

二刷:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private int helper(String s, String p, int s_idx, int p_idx){
if(memo[s_idx][p_idx] != 0) return memo[s_idx][p_idx];
if(s_idx == s.length() && p_idx == p.length()){
memo[s_idx][p_idx] = 1;
return memo[s_idx][p_idx];
}
if(p_idx == p.length()) {
memo[s_idx][p_idx] = -1;
return memo[s_idx][p_idx];
}
if(s_idx == s.length()){
while (p_idx < p.length() && p.charAt(p_idx) == '*') {++p_idx;}
memo[s_idx][p_idx] = p_idx == p.length() ? 1 : -1;
return memo[s_idx][p_idx];
}

if(p.charAt(p_idx) == '?' || s.charAt(s_idx) == p.charAt(p_idx)){
memo[s_idx][p_idx] = helper(s,p, s_idx + 1, p_idx + 1);

}else if(p.charAt(p_idx) == '*'){
memo[s_idx][p_idx] = helper(s, p, s_idx + 1, p_idx);
if(memo[s_idx][p_idx] < 0)
memo[s_idx][p_idx] = helper(s, p, s_idx, p_idx + 1);
}else{
memo[s_idx][p_idx] = -1;
}
return memo[s_idx][p_idx];
}
int[][] memo;
public boolean isMatch(String s, String p) {
memo = new int[s.length() + 1][p.length() + 1];
helper(s, p ,0,0);
return memo[s.length()][p.length()] == 1;
}

Regular Expression Matching

给两个字符串,其中一个含有*或.*代表可匹配前一个元素0个或多个。.代表可匹配任意元素。求两个字符串是否能完全匹配

思路:回溯,碰到不行的就回退

注意边界条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private boolean helper(String s, String p, int s_idx, int p_idx){
if(s_idx < 0 && p_idx < 0) return true;
if(p_idx < 0) return false;
if(s_idx < 0){
if(p.charAt(p_idx) == '*')
return helper(s, p, s_idx, p_idx - 2); // 匹配0个
else return false;
}
char p_element = p.charAt(p_idx);
char s_element = s.charAt(s_idx);
if(p_element == '.'){
return helper(s, p, s_idx - 1, p_idx - 1);
}else if(p_element == '*'){
// 比较s[s_idx]与p[p_idx - 1]
if(p_idx == 0) return true;
if((s_element == p.charAt(p_idx - 1)) || (p.charAt(p_idx - 1) == '.')){
return helper(s, p, s_idx - 1,p_idx) || // 匹配1个
helper(s, p, s_idx, p_idx - 2); // 匹配0个
}else{
return helper(s, p, s_idx, p_idx - 2); // 匹配0个
}
}else{
if(p_element == s_element){
return helper(s, p, s_idx - 1, p_idx - 1);
}else
return false;
}
}
public boolean isMatch(String s, String p) {
return helper(s, p, s.length() - 1,p.length() - 1);
}

Reconstruct Itinerary

行程安排问题。一个人从JFK出发,求一种能走得通的行程

这道题写了很久,一开始陷入了拓扑排序的怪圈。以后要注意自己的思维,不要被之前的题限制!

思路:

  1. 建立每个点的邻接列表
  2. 依次往下探测,遇到不合适的就返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Node implements Comparable<Node>{
String departure;
ArrayList<Node> neighbors = new ArrayList<>();
boolean[] visited;
Node(String departure){
this.departure = departure;
}

@Override
public int compareTo(Node o) {
return this.departure.compareTo(o.departure);
}
}
private HashMap<String, Node> countDegree(String[][] tickets){
HashMap<String, Node> hashMap = new HashMap<>();
for(String[] edge : tickets){
hashMap.put(edge[0], new Node(edge[0]));
hashMap.put(edge[1], new Node(edge[1]));
}
for(String[] edge : tickets){
Node neibor = hashMap.get(edge[1]);
hashMap.get(edge[0]).neighbors.add(neibor);
}
// 对每个departures的邻居排序
for(Node e : hashMap.values()){
Collections.sort(e.neighbors);
e.visited = new boolean[e.neighbors.size()];
}
return hashMap;
}
private boolean dfs(Node departure, List<String> result, int length){
//System.out.println(result);
if(result.size() == length) return true;
else if(result.size() > length) return false;
for(int i = 0; i < departure.visited.length; ++i){
if(departure.visited[i])continue;
departure.visited[i] = true;
result.add(departure.neighbors.get(i).departure);
if(dfs(departure.neighbors.get(i), result, length)) return true;
result.remove(result.size() - 1);
departure.visited[i] = false;
}
return false;
}
public List<String> findItinerary(String[][] tickets) {
//统计每个站邻居,并做排序
HashMap<String, Node> departures = countDegree(tickets);
// 开始做dfs
List<String> result = new ArrayList<>(2 + tickets.length - 1);
result.add("JFK");
dfs(departures.get("JFK"), result, 2 + tickets.length - 1);
return result;
}

用优先队列

下面这个方法真是太鸡贼了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<String> findItinerary(String[][] tickets) {
for (String[] ticket : tickets)
targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
visit("JFK");
return route;
}

Map<String, PriorityQueue<String>> targets = new HashMap<>();
List<String> route = new LinkedList();

void visit(String airport) {
while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
visit(targets.get(airport).poll());
route.add(0, airport); // 这里很巧妙
// 1. 假设这条路下去是个环路,走回来了,那就暂时先不加,继续从环路递归
// 2. 加入这条路不是个环路,那就加进去,然后跳出循环,回到环路,再把环路的结果依次相加
}

还有一种非递归,用栈的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<String> findItinerary(String[][] tickets) {
Map<String, PriorityQueue<String>> targets = new HashMap<>();
for (String[] ticket : tickets)
targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
List<String> route = new LinkedList();
Stack<String> stack = new Stack<>();
stack.push("JFK");
while (!stack.empty()) {
while (targets.containsKey(stack.peek()) && !targets.get(stack.peek()).isEmpty())
stack.push(targets.get(stack.peek()).poll());
route.add(0, stack.pop());
}
return route;
}

Matchsticks to Square

给一个数组,值表示火柴长度。求这些火柴能不能组成正方形。

有意思的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private boolean dfs(int[] nums, boolean[] visited, int idx, int sum, int width, int counter){
if(sum > width)return false;
if(counter >= 4)return true;
if(sum == width){
++counter;
if(counter == 4)return true;
idx = 0; //这里比较有意思
sum = 0; // 有意思哇
}
if(idx >= nums.length || nums[idx] > width) return false;
for(int i = idx; i < nums.length; ++i){
if(visited[i])continue;
if(nums[i] > width)return false;
visited[i] = true;
if(dfs(nums, visited, i + 1, sum + nums[i], width,counter))return true;
visited[i] = false;
}
return false;
}
public boolean makesquare(int[] nums) {
int sum = 0;
for(int num : nums) sum += num;
if(sum % 4 != 0) return false;
int width = sum/4;
return dfs(nums, new boolean[nums.length], 0, 0, width, 0);
}

Maximum Length of Pair Chain

假设有整数对[a,b][c,d] 。如果b < c ,那么这两个整数对可以构成一个链。给一些整数对,求这些整数对能构成的最长链。

思路:排序+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
   int[] memo;
// memo[i]表示[i,n]的整数对能构成的最长链
private int helper(int[][] pair, int idx, int[] lastPair){
if(idx >= pair.length) return 0;
if(memo[idx] >= 0) return memo[idx];
// [lastPair[0], lastPair[1]] , [pairidx[0], pairidx[1]]
// 如果这两个整数对可以构成链,则尝试构成
if(lastPair[1] < pair[idx][0]){
memo[idx] = helper(pair, idx + 1, pair[idx]) + 1;
}
// 跳过这个整数对
memo[idx] = Math.max(memo[idx], helper(pair, idx + 1, lastPair));
return memo[idx];
}
public int findLongestChain(int[][] pairs) {
// 先按照第2个元素排序
Arrays.sort(pairs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
memo = new int[pairs.length];
Arrays.fill(memo, -1);
return helper(pairs, 0, new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE});
}

参考文献

  1. 全排列的经典算法-heap's algorithms
  2. 全排列算法part1
  3. [Leetcode] Permutation Sequence 全排列序列
  4. [LeetCode]76. Permutation Sequence全排列序列