排序题目

1 熟练运用sorted函数,理解其可以对list排序的写法,做题前要审清题意,这个题不是直接把名次相加再求和比较大小

5345. 通过投票对团队排名

2 用贪心和指针的思想都很容易解决,

这两题很像,57也可用二分  57. 插入区间     56. 合并区间
   495. 提莫攻击

3 利用一个栈和一个队列实现,一个记录正序,一个记录逆序,如果减到0了,就不会被入栈或队列,如果用其它方法,还要对不满足条件的删除索引,这里实际上给了一个不用删除索引的方法,

5336. 上升下降字符串

4 必须要先排序,再合理讨论区间间的关系,

56. 合并区间

5 可以用快速排序和堆排序,用快速排序时,关键是当数组中的值小于target时,指针要加1,并且交换位置,

215. 数组中的第K个最大元素

6 同上一个题一样,只需求解第k小的数即可,

面试题 17.14. 最小K个数

拓扑排序

1 拓扑排序专门为了解决有向图中的排序问题,无向图用并查集,拓扑排序必须要有两个东西记录数据,

一个是出边表记录每个点所指向的点,这个目的是为了每删除一个入度为0的点时,要删除其对应的边,

另一个是入度表,每删除一个点后,都要更新入度表中的数据,时间复杂度: O(n+m),其中 n为课程数,

m为先修课程的要求数,m时机上是边的个数,一个边只要遍历一遍就会被删除,所以是O(n+m)

207. 课程表   210. 课程表 II

原文地址:https://www.cnblogs.com/xxswkl/p/12390820.html