3.28【LeetCode练习】课程表

vector用法几个for的新用法关于我的超时代码对比了题解之后新的结果

第一个图论题，去看题解了…

先放一些vector的用法：
来自：C++ 二维vector使用
首先是C++对于二维数组的构建：

int **p;
p = new int*[10];    //注意，int*[10]表示一个有10个元素的指针数组
for (int i = 0; i < 10; ++i)
{
    p[i] = new int[5];
}

二维vector定义：

vector > p;

resize可以改变行、列形状，一般用于初始化的时候。二维vector的访问和二维数组的访问方法相同：

int i,j;
vector> array(5);
for (i = 0; i < array.size(); i++)
    array[i].resize(3);
 
for(i = 0; i < array.size(); i++)
{
    for (j = 0; j < array[0].size();j++)
    {
        array[i][j] = (i+1)*(j+1);
    }
}

想要拷贝元素：for(auto x:range)
想要修改元素 : for(auto &&x:range)
想要只读元素：for(const auto& x:range)

这是看完题解之后我手敲的代码结果：我的深度遍历递归会超时…大哭…

class Solution {
public:
	vector > edges;
	vector  visited;
	bool valid=true;
	void dfs(int i){
		for (const auto& edge:edges[i]) {
			if (visited[edge]==0){
				visited[i]=1;
				dfs(edge);
				visited[i]=0;
			}
			else if (visited[edge]==1){
				valid=false;
				return;
			}
		}
	}
    bool canFinish(int numCourses, vector>& prerequisites) {
		edges.resize(numCourses);
		visited.resize(numCourses,0);
		for (const auto& edge:prerequisites){
			edges[edge[0]].push_back(edge[1]);
		}
		for (int i=0;i 
对比了题解之后 
然后我又去看了一遍题解，问题出在哪里了呢，同样是递归…
 有两处不同：
 
题解里的把递归的状态给了三种：未搜索、已搜索、搜索中。也就是多给了一个递归状态“2”，画图之后我对2的作用的理解：当拓扑图的一条支路遍历完成之后（即是一个通路），会将其状态赋值为2。这样在主函数做循环时，无需再遍历状态为2的支路，大大降低时间复杂度。递归返回上一级节点时，如果刚才的那条支路不通，直接valid=false返回，不需要递归完整个子树，也能够减少时间复杂度。 
新的结果 
 
class Solution {
public:
	vector > edges;
	vector  visited;
	bool valid=true;
	void dfs(int i){
		for (const auto& edge:edges[i]) {
			if (visited[edge]==0){
				visited[i]=1;
				dfs(edge);
                if (!valid) {
                    return;
                }
				visited[i]=0;
			}
			else if (visited[edge]==1){
				valid=false;
				return;
			}
		}
        visited[i]=2;
	}
    bool canFinish(int numCourses, vector>& prerequisites) {
		edges.resize(numCourses);
		visited.resize(numCourses,0);
		for (const auto& edge:prerequisites){
			edges[edge[0]].push_back(edge[1]);
		}
		for (int i=0;i