拓扑排序
找到做事情的先后顺序，拓扑排序的结果可能不是唯一的
如何排序?

  1. 找出图中入度为 0 的点，然后输出
  2. 删除与该点连接的边
  3. 重复 1、2 操作，直到图中没有点或者没有入度为 0 的点为止

实现拓扑排序
借助队列，来一次 BFS 即可

  1. 初始化:把所有入度为 0 的点加入到队列中
  2. 当队列不为空的时候:拿出队头元素，加入到最终结果中;删除与该元素相连的边;判断:与删除边相连的点,是否入度变成 0 如果入度为 0，加入到队列中

借助STL容器灵活建图
vector<vector> edges;
unordered_map<int,vector> edges;

根据算法流程，灵活建图
每个顶点的入度 vector in;

1课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //1.准备工作
        unordered_map<int,vector<int>> edges;//邻接表存图
        vector<int> in(numCourses);//标记每个节点的入度

        //2.建图
        for(auto e:prerequisites){
            int a=e[0],b=e[1];
            edges[b].push_back(a);
            in[a]++;
        }

        //3.拓扑排序
        a
        queue<int> q;
        for(int i=0;i<numCourses;i++){
            if(in[i]==0){
                q.push(i);
            }
        }

        //bfs
        while(!q.empty()){
            int t=q.front();q.pop();

            for(int a:edges[t]){
                in[a]--;
                if(in[a]==0){
                    q.push(a);
                }
            }
        }

        //4.判断是否有环
        for(int i=0;i<numCourses;i++){
            if(in[i]) return false;
        }
        return true;
    }
};

2体育课测验(二)

描述
体育课共有 numProject个考核项目，编号为 0到 numProject−1，考核中每两个项目被划分为一组得到分组数组
groupsi ，现规定若想完成项目 groupsi[0]，必须先完成 groupsi[1]。保证所有分组互不相同，
若分组情况能顺利完成考核，请返回任意的一个完成顺序,否则返回空数组 。

数据范围：
1≤numProject≤2000 1≤groupsi.length≤numProject∗(numProject−1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <queue>
#include <unordered_map>
class Solution {
public:
    vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
        // write code here
        //1.准备工作
        unordered_map<int, vector<int>> edges;
        vector<int> in(numProject,0);
        vector<int> ans;

        //2.建图
        for(auto e:groups){
            int a=e[0],b=e[1];
            edges[b].push_back(a);
            in[a]++;
        }

        //3.拓扑排序
        //把所有入度为零的点加入到队列中
        queue<int> q;
        for(int i=0;i<numProject;i++){
            if(in[i]==0){
                q.push(i);
            }
        }

        //bfs
        while(!q.empty()){
            int t=q.front();q.pop();
            ans.push_back(t);
            for(int a:edges[t]){
                in[a]--;
                if(in[a]==0){
                    q.push(a);
                }
            }
        }

        //4.检查是否所有节点都被处理
        if(ans.size()!=numProject){
            return {};
        }
        return ans;
    }
};

快速排序

3数组排序

给你一个整数数组 nums，请你将该数组升序排列。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }

    void qsort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return;
        int key=get_rand(nums,left,right);
        int i=left,l=left-1,r=right+1;
        while(i<r)
        {
            if(nums[i]<key) swap(nums[++l],nums[i++]);
            else if(key==nums[i]) i++;
            else swap(nums[i],nums[--r]);
        }

        //[left,l][l+1,r-1][r,right]
        qsort(nums,left,l);
        qsort(nums,r,right);
    }

    int get_rand(vector<int>& nums,int left,int right)
    {
        int r=rand();
        return nums[r%(right-left+1)+left];
    }
};

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    vector<int> ret;
public:
    vector<int> sortArray(vector<int>& nums) {
        ret.resize(nums.size());
        Mergesort(nums,0,nums.size()-1);
        return nums;
    }

    void Mergesort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return;
        //选择中间位置
        int mid=(left+right)>>1;

        //把左右区间排序
        //[left,mid][mid+1,right]
        Mergesort(nums,left,mid);
        Mergesort(nums,mid+1,right);

        //合并两个有序数组
        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=right)
        {
            ret[i++]=nums[cur1]<nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        //处理没有遍历完的数组
        while(cur1<=mid) ret[i++]=nums[cur1++];
        while(cur2<=right) ret[i++]=nums[cur2++];

        //还原
        for(i=left;i<=right;i++)
            nums[i]=ret[i-left];
    }
};