leetcode second round: 8/17

today's mission:  220 - 210

今天的任务没有完成的题目是最多的，那几题还是不会做。

220: contain duplicates III
这个题目 index 范围k可以通过sliding window来实现，|num[i] - num[j]| <= t, 对每次即将加入的新元素而言，可以通过lower_bound这个method来看看是否存在j, nums[j] >= nums[i] - t; 同时，需要知道是否存在j , nums[j] <= nums[i] + t, 可以直接看nums[j]的最小值满不满足条件，因为这个不等式至少nums[j]的最小值是需要满足的。
Note: set的lower_bound method的使用！ 可以知道是否存在满足某个条件的点。
219: contain duplicatesII
sliding window + unordered_set
这个题目index 范围跟上面那个题目一样，可以用sliding window来处理，而对于相同的元素，是可以通过 unordered_set中的find method来实现的。
217： contain duplicate
这个是最简单的版本直接要判断一个array里面是否存在duplicate，用一个hash set, 即unordered_set就可以解决了。
218: skyline problem

216：combination sumIII
这个题目要求所有的可能，典型的DFS，DFS画出DFS递归树，要注意DFS signiture中各个参数的含义，这个题目中要注意的是树的下一层的起始node 是上一层的起始node + 1，所以需要有一个标记起始位置的参数，可以叫start。
215： Kth largest element in an array
这个题目用priority_queue很容易解决，但是时间复杂度是O（nlogn）， 但是quicksort也可以解决这类问题，average时间复杂度是O（n）, worst case时间复杂度是O（n^2）, 在这里用两种方法都实现了，两种方法都是能解决duplicate的问题的。
用 quick sort解，第一轮如果pivot swap后所在位置正好是K，那么这个位置所在元素就是所求的解了， 如果这个位置  < k，说明第k个元素在这个位置的后半部分， 继续quick sort后半部分， 如果这个位置 > k， 说明第k个元素在这个位置的前半部分， 继续quick sort前半部分， 有点像binary search 的感觉。
从运行结果上看， quick sort 4ms， 但是priority_queue 46ms, quick sort确实在处理kth largest element 类似问题上比priority_queue要快很多。 但是如果是需要找到前k大elements的话，可能priority_queue比quick sort处理起来更方便， quick sort 如果要用来找前k个的话可能需要把整个array都排好序才行。
在这里把quick sort的方法贴出来：
class Solution {
private:
    int helper(vector<int> &nums, int left, int right, int k) {
        swap(nums[left], nums[right]);
        int j = right;
        int i = left;
        while (i < j) {
            if (nums[i] < nums[right]) {
                i++;
            } else {
                j--;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i], nums[right]);
        if (i == k) {
            return nums[i];
        }
        if (i < k) {
            return helper(nums,i+1, right, k);
        }
        return helper(nums, left, i-1 , k);
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        return helper(nums, 0, nums.size()-1, nums.size()-k);
       
    }
};
214：Shortest Palindrome

213: House Robber II
这个题目是基于下面这个题目的， 唯一区别在与首尾两家是不能同时偷的，也是基于dp的思想，分两种情况，case1： 偷 头，case2： 偷尾。最后取两者最大。
198： House RobberI 
这个题目是很明显的dp来解，M[i]在dp里面代表的含义可以不同，不同含义的M[i]会导致算法不同，通过比较选择更适合解题的M[i]。
这个题目里面M[i] 代表到I为止，maximum money can be stolen, either including M[i] or not including M[i]. 这个是比较简单的M[i]， 也可以定义为including M[i]， 但是这样做的话时间复杂度就会高了。
这个题目也可以将空间复杂度降低为O（1）， 因为对于输入很大的话，用O（n）的空间复杂度存会很浪费不必要的空间。

212: Word SearchII

211: Add  and search Word
Trie tree + dfs search 

210: Course ScheduleII
 这个题目是跟下面那个题目的方法类似的，是典型的topological sort，找prerequsite，方法也是DFS+mark visitIII, 在每次visit 完一个node的时候代表这个node是先修，可以push到rst里面， 但是在graph构造的时候， 两个node 构造的edge :  后序->先修，否则，结果要reverse一下。
Note: 同时需要同时判断这个graph是否valid， 即是否有cycle。

207: Course ScheduleI
这个题目很重要， 从这个题目可以看出2 个graph里面很常见的思想：
1. 从一个edgelist转化成adjacent list表示的graph： how? 
利用 unordered_map来convert 成一个graph， map的 key: node， map的value是neighbors。 这样时间复杂度O（n）就可以转化了。
2. 这个题目其实是需要判断这个graph里面有没有cycle， 怎么判断一个有向图里面有没有cycle呢？ 利用DFS + mark visit III, 3个 state的mark, 而且需要对graph里面的每个node都进行dfs check才能检测出所有可能的cycle.