leetcode中的图问题I

  1. Course Schedule
    总共有n个课程,用0~n-1来表示,给定一个课程先修后修的表,判断是否合理
    [0,1]表示如果要修课程0,必须先修课程1
    [[1,0],[0,1]]表示如果要修1,必须先修0;如果要修0,必须先修1,矛盾,不合理
  2. Course Schedule II
    按顺序输出任意一种图的先修后修路线
    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, return the ordering of courses you should take to finish all courses.
    There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
    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 the correct course order is [0,1]
    4, [[1,0],[2,0],[3,1],[3,2]]
    There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is[0,1,2,3]. Another correct ordering is[0,2,1,3].
  3. For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
    Format
    The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
    You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
    Example :
    Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
    1
    2
    3
    4
    5
    6
    7
    8
    0 1 2
    \ | /
    3
    |
    4
    |
    5
    return [3, 4]

第1,2两道题的图问题,就是判断是否有环,然后输出先后顺序,用拓扑排序,可以解决。
第3题的思想和拓扑排序有点像,就是找叶子节点,然后不断删除,重复上面的过程,将最后剩下小于等于2的节点返回。

[leetcode 207] Course Schedule

摘抄一段拓扑排序的思想,详细参见leetcode Graph 图论
拓扑排序的做法如下:

  1. 每次找入度为0的点,输出该入度为0的点,并删除与之相连接的边
  2. 重复1直到没有入度为0的点。之前输出入度为0的点若小于原图的结点数,那么说明图有环,即拓扑排序不存在,否则即为拓扑排序

然后照着上面的原理写了下面的代码,写的并不好,leetcode上勉强通过,主要是为了熟悉拓扑排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer,List<Integer>> map=new HashMap<>();
int[] number=new int[numCourses];
Stack<Integer> stack=new Stack<>();
for(int i=0;i<prerequisites.length;i++){
if(!map.containsKey(prerequisites[i][0]))map.put(prerequisites[i][0],new ArrayList<>());
map.get(prerequisites[i][0]).add(prerequisites[i][1]);
number[prerequisites[i][0]]++;
}
for(int i=0;i<numCourses;i++)if(number[i]==0)stack.push(i);
while (!stack.isEmpty()){
int temp=stack.pop();
for(Map.Entry<Integer,List<Integer>> entry:map.entrySet()){
if(entry.getValue().contains(temp)){
entry.getValue().remove(new Integer(temp));
number[entry.getKey()]--;
if(number[entry.getKey()]==0)stack.push(entry.getKey());
}
}
}
for(int i=0;i<numCourses;i++)if(number[i]!=0)return false;
return true;
}

[leetcode 210] Course Schedule II

这个代码和前面的没有什么区别,前面本来是应该用队列的,用队列的话,可以直接输出结果

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
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer,List<Integer>> map=new HashMap<>();
int[] number=new int[numCourses];
Queue<Integer> queue=new LinkedList<>();
int[] res=new int[numCourses];
int k=0;
for(int i=0;i<prerequisites.length;i++){
if(!map.containsKey(prerequisites[i][0]))map.put(prerequisites[i][0],new ArrayList<>());
map.get(prerequisites[i][0]).add(prerequisites[i][1]);
number[prerequisites[i][0]]++;
}
for(int i=0;i<numCourses;i++)if(number[i]==0)queue.add(i);
while (!queue.isEmpty()){
int temp=queue.poll();
res[k++]=temp;
for(Map.Entry<Integer,List<Integer>> entry:map.entrySet()){
if(entry.getValue().contains(temp)){
entry.getValue().remove(new Integer(temp));
number[entry.getKey()]--;
if(number[entry.getKey()]==0)queue.add(entry.getKey());
}
}
}
if(k==numCourses)return res;
return new int[0];
}

[leetcode 310] Minimum Height Trees

这道题的意思就是找到一个中间节点(或者是两个),以这个节点的权重为0向外延伸,每过一个节点,就加1,然后将这些节点的权重相加,使之最小。有点像BFS,遍历每个节点,然后每次将节点入队,并附上权重,最后找到最小的权重和对应的节点,返回。discuss排名第一的答案给出的是反向实现的方法,每次找叶子节点,然后删除,找出一下轮的叶子节点,如果剩下的节点小于等于2,就返回这些节点,否则,继续删除,知道满足剩下的节点小于等于2,返回。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<HashSet<Integer>>list=new ArrayList<>();
if(n==1){List<Integer>list1=new ArrayList<>();list1.add(0);return list1;}
for(int i=0;i<n;i++)list.add(new HashSet<>());
for(int[] edg:edges){list.get(edg[0]).add(edg[1]);list.get(edg[1]).add(edg[0]);}
List<Integer> levels=new ArrayList<>();
for(int i=0;i<n;i++)if(list.get(i).size()==1)levels.add(i);
while (n>2){
n-=levels.size();
List<Integer> newLevels=new ArrayList<>();
for(int i:levels){
int temp=list.get(i).iterator().next();
list.get(temp).remove(i);
if(list.get(temp).size()==1)newLevels.add(temp);
}
levels=newLevels;
}
return levels;
}

我解释一下这个代码,用一个列表记录每个节点所连接的节点标号,用set存储,当对应节点的set等于1,说明是叶子节点,那么将这些叶子节点进行缩进(也就是删除,也可以说是有一个指针从叶子节点开始向前走),这样肯定会产生新一轮的叶子节点…

如果觉得有帮助,给我打赏吧!