系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

【英雄哥六月集训】第 22天: 有序集合

【英雄哥六月集训】第 23天: 字典树

【英雄哥六月集训】第 24天: 线段树

【英雄哥六月集训】第 25天: 树状数组

【英雄哥六月集训】第 26天: 并查集

【英雄哥六月集训】第 27天: 图

【英雄哥六月集训】第 28天: 动态规划

【英雄哥六月集训】第 29天: 分而治之

【英雄哥六月集训】第 30天: 拓扑排序

---

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

一、 从给定原材料中找到所有可以做出的菜

2115. 从给定原材料中找到所有可以做出的菜

class Solution {
    Map<String,Boolean> has = new HashMap();
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        int i,j;
        List<String> ans = new ArrayList<String>();
        for(i=0;i<supplies.length;++i){
            has.put(supplies[i],true);
        }
        boolean flag=true;
        while(flag){
            flag=false;
            for(i=0;i<recipes.length;i++){
                if(has.containsKey(recipes[i])){
                    continue;
                }
                for(j=ingredients.get(i).size()-1;j>=0;--j){
                    if(!has.containsKey(ingredients.get(i).get(j))){
                        break;
                    }
                }
                if(j==-1){
                    has.put(recipes[i],true);
                    ans.add(recipes[i]);
                    flag=true;

                }
            }
        }
        return ans;

    }
}
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

---

二、 重建序列

剑指 Offer II 115. 重建序列

class Solution {
    int maxn=10010;
    int[] deg=new int[maxn];
    List<List<Integer>> edge = new ArrayList<List<Integer>>(maxn);
    public void initEdgeArray(){
        for(int i=0;i<maxn;i++){
            edge.add(new ArrayList<Integer>());
        }
    }
    public void addEdge(int u,int v){
        ++deg[v];
        edge.get(u).add(v);
    }
    public boolean sequenceReconstruction(int[] nums, int[][] seqs) {
        int i,j;
        Deque<Integer> q = new ArrayDeque<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        initEdgeArray();
        for(i=0;i<seqs.length;++i){
            for(j=1;j<seqs[i].length;++j){
                addEdge(seqs[i][j-1],seqs[i][j]);
            }
        }
        

        for(i=1;i<=nums.length;++i){
            if(deg[i]==0){
                q.add(i);
                ans.add(i);
            }
        }
        
        if(q.size()>1){
            return false;
        }
        
        while(!q.isEmpty()){
            System.out.println(q);
            Integer u = q.removeFirst();
            for(i=0;i<edge.get(u).size();++i){
                Integer v = edge.get(u).get(i);
                if((--deg[v])==0){
                    q.add(v);
                    ans.add(v);
                }
            }
            if(q.size()>1){
                return false;
            }
        }
        //System.out.println(ans);
        if(nums.length>ans.size()){
            return false;
        }
        for(i=0;i<nums.length;++i){
            if(ans.get(i)!=nums[i]){
                return false;
            }
        }
        return true;
        

    }
}
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

三、 课程表 IV

1462. 课程表 IV
先用拓扑排序写了一版,结果超时,实在不会改了

class Solution {
    int maxn=110;
    Map<Integer, List<Integer>> edges = new HashMap<Integer,List<Integer>>();
    Map<Integer, List<Integer>> go = new HashMap<Integer,List<Integer>>();
    int[] vis = new int[maxn];
    

    void addEdge(int u,int v){
        edges.putIfAbsent(u,new ArrayList<Integer>());
        edges.get(u).add(v);
    }
    void dfs(int u,List<Integer> go){
        //{0=[1, 2], 2=[1]} 对于 0,1,2 来说的通路
        
        //vis[go.get(u)]=1;
            //System.out.println(u);
        go.add(u);
            
        if(edges.containsKey(u)){
            for(int i =0;i<edges.get(u).size();++i){
                //if (vis[edges.get(u).get(i)]==0){
                    dfs(edges.get(u).get(i),go);
                //}
            }
            
        }
    
    }

    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        int i,j;
        List<Boolean> ans=new ArrayList<Boolean>();
        for(i=0;i<prerequisites.length;++i){
            int u = prerequisites[i][0];
            int v = prerequisites[i][1];
            addEdge(v,u);
        }
        //System.out.println(edges); //{0=[1, 2], 2=[1]}
        for(i=0;i<numCourses;++i){
            go.putIfAbsent(i,new ArrayList<Integer>());
            dfs(i,go.get(i));  
        }
        System.out.println(go);
        for(i =0;i<queries.length;++i){
            int u = queries[i][0];
            int v = queries[i][1];
            Boolean flag = false;
            
            for(j=0;j<go.get(v).size();++j){
                if(go.get(v).get(j)==u){
                    flag=true;
                }
            }
            ans.add(flag);
        }
        return ans;
        

    }
}
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

最后还是用了 floyed 算法

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {

          /*
               floyed[i][j] 
               if there is path from i to j

          */

          boolean[][] floyed = new boolean[numCourses][numCourses];

          for(int [] pre : prerequisites){
               floyed[pre[0]][pre[1]] = true;
          }

          for(int mid = 0; mid < numCourses; mid++){

               for(int i = 0; i < numCourses; i++){

                    for(int j = 0; j < numCourses; j++){

                         floyed[i][j] = floyed[i][j]|| (floyed[i][mid] && floyed[mid][j]);
                    }
               }
          }

          List<Boolean> result = new ArrayList<>();

          for(int[] query : queries){

               int i = query[0];
               int j = query[1];

               result.add(floyed[i][j]);
          }
          return result;

    }
}

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

四、 外星文字典

剑指 Offer II 114. 外星文字典

class Solution {
    static final int VISITING = 1,VISITED = 2;
    Map<Character, List<Character>> edges = new HashMap<Character,List<Character>>();
    Map<Character, Integer> states = new HashMap<Character,Integer>();
    boolean valid = true;
    char[] order;
    int index;

    void addEdge(String before, String after){
        int length1 = before.length(),length2 = after.length();
        int length = Math.min(length1,length2);
        int index = 0;
        while(index < length){
            char c1 = before.charAt(index), c2 = after.charAt(index);
            if(c1 != c2){
                edges.get(c1).add(c2);
                break;
            }
            index++;
        }
        if(index == length && length1>length2){
            valid = false;
        }
    }
    void dfs(char u){
        states.put(u,VISITING);
        List<Character> adjacent = edges.get(u);
        for(char v:adjacent){
            if(!states.containsKey(v)){
                dfs(v);
                if(!valid){
                    return ;
                }
            } else if(states.get(v)==VISITING){
                valid = false;
                return ;
            }
        }
        states.put(u,VISITED);
        order[index]=u;
        index--;
    }
    public String alienOrder(String[] words) {
        int length = words.length;
        for( String word: words){
            int wordLength = word.length();
            for( int j=0;j<wordLength; j++){
                char c = word.charAt(j);
                edges.putIfAbsent(c,new ArrayList<Character>());
            }
        }
        for( int i=1;i<length&& valid ;i++){
            addEdge(words[i-1],words[i]);
        }
        order = new char[edges.size()];
        index = edges.size()-1;
        Set<Character> letterSet = edges.keySet();
        for(char u:letterSet){
            if(!states.containsKey(u)){
                dfs(u);
            }
        }
        if(!valid){
            return "";
        }
        return new String(order);

    }
}
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

总结