记录我的LeetCode答题框架。
我在LeetCode中答过的题代码全部托管在GitHub：xiaobai050/leetcode
最初在LeetCode上学习在线编程时，由于不熟练，脑中还没有答题的框架，测试用例、待提交代码、入口方法之间的耦合过大，添加、修改测试用例需要修改源代码，导致调试效率过低，不够优雅。
为了尽可能方便调试，高效编辑，分离测试用例和算法实现，改进整理出了自己顺手的答题框架，记录下来。万事开头难，如果能帮助到想我当初一样迷茫的初学者，就更好不过了:)
目录结构：
- LeetCode ——项目名称，方便Eclipse内置Git对代码进行管理和多终端同步
- pid1 ——题目包，每个题目封装在一个单独的包中，包名用LeetCode题目编号表示
- Solution.java ——算法类，注意到LeetCode每道题目的代码类名为Solution
- Main.java ——包含主函数（控制逻辑、测试用例数组）、测试函数（测试结果输出、算法耗时）
- pid2
以具体题目为例：96. Unique Binary Search Trees
- 拿到题目，首先在创建题目包pid96;
- 新建类：Main.java，并创建方法： main 和 test;
- 新建类：Solution.java，将算法方法代码用题目中原始代码进行替换，并添加默认返回值;
- 在main方法中新建测试用例数组，并循环调用测试方法test(input);
- 在test方法中实例化Solution类，执行算法，并在首尾计时统计运行时间。
代码内容如下：
main.java
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
| package pid96;
public class Main {
public static void main(String[] args) {
int[] testTable = { 0, 1, 2, 3, 4, 5, 6, 10 };
for (int input : testTable) {
test(input);
}
}
private static void test(int input) {
Solution solution = new Solution();
int output;
long begin = System.currentTimeMillis();
output = solution.numTrees(input);
long end = System.currentTimeMillis();
System.out.println(input + ": output=" + output);
System.out.println();
System.out.println("耗时：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
|
Solution.java
1
2
3
4
5
6
7
| package pid96;
public class Solution {
public int numTrees(int n) {
return 0;
}
}
|
接下来开始写算法，全部在Solution.java中完成。
完成后如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| package pid96;
public class Solution {
public int numTrees(int n) {
if(n<=1)return 1;
if(n==2)return 2;
int [] table= new int[n+1];
table[0]=1;
table[1]=1;
table[2]=2;
for(int i=2;i<n;i++){
for(int j=0;j<=i;j++){
table[i+1]+=table[i-j]*table[j];
}
}
return table[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
| 0: output=1
耗时：0ms
-------------------
1: output=1
耗时：0ms
-------------------
2: output=2
耗时：0ms
-------------------
3: output=5
耗时：0ms
-------------------
4: output=14
耗时：0ms
-------------------
5: output=42
耗时：0ms
-------------------
6: output=132
耗时：0ms
-------------------
10: output=16796
耗时：0ms
-------------------
|
