第三期Task-LeetCode算法题

发表于

第三期Task-LeetCode算法题

3Sum

先附上题目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

看到这道题我的第一想法就是用调用2Sum函数来写，但是发现2Sum返回的是索引，而这题需要的是数值。想通这点之后就意识到了重复查找的问题。

因为2Sum是用的hash表做的，速度还不错，因此最开始我的想法也还是用hash来写。然后有了如下的solution1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> for_return = new LinkedList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i != 0 && nums[i] == nums[i-1]) continue;
            Hashtable hashtable = new Hashtable();
            for(int j = i + 1; j < nums.length; j++){
                int tag = 0 - nums[i] - nums[j];
                if(hashtable.containsKey(tag)){
                    if((int)hashtable.get(tag) == 0){
                        for_return.add(Arrays.asList(nums[i],tag,nums[j]));
                        hashtable.replace(tag, 0, 1);
                    }
                }
                else hashtable.put(nums[j] , 0);
            }
        }
        return for_return;
    }

首先，调用了Arrays类的方法sort对nums数组进行排序。然后进入外部循环，循环体内的第一句是后续优化时加上的，因为排序之后，当最小的数都大于0，结果一定大于0，所以也就不需要继续判断了（加上这句才AC的）。第二句是防止重复（因为已经排序好了，相同的数已经放在了一起，所以很容易跳过不需要判断的重复数）。在内部循环中，从索引i+1开始，使用类似2Sum的hash解法的方法判断结果。为了避免重复，在每个数第一次进入hash表时，给的值是0，然后在这个数被使用之后，调用replace方法，把值修改为1，下次不再使用这组数。

这里贴上2Sum的hash解法 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] twoSum(int[] nums, int target) {
        Hashtable hashtable = new Hashtable();
        int for_return[] = new int[2];
        for(int i = 0;i < nums.length;i++){
            int tag = target - nums[i];
            if(hashtable.containsKey(tag)){
                for_return[0] = (int)hashtable.get(tag);
                for_return[1] = i;
                break;
            }
            hashtable.put(nums[i],i);
        }
        return for_return;
    }

这个解法跑完之后险险AC（多次优化后421ms），但是只beat了2.31%。然后我就去看了看这题的标签，2333竟然在Two Pointer里面。然后才有了solution2。

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
public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> for_return = new LinkedList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i != 0 && nums[i] == nums[i-1]) continue;
            int low = i + 1, high = nums.length -1;
            while(low < high){
                if(nums[i] + nums[low] + nums[high] >0){
                    high--;
                }
                else if(nums[i] + nums[low] + nums[high] < 0){
                    low++;
                }
                else{
                    for_return.add(Arrays.asList(nums[i],nums[low],nums[high]));
                    while(low < high && nums[low] == nums[low + 1]) low++;
                    while(low < high && nums[high] == nums[high - 1]) high--;
                    low++;
                    high--;
                }
            }
        }
        return for_return;
    }

这个思考的时间比hash长。但是感觉这个代码比hash要优雅。最主要的是时间短…一下子就77ms。

  • [x] 一味的使用hash表也不一定好，能不查找就不查找。

Climbing Stairs

emmm去年c语言大赛做过这道题，从后往前分析一下就是简单的斐波那契数列。附上代码走人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        int first = 1;
        int second = 1;
        int temp;
        for(int i = 1; i < n; i++){
            temp = second;
            second += first;
            first = temp;
        }
        return second;
    }

Course Schedule

先上题目

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

拓扑排序：

  1. 在有向图中选择一个没有前驱的节点进行操作。
  2. 从有向图中删除该顶点和所有以它为尾的弧。
  3. 重复1&2
  4. 之后两种情况，a.所有节点均被操作过–>没有环（也就是可以修完所有科目），b.存在没有被操作过的节点–>有环（准备收到一个环的你能做的岂止于此）。

那么思路其实就是判断第四步进入a还是b了。

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
       List<List<Integer>> edges = new LinkedList<>();
        int[] in = new int[numCourses];
        List<Integer> temp;
        Queue<Integer> queueForFS = new LinkedList<>();
        int FScounter = 0;
		for (int i = 0; i < numCourses; i++) {
			temp = new LinkedList<>();
			edges.add(temp);	
		}
		for (int i = 0; i < prerequisites.length; i++){
			edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
		}
        for (int i = 0; i < prerequisites.length; i++) {
			in[prerequisites[i][0]]++;
		}
        for (int i = 0; i < numCourses; i++) {
			if(in[i] == 0){
				queueForFS.offer(i);
			}
		}
        while(!queueForFS.isEmpty()){
        	FScounter++;
        	for (int i : edges.get(queueForFS.poll())) {
				in[i]--;
				if(in[i] == 0){
					queueForFS.offer(i);
				}
			}
        }
        return FScounter == numCourses;
    }

第一个循环初始化List>。第二个循环建立表。第三个循环统计入度。第四个循环将所有没有前驱的节点入队。准备工作完成之后，就可以进行环的判断。这里使用了一个FScounter来统计遍历过的节点数量。（至今没搞清楚foreach循环和for循环哪个快…）

MinStack

开始觉得不优雅，不想用第二个List来实现。然后就…各种尴尬，最后还是妥协了。另外真的觉得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
public class MinStack {
    private List<Integer> head;
    private List<Integer> mIntegers;
    /** initialize your data structure here. */
    public MinStack() {
        head = new LinkedList<>();
        mIntegers = new LinkedList<>();
    }
    
    public void push(int x) {
        head.add(0,x);
        if(mIntegers.isEmpty() || x <= getMin()){
        	mIntegers.add(0,x);
        }
    }
    
    public void pop() {
    	if(!head.isEmpty()){
    		if(head.get(0) == getMin())
    			mIntegers.remove(0);
    		head.remove(0);
    	}
    }
    
    public int top() {
        return head.get(0);
    }
    
    public int getMin() {
        return mIntegers.get(0);
    }
}