关于namespace的使用

题目:

关于namespace的使用

基于宽度优先搜索的拓扑排序

思路:

这个问题相当查找有向图中是否存在环。逐个删除入度为0的节点,当删除的节点数量等于输入的所有节点数量时,判定不存在环。

拓扑排序最好使用邻接链表存储邻接关系,而非使用邻接矩阵。因为邻接链表在能够非常直接查找到邻接节点,查找操作耗时O(m+n),而邻接矩阵需要进行遍历才能查找到邻接节点,查找操作耗时O(n^2)。其中n为节点数量,m为边的数量。

本算法的时间复杂度和空间复杂度都比较大,原因在于创建了邻接矩阵存储邻接关系。导致在查找邻接关系的时候,需要进行遍历操作,时间复杂度为O(n^2)。

执行用时 :60 ms, 在所有 cpp 提交中击败了32.55%的用户
内存消耗 :81.6 MB, 在所有 cpp 提交中击败了5.21%的用户
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == )
return true; vector< vector<int> > mat( numCourses, vector<int>(numCourses,) );
vector<int> numR(numCourses, );
vector<int> stack(numCourses, );
vector<int> tIn;
int top = , count = ; for(int i = ; i < prerequisites.size(); ++i) {
tIn = prerequisites[i];
mat[tIn[]][tIn[]] = ;
numR[tIn[]] += ;
} for(int j = ; j < numCourses; ++j) {
if(numR[j] == ) {
stack[top++] = j;
}
} while(top > ) {
int gettop = stack[--top];
count += ; for(int k = ; k < numCourses; ++k) {
if(mat[gettop][k] == ) {
numR[k] -= ; if(numR[k] == )
stack[top++] = k;
}
}
} if(count == numCourses )
return true;
else
return false;
}
};

对上述算法进行改进。将邻接矩阵换成邻接链表。时间复杂度为O(m+n),耗时大大缩小。

执行用时 :24 ms, 在所有 cpp 提交中击败了93.35%的用户
内存消耗 :12.9 MB, 在所有 cpp 提交中击败了19.07%的用户
注意,这里巧妙使用vector<vector<int>>数据类型创建了“邻接链表”。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == )
return true; vector< vector<int> > mat(numCourses);
vector<int> numR(numCourses, );
vector<int> stack(numCourses, );
vector<int> tIn;
int top = , count = ; for(int i = ; i < prerequisites.size(); ++i) {
tIn = prerequisites[i];
mat[tIn[]].push_back(tIn[]);
numR[tIn[]] += ;
} for(int j = ; j < numCourses; ++j) {
if(numR[j] == ) {
stack[top++] = j;
}
} while(top > ) {
int gettop = stack[--top];
count += ; for(int k = ; k < mat[gettop].size(); ++k) {
numR[mat[gettop][k]] -= ; if(numR[mat[gettop][k]] == )
stack[top++] = mat[gettop][k];
}
} if(count == numCourses )
return true;
else
return false;
}
};

基于深度优先搜索的拓扑排序

时间复杂度:排序过程为O(n+m),其中n为节点数量,m为边数量。构建邻接链表为O(m)。

空间复杂度:邻接链表占据空间为O(m);标识数组占据空间为O(n);递归过程的栈内存最大为O(n),此时拓扑序列为一条链。

class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == )
return true; vector< vector<int> > mat(numCourses);
vector<int> flag(numCourses, );
vector<int> tIn; for(int i = ; i < prerequisites.size(); ++i) {
tIn = prerequisites[i];
mat[tIn[]].push_back(tIn[]);
} bool ans = true;
for(int i = ; i < numCourses; ++i) {
ans = ans&&dfsF(i, flag, mat); // 每一条路线不允许存在回路,所以是“&&”逻辑
}
return ans;
} bool dfsF(int i, vector<int>& flag, const vector<vector<int> >& matC){
if(flag[i] == )
return true; if(flag[i] == -)
return false; flag[i] = -;
for(int j = ; j < matC[i].size(); ++j) {
if(dfsF(matC[i][j], flag, matC))
continue;
else
return false;
} flag[i] = ;
return true;
}
};
上一篇:『编程题全队』Beta 阶段冲刺博客五


下一篇:LeetCode77. Combinations(剑指offer38-2)