[Li Kou] curriculum series

【 Power button 】 Curriculum series

Leetcode 0207 The curriculum

Title Description ：Leetcode 0207 The curriculum

analysis

• The test site of this question ： A topological sort .

• For topology sorting, please refer to ： website .

Code

• C++

class Solution {
    
public:
    bool canFinish(int n, vector<vector<int>> &edges) {
    

        vector<vector<int>> g(n);
        vector<int> d(n);  //  Storage penetration 
        for (auto &e : edges) {
    
            int b = e[0], a = e[1];
            g[a].push_back(b);
            d[b]++;
        }

        queue<int> q;
        for (int i = 0; i < n; i++)
            if (d[i] == 0)
                q.push(i);

        int cnt = 0;
        while (q.size()) {
    
            auto a = q.front(); q.pop();
            cnt++;
            for (auto b : g[a])
                if (--d[b] == 0)
                    q.push(b);
        }
        return cnt == n;
    }
};

• Java

class Solution {
    
    public boolean canFinish(int n, int[][] edges) {
    

        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        int[] d = new int[n];  //  Storage penetration 
        for (int[] e : edges) {
    
            int b = e[0], a = e[1];
            g.get(a).add(b);
            d[b]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++)
            if (d[i] == 0)
                q.add(i);

        int cnt = 0;
        while (!q.isEmpty()) {
    
            int a = q.remove();
            cnt++;
            for (int b : g.get(a))
                if (--d[b] == 0)
                    q.add(b);
        }
        return cnt == n;
    }
}

Time and space complexity analysis

• Time complexity ：$O(n)$,n Number of courses .

• Spatial complexity ：$O(n)$.

Leetcode 0210 The curriculum II

Title Description ：Leetcode 0210 The curriculum II

analysis

• The test site of this question ： A topological sort .

• For topology sorting, please refer to ： website .

• This question is relative to Leetcode 0207 The curriculum , Let's find out the scheme of topological sorting . The out of queue order of the elements in the queue is a legal scheme , Just write it down

Code

• C++

class Solution {
    
public:
    vector<int> findOrder(int n, vector<vector<int>> &edges) {
    

        vector<vector<int>> g(n);
        vector<int> d(n);  //  The degree of 
        for (auto &e : edges) {
    
            auto b = e[0], a = e[1];
            g[a].push_back(b);
            d[b]++;
        }

        queue<int> q;
        for (int i = 0; i < n; i++)
            if (d[i] == 0)
                q.push(i);

        vector<int> res;
        while (q.size()) {
    
            auto a = q.front();
            q.pop();
            res.push_back(a);
            for (auto b : g[a])
                if (--d[b] == 0)
                    q.push(b);
        }
        if (res.size() < n) res = {
    };
        return res;
    }
};

• Java

class Solution {
    
    public int[] findOrder(int n, int[][] edges) {
    

        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        int[] d = new int[n];  //  Storage penetration 
        for (int[] e : edges) {
    
            int b = e[0], a = e[1];
            g.get(a).add(b);
            d[b]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++)
            if (d[i] == 0)
                q.add(i);

        int[] res = new int[n];
        int cnt = 0;
        while (!q.isEmpty()) {
    
            int a = q.remove();
            res[cnt++] = a;
            for (int b : g.get(a))
                if (--d[b] == 0)
                    q.add(b);
        }
        if (cnt < n) return new int[]{
    };
        return res;
    }
}

Time and space complexity analysis

• Time complexity ：$O(n)$,n Number of courses .

• Spatial complexity ：$O(n)$.

Leetcode 0630 The curriculum III

Title Description ：Leetcode 0630 The curriculum III

analysis

• The test site of this question ： greedy 、 Pile up .

• Sort by deadline from small to large , Look at each course from front to back , If you can choose this course, choose , If not, you must delete a course , Delete the longest course containing the current course .

• Choose if you can ： That is, if the total time taken after joining this course does not exceed the current deadline .

Code

• C++

class Solution {
    
public:
    int scheduleCourse(vector<vector<int>> &courses) {
    
        sort(courses.begin(), courses.end(), [](vector<int> &a, vector<int> &b) {
    
            return a[1] < b[1];
        });

        priority_queue<int> heap;
        int tot = 0;  //  Selected course time 
        for (auto &c : courses) {
    
            tot += c[0];
            heap.push(c[0]);
            if (tot > c[1]) {
    
                tot -= heap.top();
                heap.pop();
            }
        }
        return heap.size();
    }
};

Time and space complexity analysis

• Time complexity ：$O(n\times log(n))$,n Is array length .

• Spatial complexity ：$O(n)$.