算法与数据结构例题选讲-yunanluo.pdfVIP

算法与数据结构例题选讲 清华大学交叉信息研究院 罗宇男 /noip Pre-survey 1. 复杂度分析 9. 二叉有哪些信誉好的足球投注网站树 17. 近似算法 2. 分治 10. 单调队列 18. 字符串处理 3. BFS 11. 线段树 19. 博弈游戏 4. DFS 12. 网络流  √ ：solved problem 5. 最短路 13. 贪心  〇：Known 6. 最小生成树 14. 动态规划  × ：Unknown 7. 并查集 15. Hash 8. 堆 16. 随机算法 Idea  着重思考问题的过程，而不是对数据结构、经典算法的代码记忆。  编程能力与算法设计能力并重。  贪心法、随机化也能拿很高的部分分。 近似算法 负载平衡  输入：m台机器，n个零件。零件j 的加工时间是t[j]。 一个零件加工的时候不能中途停止 一台机器同一时间最多只能加工一个零件  Def ：J[i]表示分配给机器i的零件的集合，则机器i的负载为 Li t j j J [i ]  Def ：完工时间 L  max L i i  目标：最小化L 近似算法：贪心  以任意顺序遍历job[] ，当处理到job[ i]时，将其分配到当前负载 最小的机器上。  E.g ：job={2,3,4,6,2,2} ，3台机器  L1=8  L2=5  L3=6  L=8 近似估计  定理：上述贪心法是一个2-近似，即 L 2L*,L*是最优值。  证明： Q1: 3-SUM  N个数的数组，判断是否有三个数a,b,c满足a+b+c=0. O(N^2)  转化为：给定x ，判断是否存在i,j使得a[i]+a[j]=x Q2: Resource allocation  N个人分处数轴上的N个不同的点，现在要建造一个公共设施 （如消防队），使得其到各个点的距离之和最短。  中位数！ Q3: Longest Palindromic Substring  给定一个字符串，求最长回文子串。  Solution1: 枚举起点和终点，O(n^3)  Solution2: 枚举中点，往左右扫描，O(n^2)  Solution3: DP! P[i,j]=1表示s[i]到s[j]是一个回文串，P[i,j]=1 iff – i=j, or – j=i+1 and s[ i]=s[j], or – P[i+1,j-1]=1 and s[i]=s[j] O(n)! Q4: 区间覆盖  定义：如果一个点被某个区间包含，那么我们称改点覆盖该区间。  数轴正半轴上有n个区间[Ai,Bi] ，选取一个点使得其覆盖尽量多的 区间。输出最多覆盖的区间数。  Input: [3,5], [4,8], [1,2], [5,10]  Output: 3 /*(5,0)*/ Q4: 区间覆盖  Sol1 ：枚举所有点，统计最大覆盖数。但复杂度高达 O(n*(|minAi|+|maxBi|))。  Sol2 ：最优点一定放置在某个区间的左端点 Ai处。首先对左端点 从小到大排序，那么如果j = i ，则区间j 包含区间i当且仅当B_j = A_i。于是我们可以把所有区间的右端点放到堆中，然后对于 每个Ai ，统计比其大的右端点的个数。复杂度O(N log N)。  Sol3 ：对左右端点赋值，分别为+1和-1 ，对所有点排序，如果两 个点坐标相同，那么左点排在右点的前面。之后扫面一遍，+1和 -1分别代表进入和退出区间。在扫描的过程中记录最大的区间覆 盖数即可。