思路
BFS
Solution:
Time: O(A^A)
Space: O(A)
public class Solution {
public int solve(int A, ArrayList<Integer> B) {
int[] count = new int[]{0};
helper(A, B, count);
return count[0];
}
private void helper(int A, ArrayList<Integer> B, int[] count) {
if (A == B.size()) {
System.out.println(B.toString());
count[0] += 1;
return;
}
Set<Integer> exist = new HashSet<>(B);
Set<Integer> candidates = new HashSet<>();
for (int i = 0; i < B.size(); i ++) {
int curr = B.get(i);
if (curr - 1 >= 1 && !exist.contains(curr - 1)) {
candidates.add(curr - 1);
}
if (curr + 1 <= A && !exist.contains(curr + 1)) {
candidates.add(curr + 1);
}
}
for (int candidate : candidates) {
ArrayList<Integer> b = new ArrayList<>(B);
b.add(candidate);
helper(A, b, count);
}
}
}
思路2
假设input是10, [3, 7]
我们可以将没见过的城市分成3个连续的group,
1,2
4,6
8,10
1，2和8，10这样两边的城市分别只有一种visit的办法，2 -> 1，8 -> 9 -> 10
4，6这样中间的城市则有2^(size - 1)的方法，因为可以从两边visit，比如4，6有2^2 = 4种方法，分别是456，465，654，645。
如果我们按group从前往后visit，那只要把各个group的visit的方法乘起来就可以。
但是我们还要考虑visit不同group的顺序可以不同，比如我们可以先visit group<4,6> ->4，再visit<1,2> -> 1，再visit<8, 10> -> 8，再visit<4.6> -> 5， 再visit<8, 10> -> 9。。。也可以先visit group<1,2> ->1，再visit group<8, 10> -> 8。。。
要计算有多少种不同的顺序可以用nCr来计算，比如当我们只有<1,2>的时候，总共有两个城市AA，有两个candidateAA，所以有2C2 = 1种可能，同时每种顺序也只有一种visit方法2->1。然后我们来到<4,6>，这时总共有5个城市AABBB，4到6三个城市BBB共能造成5C3 = 10 种可能: AABBB, ABABB, ABBAB, ABBBA, BAABB, BABAB, BABBA, BBABA, BBAAB, BBBAA（每种顺序可能有4种visit方法 =》 456，465，654，645）。再来到<8,10>，总共有8个城市，AABBBCCC，同样的有8C3 = 56种组合，但是每种组合有1种visit方法，因为只能从8visit到10。
我们需要把每个group有多少种visit的方法，乘以visit不同group的组合，就能得到答案。
[<1,2>, <4,6>, <8,10>]
1 * 1 * (2C2) = 1
1 * 4 * (5C3) = 40
40 * 1 * (8C3) = 2240
2240
Solution:
Time: O(A^2)
Space: O(A^2)
public class Solution {
public static class Group {
int x;
int y;
public Group(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "<" + this.x + "," + this.y + ">";
}
}
public int solve(int A, ArrayList<Integer> B) {
long[][] combinations = getCombs(A);
long[] binomials = getBinomials(A);
long total = 1;
int totalCity = 0;
List<Group> groups = getGroups(A, B);
// System.out.println(groups.toString());
for (int i = 0; i < groups.size(); i ++) {
long possibilityInGroup = 1;
Group group = groups.get(i);
int size = group.y - group.x + 1;
totalCity += size;
if (group.x != 1 && group.y != A) {
possibilityInGroup = binomials[size - 1];
}
//System.out.println(total + " * " + possibilityInGroup + " * (" + totalCity + "C" + size + ")");
total = (total * possibilityInGroup) % 1000000007;
total = (total * combinations[totalCity][size]) % 1000000007;
}
return (int) (total % 1000000007);
}
private long[][] getCombs(int A) {
long[][] combs = new long[A + 1][A + 1];
for (int i = 1; i <= A; i ++) {
for (int j = 0; j <= i; j ++) {
if (j == 0 || i == j) {
combs[i][j] = 1;
} else {
// if A is picked, the rest possibilty is N-1 C j - 1
// if A is not picked, the rest is N - 1 C j
combs[i][j] = (combs[i - 1][j] + combs[i - 1][j - 1]) % 1000000007;
}
}
}
return combs;
}
private long[] getBinomials(int A) {
long[] bino = new long[A + 1];
bino[0] = 1;
for (int i = 1; i <= A; i ++) {
bino[i] = (bino[i - 1] * 2) % 1000000007;
}
return bino;
}
private List<Group> getGroups(int A, ArrayList<Integer> B) {
Collections.sort(B);
List<Group> groups = new ArrayList<>();
int next = 1;
for (int i = 0; i < B.size(); i ++) {
int curr = B.get(i);
if (curr - 1 >= next) {
groups.add(new Group(next, curr - 1));
}
next = curr + 1;
}
if (A >= next) {
groups.add(new Group(next, A));
}
return groups;
}
}