注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex210 Course Schedule II  

2015-05-24 20:59:08|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
和上一题几乎一样

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].



就是要在遍历过程中把删除节点的顺序给记录下来,加一个vector记录就可以了。

struct Node{
int in; //第一个维度表示她的入度
vector<int>request; //第二维度存需要“我”的节点
};

class Solution {
public:
vector<int> result;
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<Node>nodes(numCourses); //有多少门课程就有多少个节点
int len = 0;
len = prerequisites.size();
int i;
for (i = 0; i < numCourses; i++)
nodes[i].in = 0;
pair<int, int> current;
for (i = 0; i < len; i++)
{
//prerequisites的维数其实是二维的
current = prerequisites[i];
nodes[current.second].request.push_back(current.first);
//nodes[i]的req属性里面存的是需要i的节点,不要搞反了
nodes[current.first].in++;//入度 +1
}
queue<int> myQ;
for (i = 0; i < numCourses; i++)
{
if (nodes[i].in == 0)
{
myQ.push(i);
}
}
int index;
while (!myQ.empty())
{
index = myQ.front();
result.push_back(index);
myQ.pop();
len = nodes[index].request.size(); //需要index节点的课程都存在这里的request里面
for (i = 0; i < len; i++)
{
//这里挨个把需要index节点课程的入度都 -1
nodes[nodes[index].request[i]].in--;
if (nodes[nodes[index].request[i]].in == 0)
myQ.push(nodes[index].request[i]);
}
}
for (i = 0; i < numCourses; i++)
{
//最后检查时候还有入度大于0的课程
if (nodes[i].in > 0)
{
result.clear();
return result;
}

}
return result;
}
};


  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017