蜗居匹兹堡孤独刷题中

Day 45 - 2019/03/21

540. Single Element in a Sorted Array
很好的二分法的题，注意用具体例子分析

partition positive and negative in place
相向双指针之partition

200. Number of Islands
方法一：DFS
注意什么时候count++
O(n * m) time, O(n * m) space
方法二：BFS
编程量大的题一定注意typo的检查
O(n * m) time, O(min(n, m)) 注意queue的增长限制
方法三：并查集
O(n * m) time, O(n * m) space

English numeric words to number
首先创建一个dict将需要用到的numeric words和相应的number对应起来。
然后注意符号
还有就是计算这些数字的顺序需要考虑英语语法。

273. Integer to English Words
首先需要注意的是零的特殊处理，除了input == 0之外，没有地方会用到“Zero”。所以，必须写一个helper作为递归函数。

3. Longest Substring Without Repeating Characters

235. Lowest Common Ancestor of a Binary Search Tree
递归和非递归方法

169. Majority Element
用HashMap是O(n)time, O(n) space
先sort 再返回nums[nums.length / 2]是O(nlogn) time, O(1) space

229. Majority Element II
Boyer-Moore Majority Vote algorithm 背一遍

Day 46 - 2019/03/22

今天去本地的一个小破公司面了个试，荒废了。

Day 47 - 2019/03/23

今天玩了一天
346. Moving Average from Data Stream

Day 48 - 2019/03/24

Rehashing
首先注意在open hash中，新加入的值是加在linkedlist末尾还是开头。
然后注意负数取模：a % b = (a % b + b) % b to make it is a non negative integer

146. LRU Cache

首先我需要一种数据结构，能够维护这些key/value使用的先后顺序，如果一个key刚刚被使用，那它就需要被提前。如果达到了capacity，需要去掉Least Recently Uesd。
注意：不是加入的顺序，而是要维护使用的顺序。随时改变顺序。
这样需要频繁改变结构的时候，用LinkedList比较合适。
使用头尾两个指针，头指针指向刚刚用过的值，尾指针指向最不常用的值。这样，需要提供的操作有：
addFirst(); // put
moveToFirst(); //used by get and put(update a value)
removeLast();  // put
然后，还需要有哈希表的功能。需要通过key，查到相应的ListNode。同时，当removeLast的时候，要update哈希表。所以，ListNode里不仅要存value，还要存key，以便update哈希表。
我经常会忘记的是，如果put一个已有的key，这时候不仅要update value，还要moveToFirst();

Implementing a Max Heap using an Array

Day 49 - 2019/03/25

263. Ugly Number
注意0

264. Ugly Number II
方法一： PQ + HashSet
用当前已知的最小的丑数，乘以{2, 3, 5}，就能够得到其他丑数。用一个minHeap保存已知丑数，方便取到最小值。
注意：1）新造出来的数可能已经出现过了，所以用Set去重； 2）overflow
O(nlogn) time
方法二：DP O(n) 正常人不太能想得到，先不研究了

Top K Largest Number II
维护一个minHeap，if (minHeap.size() > k) minHeap.poll()
记着练练minHeap.iterator()

Merge K Sorted Lists  
方法一 PriorityQueue，O(nlogk) time.
注意任何时候加入PQ都要检查是否是null
方法二：Divide & Conquer, O(nlogk) time.
方法三：两两归并, O(nlogk) time. 注意奇偶性

347. Top K Frequent Elements
方法一：minHeap，O(nlogk) time
方法二：桶排序 O(n) time, O(n) space

53. Maximum Subarray
PrefixSum (sum include nums[i]) 联用 minSum

25. Reverse Nodes in k-Group
记住要在reverse group的时候 curr.next = null把它先断开，再reverse。[/i]

Day 50 - 2019/03/26

今天主要复习了一下大数据的基础知识

973. K Closest Points to Origin
方法一：sort后取前K。 O(nlogn) time，O(n) space
方法二：maxHeap。 O(nlogK) time， O(logK) space
方法三：partition. O(n) average time. O(1) space.

Day 51 - 2019/03/27

今天主要学习了一下unit testing，改了一下简历。又复习了一下Javascript的基本语法。

41. First Missing Positive
奇技淫巧。举例子演示，得多背两遍

Day 52 - 2019/03/28

为了一个周五的破面试，学了一天javascript，又写了一些简单题练习c#语法，真是不喜欢这些，非常烦躁

Day 53 - 2019/03/29

今天没怎么做题，主要看看笔记，复习了一些知识题，晚上面了个试

Day 54 - 2019/03/30

今天玩了一整天，什么都没干