NC316. 体育课测验(二)
描述
示例1
输入:
3,[[2,1]]
输出:
[1,2,0]
说明:
要先完成1号项目，再完成2号项目，而0号项目不受约束，故可以以1 2 0的顺序完成项目。示例2
输入:
3,[[1,0], [0,1]]
输出:
[]
说明:
第一个分组要求先完成0号项目，再完成1号项目；而第二个分组要求先完成1号项目，再完成0号项目，自相矛盾，故不可以完成项目。C 解法, 执行用时: 15ms, 内存消耗: 1824KB, 提交时间: 2022-06-25
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numProject int整型
* @param groups int整型二维数组
* @param groupsRowLen int groups数组行数
* @param groupsColLen int* groups数组列数
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdio.h>
#include <stdbool.h>
bool dfs(int current, int *history, int historyIndex, int *visited, int** groups, int groupsRowLen, int *tmpSubResult, int *tmpSubResultLen) {
visited[current] = 1;
history[historyIndex] = current;
for (int i = 0; i < groupsRowLen; i++) {
if (groups[i][0] == current) {
for (int j = 0; j < historyIndex + 1; j++) {
if (groups[i][1] == history[j]) {
return false;
}
}
if (visited[groups[i][1]] == 0) {
bool result = dfs(groups[i][1], history, historyIndex + 1, visited, groups, groupsRowLen, tmpSubResult, tmpSubResultLen);
if (!result) {
return false;
}
}
}
}
tmpSubResult[(*tmpSubResultLen)++] = current;
return true;
}
int* findOrder(int numProject, int** groups, int groupsRowLen, int* groupsColLen, int* returnSize ) {
int visited[numProject];
memset(visited, 0, sizeof(visited));
int tmpResult[numProject], tmpResultIndex = 0, tmpSubResult[numProject], tmpSubResultLen;
int history[numProject];
for (int i = 0; i < numProject; i++) {
if (visited[i] == 0) {
tmpSubResultLen = 0;
int result = dfs(i, history, 0, visited, groups, groupsRowLen, tmpSubResult, &tmpSubResultLen);
if (!result) {
*returnSize = 0;
return NULL;
} else {
for (int k = 0; k < tmpSubResultLen; k++) {
tmpResult[tmpResultIndex++] = tmpSubResult[k];
}
}
}
}
*returnSize = numProject;
int *result = (int *)malloc(sizeof(int) * numProject);
for (int i = 0; i < numProject; i++) {
result[i] = tmpResult[i];
}
return result;
}
C++ 解法, 执行用时: 15ms, 内存消耗: 2208KB, 提交时间: 2022-06-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numProject int整型
* @param groups int整型vector<vector<>>
* @return int整型vector
*/
vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
// write code here
vector<vector<int>> deps(numProject,vector<int>());
vector<int> degree(numProject,0);
for(int i=0;i<groups.size();i++){
int x=groups[i][0];
int y=groups[i][1];
deps[y].push_back(x);
degree[x]++;
}
queue<int> q;
vector<int> result;
for(int i=0;i<numProject;i++)
if(degree[i]==0){
q.push(i);
}
while(!q.empty()){
int n=q.size();
for(int i=0;i<n;i++){
int x=q.front();
q.pop();
result.push_back(x);
for(int i=0;i<deps[x].size();i++){
degree[deps[x][i]]--;
if(degree[deps[x][i]]==0) q.push(deps[x][i]);
}
}
}
return result.size()==numProject?result:vector<int>();
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2292KB, 提交时间: 2022-04-08
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numProject int整型
* @param groups int整型vector<vector<>>
* @return int整型vector
*/
vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
// write code here
vector<int> du(numProject,0);
vector<vector<int>> line(numProject);
int n=groups.size();
for(int i=0;i<n;i++){
du[groups[i][0]]++;
line[groups[i][1]].push_back(groups[i][0]);
}
queue<int> qu;
for(int i=0;i<numProject;i++){
if(du[i]==0){
qu.push(i);
}
}
if(qu.empty()==true){
return {};
}
int cnt=0;
vector<int> ans;
while(qu.empty()==false){
int ind=qu.front();
qu.pop();
ans.push_back(ind);
cnt++;
int len=line[ind].size();
for(int i=0;i<len;i++){
du[line[ind][i]]--;
if(du[line[ind][i]]==0){
qu.push(line[ind][i]);
}
}
}
if(cnt==numProject){
return ans;
}
return {};
}
};
C++ 解法, 执行用时: 16ms, 内存消耗: 2252KB, 提交时间: 2022-04-19
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numProject int整型
* @param groups int整型vector<vector<>>
* @return int整型vector
*/
vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
// write code here
visited.assign(numProject, false);
onPath.assign(numProject, false);
hasCircle = false;
auto graph = buildGraph(numProject, groups);
for (int i = 0; i < numProject; ++i) {
DFS(graph, i);
}
if (hasCircle) return {};
reverse(path.begin(), path.end());
return path;
}
private:
vector<vector<int>> buildGraph(int numProject, const vector<vector<int>>& groups) {
vector<vector<int>> graph(numProject);
for (const auto& num : groups)
graph[num[1]].push_back(num[0]);
return graph;
}
void DFS(const vector<vector<int>>& graph, int s) {
if (onPath[s]) hasCircle = true;
if (visited[s] || hasCircle) return;
visited[s] = true;
onPath[s] = true;
for (int v : graph[s])
DFS(graph, v);
path.push_back(s);
onPath[s] = false;
}
vector<bool> visited;
vector<bool> onPath;
bool hasCircle;
vector<int> path;
};
C++ 解法, 执行用时: 16ms, 内存消耗: 2264KB, 提交时间: 2022-06-29
class Solution {
private:
vector<vector<int>> edges;
vector<int> visited;
vector<int> result;
bool valid = true;
public:
void dfs(int u) {
visited[u] = 1;
for (int v : edges[u]) {
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
} else if (visited[v] == 1) {
valid = false;
return;
}
}
visited[u] = 2;
result.push_back(u);
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numProject int整型
* @param groups int整型vector<vector<>>
* @return int整型vector
*/
vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
// write code here
edges.resize(numProject);
visited.resize(numProject);
for (const auto& info : groups) {
edges[info[1]].push_back(info[0]);
}
for (int i = 0; i < numProject && valid; ++i) {
if (!visited[i]) {
dfs(i);
}
}
if (!valid) {
return {};
}
reverse(result.begin(), result.end());
return result;
}
};