【054_week3】学习总结

[taolei0108]

这次的week03 很多超出了我之前学的算法范围，dfs和bfs和图都是我之前没学过的，都是看着争哥的专栏边学边写，说实话，图我还能看懂，自己写了出来，但是dfs和bfs我都是最后写不出来借鉴的别人的方法，自己又写了一遍。下面我就说说我写的图的那题Find the Town Judge的解决方法。

class Solution {
    public int findJudge(int N, int[][] trust) {
        if(N == 1) return 1;
        Map<Integer, Integer> map = new HashMap();
        //将所有的备选法官记录下来，包括他们的入度
        for(int[] aaa: trust){
            if(map.get(aaa[1]) == null){
                map.put(aaa[1], 0);
            }
            int num = map.get(aaa[1]);
            map.put(aaa[1], num+1);
        }
        
        //移除相信别人的候选法官
        for(int[] aaa: trust){
            if(map.get(aaa[0]) != null){
                map.remove(aaa[0]);
            }
        }
        
        // 当入度达到N-1时，就是最终的法官
        for(int key : map.keySet()){
            if(map.get(key) == N-1){
                return key;
            }
        }
        
        return -1;
    }
}

上面的方法是我自己想的，比较暴力，循环3次，先把有入度的都记下来，key是label，value是入度的次数，然后第2次遍历是把有出度的key给删了，第3次遍历是看哪个key的value值等于N-1，那这个key就是法官，比较耗内存和cpu。

方法二：

class Solution {
    public int findJudge(int N, int[][] trust) {
        int[][] people = new int[N][2];
        for(int[] person : trust){
            int out = person[0];
            int in = person[1];
            people[out - 1][0] ++;
            people[in - 1][1] ++;
        }
        for(int i = 0; i < N; i ++){
            if(people[i][0] == 0 && people[i][1] == N - 1)
                return i + 1;
        }
        return -1;
    }
}

是用一个二维数组将入度和出度都记下来，最后判断出度为0且入度为N-1的label为法官，这个就比我自己想的简单很多，资源使用也少。

方法三：

class Solution {
    public int findJudge(int N, int[][] trust) {
        int[] people = new int[N];
        for(int[] aaa : trust){
            people[aaa[1]-1] ++;
            people[aaa[0]-1] --;
        }
        for(int i = 0; i < N; i ++){
            if(people[i] == N - 1)
                return i+1;
        }
        return -1;
    }
}

和方法二相比很类似，但是更简便，用一维数组即可记录入度为N-1的值