题目4：项目管理
题目描述：公司共有 n 个项目和 m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。我们用 group[i] 代表第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
- 同一小组的项目，排序后在列表中彼此相邻。
- 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
结果要求：
如果存在多个解决方案，只需要返回其中任意一个即可。
如果没有合适的解决方案，就请返回一个 空列表。
这题目乍一看就觉得挺难的，我们来理一理思路：
- 返回排序后的列表，实际上每一个任务都花一个单位的时间，任务串行来做，不考虑时间因素 。
- 同一个小组的项目排序后在列比中相邻：任务是以小组承包为单位打包进行调度的，这一个小组的所有项目开始之前，要消除其对于组外任务未进行任务的依赖。
Step1: 根据beforeItems建立邻接表itemsMap（Key:A, Set:A的依赖）, 扫描group数组建立邻接表groupMap
Step2: 统计入度为0的项目存到数组inCount, 把所有入度为0的无归属项目先做完。
Step3: 循环搜索项目全部入度为0的小组，迭代处理该小组的所有项目，注意更新inCount数组。
思考：实际上，题目的参数beforeItems已经为我们建立好了一个邻接表，其结构是A-->list（_需要在A之前完成的项目列表）。如果用这样的邻接表结构，后面每当我们处理一个入度为0的节点（项目时），需删除其他项目对他的依赖，此时需要遍历整个beforeItems，需要遍历n遍。于是我们将itemMap存储成B-->list（list:需要在B之后开始的项目列表）
再思考：前面Step3"搜索项目全部入度为0的小组"实际上是可能不存在的，而这时却有可能存在解，此时我们是允许合理的组内依赖的，所以到此为止我才真正理解了这道题：如何管理组，识别组间依赖，管理组内依赖。
于是很难受地重新整理思路：
- 建立节点的正邻接表、组和节点的入度表，节点入度只计算来自组内的，组入度对每个组计算一次，而不是每一个外部节点计算一次
- 先对组进行拓扑排序并保存排序好的组索引
- 对排序好的组，对每个组内的节点进行拓扑排序，并保存结果
class Solution { class Graph { Map<Integer,List<Integer>> map; Map<Integer,List<Integer>> reverseMap; public Graph(int n) { map = new HashMap<>(); reverseMap = new HashMap<>(); for(int i=0;i<n;i++) { map.put(i,new ArrayList<>()); reverseMap.put(i,new ArrayList<>()); } } public Graph(List<Integer> list) { map = new HashMap<>(); reverseMap = new HashMap<>(); for(int i:list) { map.put(i,new ArrayList<>()); reverseMap.put(i,new ArrayList<>()); } } public void insert(int a,int b) { map.get(a).add(b); reverseMap.get(b).add(a); } public List<Integer> getTopu() { List<Integer> ans = new LinkedList<>(); Map<Integer,Integer> rudu =new HashMap<>(); for(Map.Entry<Integer,List<Integer>> entry : reverseMap.entrySet()) { rudu.put(entry.getKey(),entry.getValue().size()); } Queue<Integer> queue = new LinkedList<>(); for(Map.Entry<Integer,Integer> entry : rudu.entrySet()) { if(entry.getValue()==0) { ans.add(entry.getKey()); queue.offer(entry.getKey()); } } while(!queue.isEmpty()) { int tmp = queue.poll(); List<Integer> list = map.get(tmp); for(int i:list) { int du= rudu.get(i); if(du==0) continue; if(du==1) { rudu.put(i,0); ans.add(i); queue.offer(i); }else{ rudu.put(i,du-1); } } } return ans; } } public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) { //首先分组 //建立一个图，组号组成的图 int index = m; for(int i=0;i<n;i++) { if(group[i]==-1) { group[i] = index++; } } Map<Integer,List<Integer>> mmm = new HashMap<>(); for(int i=0;i<index;i++) { mmm.put(i,new ArrayList<>()); } for(int i=0;i<n;i++) { mmm.get(group[i]).add(i); } Graph graph = new Graph(index); Graph[] graphs = new Graph[index]; for(int i=0;i<index;i++) { graphs[i] = new Graph(mmm.get(i)); } for(int i=0;i<n;i++) { int right = group[i]; List<Integer> list = beforeItems.get(i); for(int j:list) { int left = group[j]; if(left!=right) { graph.insert(left,right); }else{ graphs[left].insert(j,i); } } } List<Integer> zuSort = graph.getTopu(); if(zuSort.size()<index) return new int[]{}; int[] ans = new int[n]; int ind = 0; for(int i:zuSort) { List<Integer> tmp = graphs[i].getTopu(); if(tmp.size()<mmm.get(i).size()) return new int[]{}; for(int j:tmp) { ans[ind++]=j; } } return ans; } }
反思一波：最开始建立思路写123步的时候太草率了，想简单了不够严谨。没有考虑到组间依赖普遍存在的问题，没能抓住这道题的核心点在哪里。
OK，fine 确实是一道很复杂的题，以后有必要重新再做一遍。
题目3：课程表ii
现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
（就是在题目二的基础上存储课程列表，没有什么可说的，在Map/Set/Entry这遍历转换时候总是有编译错误，要靠提示才理得清，还是要多用HashMap 和 Set多熟悉呀）
代码如下，基本和前面的差不多。拓扑排序的题目要看清楚输入的有序对到底是谁依赖了谁，理清关系之后再决定如何存储邻接表。
import java.util.Map.*;
import java.util.Set.*;
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, HashSet<Integer>> map = new HashMap<>();
int[] res = new int[numCourses];
int i, j, cur, pos = 0;
if(prerequisites.length==0){
for(i = 0; i<numCourses; i++)
res[i] = i;
return res;
}
//step1建立邻接表
for(i = 0; i<prerequisites.length; i++){
if(map.containsKey(prerequisites[i][1])){
map.get(prerequisites[i][1]).add(prerequisites[i][0]);
} else{
HashSet<Integer> set = new HashSet<>();
set.add(prerequisites[i][0]);
map.put(prerequisites[i][1], set);
}
}
//统计入度
int[] inCount = new int[numCourses];
Set<Entry<Integer, HashSet<Integer>>> entrySet = map.entrySet();
for(Entry<Integer, HashSet<Integer>> entry:entrySet){
for(Integer to : entry.getValue()){
inCount[to]++;
}
}
//step2循环得到入度为0的节点入队，处理队中节点
while(!map.isEmpty()){
Queue<Integer> queue = new LinkedList<Integer>();
//入度为0的节点进队
for(i = 0; i<numCourses; i++){
if(inCount[i]==0){
queue.offer(i);
inCount[i]--;
}
}
if(queue.isEmpty() && !map.isEmpty()){
return new int[0];
}
//处理入度为0节点
while(!queue.isEmpty()){
cur = queue.remove();
res[pos++] = cur;
if(map.containsKey(cur)){
for(Integer to : map.get(cur)){
inCount[to]--;
if(!map.containsKey(to)){
map.put(to, new HashSet<Integer>());
}
}
map.remove(cur);
}
}
}//while
return res;
}
}题目2：课程表
题目描述：你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]。给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
本题思路：通过拓扑排序判断此课程安排图是否是有向无环图(DAG)
第一次做：邻接表存储图，普通拓扑排序。
用Map<Integer, HashSet<integer>>存储邻接表，解题思路就根据拓扑排序的基本思想具体分为三步：
Step1: 建立邻接表
Step2: 统计入度为0的节点
Step3: 处理入度为0的节点，循环至step2直到处理完所有节点
我这里是用队列来存储待处理的入度为0的节点，需要注意的是统计过的入度为0的节点，经过处理后要进行标记，防止其重复入队。我用一个dead数组显然是比较笨的方法，实际上用原来的入度标记数组inCount--（=-1）来标记处理过的节点就可以了。</integer>
import java.util.Map.*;
import java.util.Set.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, HashSet<Integer>> map = new HashMap<>();
int[] dead = new int[numCourses];
int i, j, cur;
//step1建立邻接表
for(i = 0; i<prerequisites.length; i++){
if(map.containsKey(prerequisites[i][0])){
map.get(prerequisites[i][0]).add(prerequisites[i][1]);
} else{
HashSet<Integer> set = new HashSet<>();
set.add(prerequisites[i][1]);
map.put(prerequisites[i][0], set);
}
}
//step2循环得到入度为0的节点入队，处理队中节点
while(!map.isEmpty()){
Queue<Integer> queue = new LinkedList<Integer>();
//统计入度
int[] inCount = new int[numCourses];
Set<Entry<Integer, HashSet<Integer>>> entrySet = map.entrySet();
for(Entry<Integer, HashSet<Integer>> entry:entrySet){
for(Integer to : entry.getValue()){
inCount[to]++;
}
}
//入度为0的节点进队
for(i = 0; i<numCourses; i++){
if(inCount[i]==0 && dead[i]==0)
queue.offer(i);
}
if(queue.isEmpty() && !map.isEmpty())
return false;
//处理入度为0节点
while(!queue.isEmpty()){
cur = queue.remove();
map.remove(cur);
dead[cur]=1;
}
}//while
return true;
}
}通过需要223ms，观察发现统计入度的循环其实不用放在大的while循环里面，入度其实可以在每一次while循环处理的时候进行更新，这样优化了算法的时间复杂度。
优化后提交，通过需要21ms。
题目1：节点间通路
第一次做：普通递归（超时）
没有搜索算法思想在里面，就是一个普通递归，因为直接写出来递归会超时，就加了一个path记录，用在if条件判断处，用来减少递归次数，然而依然超时。
class Solution {
boolean res = false;
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target){
int[][] path = new int[n][n];
for(int i = 0; i<graph.length; i++){
path[graph[i][0]][graph[i][1]] = 1;
}
return checkPath(path, start, target);
}
public boolean checkPath(int[][] path, int begin, int target){
if(path[begin][target]==1){
return true;
}
for(int i = 0; i<target; i++){
if((path[begin][i]==1||checkPath(path, begin, i))&&(path[i][target]==1||checkPath(path, i, target))){//减少递归次数
path[begin][target] = 1;
return true;
}
}
return false;
}
}第二次做：数组邻接矩阵+DFS思想
为什么超时呢？可能是这种分治思想还是递归次数太多，那么用深度优先的思路还是递归的方式来做一下吧。
class Solution {
//普通递归思路改造成深度优先搜索
boolean res = false;
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target){
int[][] path = new int[n][n];
for(int i = 0; i<graph.length; i++){
path[graph[i][0]][graph[i][1]] = 1;
}
return checkPath(path, start, start, target);
}
public boolean checkPath(int[][] path, int start, int begin, int target){
if(path[begin][target]==1){
return true;
}
for(int i = 0; i<target; i++){
if(path[begin][i] == 1){//减少递归次数
path[start][i] = 1;
if(path[i][target]==1){
return true;
}
else if(checkPath(path, i, target)){
path[i][target] = 1;
return true;
}
}
}
return false;
}
}结果，在最后一条数据n=100000的时候超出内存限制
第三次做：Map实现邻接表+DFS
为什么会在最后一条数据n=100000的时候超出内存限制？我认为原因是不能够使用邻接矩阵吧，有太多的冗余，采用邻接表结构会节省很多内存，虽然搜索时间复杂度会*k倍。
class Solution {
//邻接矩阵改成邻接表，用Map来实现
boolean res = false;
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target){
Map<Integer, HashSet<Integer>> map = new HashMap<>();
// graph[i][0]--指向-->graph[i][1]
for(int i = 0; i<graph.length; i++){
int from = graph[i][0];
int to = graph[i][1];
if(map.containsKey(from)){
map.get(from).add(to);
} else {
HashSet<Integer> set = new HashSet<>();
set.add(to);
map.put(from, set);
}
}
return searchBFS(map, start, target);
}
private boolean searchDFS(Map<Integer, HashSet<Integer>> map, int start, int target){
if(start==target)
return true;
HashSet<Integer> set = map.get(start);
if(set==null || set.isEmpty()){
return false;
}
for(Integer to:set){
if(searchDFS(map, to, target))
return true;
}
return false;
}
}
京公网安备 11010502036488号