forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode03_10Ways.java
More file actions
92 lines (85 loc) · 1.75 KB
/
Code03_10Ways.java
File metadata and controls
92 lines (85 loc) · 1.75 KB
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package class39;
import java.util.LinkedList;
public class Code03_10Ways {
public static long ways1(int N) {
int zero = N;
int one = N;
LinkedList<Integer> path = new LinkedList<>();
LinkedList<LinkedList<Integer>> ans = new LinkedList<>();
process(zero, one, path, ans);
long count = 0;
for (LinkedList<Integer> cur : ans) {
int status = 0;
for (Integer num : cur) {
if (num == 0) {
status++;
} else {
status--;
}
if (status < 0) {
break;
}
}
if (status == 0) {
count++;
}
}
return count;
}
public static void process(int zero, int one, LinkedList<Integer> path, LinkedList<LinkedList<Integer>> ans) {
if (zero == 0 && one == 0) {
LinkedList<Integer> cur = new LinkedList<>();
for (Integer num : path) {
cur.add(num);
}
ans.add(cur);
} else {
if (zero == 0) {
path.addLast(1);
process(zero, one - 1, path, ans);
path.removeLast();
} else if (one == 0) {
path.addLast(0);
process(zero - 1, one, path, ans);
path.removeLast();
} else {
path.addLast(1);
process(zero, one - 1, path, ans);
path.removeLast();
path.addLast(0);
process(zero - 1, one, path, ans);
path.removeLast();
}
}
}
public static long ways2(int N) {
if (N < 0) {
return 0;
}
if (N < 2) {
return 1;
}
long a = 1;
long b = 1;
long limit = N << 1;
for (long i = 1; i <= limit; i++) {
if (i <= N) {
a *= i;
} else {
b *= i;
}
}
return (b / a) / (N + 1);
}
public static void main(String[] args) {
System.out.println("test begin");
for (int i = 0; i < 10; i++) {
long ans1 = ways1(i);
long ans2 = ways2(i);
if (ans1 != ans2) {
System.out.println("Oops!");
}
}
System.out.println("test finish");
}
}