Hash & Heap
Moving Average from Data Stream
- average两个重要部分，sum和数量，average = sum / count
- window size是给的，也就是用于计算average的count
- moving average 用到sum，应该想到维护一个accum sum array，存前i位的sum，但是这个array size很难确定
- 一个index是当前，一个是count - index，通过这两个index在sum array里面找到这段sum
- 需要index，这样放进sum array的index就有了，所以每次有新的成员要index++
方法(2) 每次都计算一次sum，sum是个int
方法(3) 用deque，每次弹出第一个(poll)，加入最新的
Implement Stack by Two Queues
- 每次加入放Q1
- 吐出来前先把Q1的全部放进Q2，剩最后一个时吐出来
- 交换Q1,Q2，这样子Q1一直保持着‘存贮’主体，Q2一直是空的，用于移动
- stack.isEmpty就等于Q1.isEmpty
First Unique Character in a String
- 基本解法是O(N)时间和O(N)空间，因为我把string变成char array
- both O(1)解法是从a到z遍历26个字母，记录第一次出现的位置，和最后一次
for (char ch = 'a'; ch <= 'z'; ch++) str.indexOf(str) || str.lastIndexOf(str)没有就返回-1
Insert Delete GetRandom O(1)
- 用map记录
element -> indedx - 用arraylist记录element
arraylist.remove(int index)这个方法O(n)时间，因为原文如下：public E remove (int index) Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
- 为了去掉这部分O(n)时间，方法是remove the last one
- 操作： 置换最后一个和当前这个元素
K Closest Points
Top k Largest Numbers
Merge K Sorted Lists
Implement Queue by Two Stacks
Ugly Number II
Hash Table
Group Anagrams
注意：
将‘由相同字母（且数量相同）组成’的字符串都放在一个list里，它们相互为‘排列’关系，内容一样，排列顺序不同。
- Map
- str array中每一个String，都serialize，生成key，添加到map里
- 最后返回
new Array List<Integer>(map.value()); - 关键是map key：key应该是string的serialize format。26个字母出现的次数依然排序，用
#相隔开 - 为什么一定要用#隔开？因为
次数有一位数有两位数，不隔开，deserialize时根本分不清
TreeMap
TreeMap interface
- keySet(): returns a set of the keys in ascending order
- values():returns a collection of all values in the ascending order of the corresponding keys
- 但是会增加Time complexity
A TreeMap is a Red-Black tree based NavigableMap implementation. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
