LeetCode答题框架(Java+Eclipse)

发表于 阅读次数：

记录我的LeetCode答题框架。

我在LeetCode中答过的题代码全部托管在GitHub：xiaobai050/leetcode

最初在LeetCode上学习在线编程时，由于不熟练，脑中还没有答题的框架，测试用例、待提交代码、入口方法之间的耦合过大，添加、修改测试用例需要修改源代码，导致调试效率过低，不够优雅。

为了尽可能方便调试，高效编辑，分离测试用例和算法实现，改进整理出了自己顺手的答题框架，记录下来。万事开头难，如果能帮助到想我当初一样迷茫的初学者，就更好不过了:)

目录结构：

  • LeetCode ——项目名称，方便Eclipse内置Git对代码进行管理和多终端同步
    • pid1 ——题目包，每个题目封装在一个单独的包中，包名用LeetCode题目编号表示
      • Solution.java ——算法类，注意到LeetCode每道题目的代码类名为Solution
      • Main.java ——包含主函数（控制逻辑、测试用例数组）、测试函数（测试结果输出、算法耗时）
    • pid2
      • Solution.java
      • Main.java

以具体题目为例：96. Unique Binary Search Trees

  1. 拿到题目，首先在创建题目包pid96;
  2. 新建类：Main.java，并创建方法： main 和 test;
  3. 新建类：Solution.java，将算法方法代码用题目中原始代码进行替换，并添加默认返回值;
  4. 在main方法中新建测试用例数组，并循环调用测试方法test(input);
  5. 在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
package pid96;

/**
 * Unique Binary Search Trees 
 * 
 * Given n, how many structurally unique BST's
 * (binary search trees) that store values 1...n?
 * 
 * For example, Given n = 3, there are a total of 5 unique BST's.
 * 
 *  1         3     3      2      1
 *   \       /     /      / \      \
 *    3     2     1      1   3      2
 *   /     /       \                 \
 *  2     1         2                 3
 *  
 * @author 白
 *
 */
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
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
-------------------