LeetCode 207 Course Schedule

Tag: 图算法 LeetCode Posted on 2022-02-08 11:33:18 Edited on 2022-02-08 18:43:47 Views: 203

概述

https://leetcode.com/problems/course-schedule/

实际上就是有向无环图的判定。

会导致死循环的递归法

下面这个解法会导致栈溢出,因为当有环时,我们的算法就会死循环,直至堆栈溢出。

class Solution {
public:
    vector<int>* cache;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> cache(numCourses, -1);
        this->cache = &cache;
        for (int i = 0; i < numCourses; i ++) {
            if (!isOkay(i, prerequisites)) return false;
        }
        return true;
    }
    
    bool isOkay(int i, vector<vector<int>>& prerequisites) {
        if ((*cache)[i] != -1) return (*cache)[i];
        for (auto r : prerequisites) {
            if (r[0] == i) {
                if (!isOkay(r[1], prerequisites)) {
                    (*cache)[i] = 0;
                    return false;
                }
            }
        }
        (*cache)[i] = 1;
        return true;
    }
};

图遍历法

下面这个解法会导致 TLE。

class Solution {
public:
    vector<vector<int>> graph;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // build graph
        vector<vector<int>> graph(numCourses);
        for (auto p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        this->graph = graph;
        vector<bool> onPath(numCourses, false);
        for (int i = 0; i < numCourses; i ++) {
            if (!helper(i, prerequisites, onPath)) return false;
        }
        return true;
    }
    
    bool helper(int i, vector<vector<int>>& prerequisites, vector<bool>& onPath) {
        if (onPath[i]) return false;
        onPath[i] = true;
        
        for (auto n : graph[i]) {
            if (!helper(n, prerequisites, onPath)) return false;
        }
        
        onPath[i] = false;
        return true;
    }
};

实际上当我们以一个节点开始搜索是否有环时,如果该节点已经被搜索过,实际上不需要再次搜索了, 就算已经历的路径不一样也没关系,因为如果后续有环的话,第一次肯定能识别到。

图遍历法(避免重复搜索)

class Solution {
public:
    vector<vector<int>> graph;
    bool hasCycle = false;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // build graph
        vector<vector<int>> graph(numCourses);
        for (auto p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        this->graph = graph;
        vector<bool> onPath(numCourses, false);
        vector<bool> visited(numCourses, false);
        for (int i = 0; i < numCourses; i ++) {
            helper(i, prerequisites, onPath, visited);
        }
        return !hasCycle;
    }
    
    void helper(int i, vector<vector<int>>& prerequisites, vector<bool>& onPath, vector<bool>& visited) {
        if (hasCycle) return;
        if (onPath[i]) {
            hasCycle = true;
            return;
        }
        
        if (visited[i]) return;
        visited[i] = true;
        
        onPath[i] = true;
        
        for (auto n : graph[i]) {
            helper(n, prerequisites, onPath, visited);
        }
        
        onPath[i] = false;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/