体育课测验(一)

C++ 解法, 执行用时: 10ms, 内存消耗: 3488KB, 提交时间: 2022-06-19

class Solution {
  public:
    bool canFinish(int numProject, vector<vector<int>>& groups) {
        vector<vector<int>> f(numProject);
        for (auto& a : groups) {
            f[a[1]].push_back(a[0]);
        }
        bool b[numProject];
        fill(b, b + numProject, false);
        bool path[numProject];
        fill(path, path + numProject, false);
        for (int i = 0; i < numProject; i++)
            traverse(f, i, b, path);

        return !k;
    }

  private:
    void traverse(const vector<vector<int>>& f, int node,
                  bool b[], bool path[]) {
        if (path[node]) k = true;
        if (b[node] || k) return;

        b[node] = true;
        path[node] = true;
        for (auto next : f[node]) {
            traverse(f, next, b, path);
        }
        path[node] = false;
    }

  private:
    bool k = false;
};

C++ 解法, 执行用时: 10ms, 内存消耗: 3488KB, 提交时间: 2022-05-13

class Solution {
public:
    bool canFinish(int numProject, vector<vector<int>>& groups) {
        // 构建有向图
        vector<vector<int>> graph(numProject);
        for (auto& it : groups) {
            graph[it[1]].push_back(it[0]);
        }

        // 对图进行深度优先遍历
        bool isVisited[numProject];
        fill(isVisited, isVisited + numProject, false);
        bool path[numProject];
        fill(path, path + numProject, false);
        for (int i = 0; i < numProject; i++)
            traverse(graph, i, isVisited, path);

        return !hasCycle;
    }

private:
    void traverse(const vector<vector<int>> &graph, int node,
                  bool isVisited[], bool path[]) {
        if (path[node]) hasCycle = true;
        if (isVisited[node] || hasCycle) return;

        isVisited[node] = true;
        path[node] = true;
        for (auto next : graph[node]) {
            traverse(graph, next, isVisited, path);
        }
        path[node] = false;
    }

private:
    bool hasCycle = false;
};

C++ 解法, 执行用时: 10ms, 内存消耗: 3732KB, 提交时间: 2022-05-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numProject int整型 
     * @param groups int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool canFinish(int numProject, vector<vector<int> >& groups) {
        edges.resize(numProject);
        visited.resize(numProject);
        for (const auto& info : groups) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numProject; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
    void dfs(int u) {
        visited[u] = 1;
        
        for (auto &v : edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;
};

C++ 解法, 执行用时: 11ms, 内存消耗: 3372KB, 提交时间: 2022-05-15

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numProject int整型 
     * @param groups int整型vector<vector<>> 
     * @return bool布尔型
     */
    vector<bool> visited;
    vector<bool> onPath;
    bool hasCycle=false;
    vector<vector<int>> buildGraph(vector<vector<int>>& groups,int numProject)
    {
        int len=groups.size();
        vector<vector<int>> graph(numProject);
        for(vector<int> i:groups)
        {
            int from=i[1];
            int to = i[0];
            
            graph[from].push_back(to);
        }
        return graph;
    }
    void dfs(vector<vector<int> >& graph,int s)
    {
        if(s>graph.size()||s<0)
        {
            cout<<"out of bound"<<endl;
            return ;
            
            
        }
        if(onPath[s])
        {
            hasCycle=true;
            return ;
        }
        if(visited[s])
        {
            return;
        }
        onPath[s]=true;
        visited[s]=true;
        for(int i:graph[s])
        {
            dfs(graph,i);
        }
        onPath[s]=false;
    }
    bool canFinish(int numProject, vector<vector<int> >& groups) {
        // write code here
        vector<vector<int>> graph=buildGraph(groups,numProject);
        int len=groups.size();
        visited.resize(numProject);
        onPath.resize(numProject);
        for(int i=0;i<numProject;i++)
        {
            dfs(graph,i);
        }
        
        return !hasCycle;
    }
};

C++ 解法, 执行用时: 11ms, 内存消耗: 3468KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numProject int整型 
     * @param groups int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool canFinish(int numProject, vector<vector<int> >& groups) {
        // write code here
        vector<vector<int>> f(numProject);
        for(auto &a:groups)
        {
            f[a[1]].push_back(a[0]);
        }
        bool b[numProject];
        fill(b,b+numProject,false);
        bool path[numProject];
        fill(path,path+numProject,false);
        for(int i=0;i<numProject;i++)
            traverse(f,i,b,path);
        return !k;
        
    }
    private:
    void traverse(const vector<vector<int>> &f,int node,bool b[],bool path[])
    {
        if(path[node])
            k=true;
        if(b[node]||k)
            return;
        b[node]=true;
        path[node]=true;
        for(auto next:f[node])
        {
            traverse(f,next,b,path);
        }
        path[node]=false;
    }
    private:
    bool k=false;
};

详情