Chapter 27 Select Topics

27.2 200. Number of Islands

https://leetcode.com/problems/number-of-islands/

27.2.4 Union Find

Another way to make set:

findset的解释: 如果我没有boss(bo[x]==-1),就返回我自己,否则返回我boss的boss,知道我的boss的boss没有boss(没有boss的就是超级大boss- root).

27.3 305. Number of Islands II

https://leetcode.com/problems/number-of-islands-ii/

这道题只有union find一条路了!

27.5 406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

https://leetcode.com/problems/queue-reconstruction-by-height/

http://massivealgorithms.blogspot.com/2016/09/leetcode-406-queue-reconstruction-by.html

http://tianshilei.me/2016/10/19/leetcode406/

解法1:插入排序Insertion Sort

这道题就是一道排序题,只不过由于它的元素是 pair,因此排序的条件比较奇特.因此,我们需要使用的工具可以定下来了,就是使用 STL中的sort 函数,然后定义comp.

那我们如何定义这个comp呢?请先考虑,如果给定几张特殊的扑克牌,每张扑克牌上都有两个数字,分别代表题目中的 h 和 k,然后我们需要将这副牌按照题目的要求排列,那么应该如何手动做呢?我想,我应该会先按照 h 对手上的牌进行排序,从大到小.那如果 h 一样怎么办?那么谁的 k 小谁排在前面.这是第一轮排序.假设我的牌是从左向右排列的.然后从最左边一张牌开始,每次拿出来一张,看看它的 k 是多少,就将它插在从左数第 k 个位置,然后再取下一张,重复这个过程,直到所有的牌都重新插好.这是第二轮排序.我们就拿上面它给的例子来看:

我们通过最初的排序可以得到排序后的结果,然后再对每一张牌进行插入式排序.图中的蓝色箭头就代表我们将这张牌取出来,插到相应的位置.

那么接下来的问题是,我们为什么要按照上面说的规则进行第一轮排序呢?这个问题的回答其实需要参照我们第二轮插入的过程来看.我们在第二轮进行插入的时候,每次都是从最左边(也就是序列的初始位置)开始数第 k 个位置进行插入,这个有些贪心的策略在里面(而 Leetcode 上面也确实将这个题的 Tags 设置为 greedy),就是考虑所谓的局部最合适.因此,为了让后面的元素每次找插入位置的时候从最左边开始且恰好第 k 个位置之前的元素都要大于它,这需要我们在每次选择元素的时候按照 h 递减的次序选,因此才有了第一轮排序中的对 h 进行排序,大的放在前面这个策略了.我们第一轮排序中还有一个原则是,如果 h 一样,那么谁的 k 小谁排在前面.这个是为什么呢?举个反例就可以说明了.还看第二轮,假如 k 大的排在前面,那么我们首先会拿到大的那张牌C1,假设它的 k 值是 k1,然后将它插在第 k1 个位置,接下来我们会拿到小的那张牌C2,假设它的 k 值是 k2,且 k1 > k2,那么按照我们第二轮的插入策略,必然将它插在 C1 的前面,这个时候虽然 C2的 k 值是对着的,但是 C1 的值就不应该是 k1,而应该是 k1 + 1 了,就不对了.

有了上述手动排序的过程,我们就不难写出相应的 C++ 代码了,这里我们用了一些 C++11 新特性,比如 Lambda 表达式、auto 符号等.

学插入排序的时候觉得太简单没啥用,这道题就派上用场了.

解法2:

上面那种方法是简洁,但是用到了额外空间,我们来看一种不使用额外空间的解法.

解法3:

考点是sort的定制的写法,vector的insert函数用法.

复杂度: 插入排序是O(N^2),所以T始终是\(O(N^2)\), S可以降到\(O(1)\).