自己监督自己的刷题打卡贴

时间 ： 09/11/2018

42. Trapping Rain Water。不会写。
只能说思考的角度太厉害了。two pointer那个也太厉害了。左右最大值中最小的，从两边往中间找的话，比如 a|b .. c|d。 如果第一个|小，那么对于b来说知道了左边的最大值，右边最大值未知，但是已经表明了小于等于右边最大值的一个墙已经大于左边最大值了，所以此时就已经确定了。这两个墙总有一个小的所以bc总有个已经确定了最大值中最小的那个数，然后就可以知道这个点本身的蓄水量，然后往中间计算下一个点。厉害厉害。
407.Trapping Rain Water II。不会写。
不同的边儿都要用来比较长短选取最短的那个，然后往里移动，那么这时候就应该需要一直能找出最小值的那个了，此时就想到Priorityqueue。但是对于一个点来说，四个相邻的点都作为可能visited的candidate，这种向里聚合的方向性该怎么确定呢？貌似从四个边儿开始为起点，就已经imply的规定了这个的方向性。 对于同一个水池来说，里边所有点的最短边都是一样的都等于水池本身的最短边。也就是说当遇见这个最短边的那一刻，就持续poll扩散找到本水池的所有点，更新水量。之后再找queue里的存的别的可能蓄水的点，找到下一个水池的最短边后也是开始Poll和扩散（因为扩散过程中加入queue的Height不变，代表最短边）。那么如果这个点没有蓄水和水池无关呢？因为我们是从四个边向中间扩散的，所以如果不蓄水又很短的话，情况只有从边到中间的过程中，是逐渐上升的，所以每次到里边的一个点的时候，height是递增，所以会被更新，然后本身减去是负数，所以不会蓄水。
408. Valid Word Abbreviation。AC。
409. Longest Palindrome。AC
410. Split Array Largest Sum。不会写。dp用的很好。二分法。。跪了跪了。

411不会写。
投了一些简历

09/13/2018
413. Arithmetic Slices. AC.45min  M
414. Third Maximum Number AC. 9min E
415. AC. 10min E
416. AC. 30min M.自己用dfs写的，一开始TLE把pruning的步骤加上就好了。 然后感觉dp的解法非常的厉害

来给楼主回赞一个～莫非也是边做实验边转行儿的同仁 哈哈
加油儿！

Eeveei 发表于 2018-9-14 12:08
来给楼主回赞一个～莫非也是边做实验边转行儿的同仁 哈哈
加油儿！

哈哈  谢谢！ 以前做实验，现在已经不啦。加油！

09/14/2018
417. Pacific Atlantic Water Flow。写错。debug很久。发现一定要分开讨论，不能共用一个visited matrix。因为有方向性，所以要从四个边开始，如果从任意点开始，比如是中间某一点，这样人为隔断了此点和更高处，出现错误答案。
417. TLE test case 40/51

09/17/2018
4.Median of Two Sorted Arrays
733. Flood Fill
824. Goat Latin

09/18/2018
8.String to Integer(atoi)
10.Regular Expression Mathcing
12.Integer to Roman
437.Path Sum III

09/20/2018
314. Binary Tree Vertical Order Traversal
273. Integer to English Words
17.Letter Combinations of a Phone Number
278.First Bad Version
91 Decode Ways
253 Meeting Rooms II
168 Excel Sheet Column Title
23 Merge k Sorted Lists