GIS找工作一个多月准备转CS

昨天收到亚麻OA链接，高频题目刷起来。

973. K Closest Points to Origin

用了排序前K个，O(2nk).
实际问题中可以用于，仓储服务区，辐射k个客户。

146. LRU Cache

简易的缓存设计，最近用到的放最前面，先前使用过的依次往后顶，超出capacity限制的element/node被移除掉。

使用了hash map管理缓存list，缓存list由多个node组成。

演变类型：460. LFU Cache
把使用频率纳入考虑范围，常用的元素放在前面。每次操作element后更新node使用频率，在根据频率降序排序，如果频率一样，参见146LRU的原理。

200. Number of Islands

在grid中看有几个小岛，我是学GIS的，这个处理栅格数据应该以后会用到，遍历发现陆地就把它相连的陆地沉如海底(将值由1改成0)，同时计数。遍历完成后即得Number of Islands.

16ms, 98.8%; 10M, 94.6%
可能大家都用的这个算法，percent高并不能说明什么问题，只是自己运气好而已～
time: O(h*w)
space: O(h*w)

Hash Map Review
hash_map<int, int> indies;

819. Most Common Word

将段落读取，过滤段落格式化成小写c = isalpha(c) ? tolower(c) : ' '; //clear data
istringstream //read data
pair<string, int> res ("", 0); //define result pair
if (ban.find(word) == ban.end()) //word is not found in ban.
if (++count[word] > res.second) //cnt > 原记录数（最初定义为0）
res = make_pair(word, count[word]);//update result

Time：97.8%  O(n)
Space：91.8% O(n)

295. Find Median from Data Stream

Balanced binary search tree

排序后在中位数位置放置指针，左L右R指针对应中位数因子，每增加一个数按odd even情况移动指针。
med =<double> (L+R)/2

Time：79.58%  
add(num): O(logn)
findMedian(): O(logn)

21. Merge Two Sorted Lists

两个排过序的链表L1, L2，新建一个链表用于存储。

比较L1和L2 的头部，选择小的插入新链表。移动被操作的链表的指针到next。
依次类推，直到其中之一的链表指到头。

排序完成，将剩余的链表移入，生成新链表。

time: 100% O(n);
space: 99.7% O(n);

455. Assign Cookies

贪心Greedy

分别排序小孩需求g, 和cookie供给s.
for loop
比较需求，while 需求r (in g)大于供给s[j] && j没走到头，右移供给指针j。
if 指针j没走到头，那么当前小孩得到满足，++ans。右移指针j。
开始check下一个小孩

最后循环完毕，返回ans，表示被满足的小孩数。

Time: O(g) + O(s)
Space: O(glog(g)) + O(slogs)

404. Sum of Left Leaves

Binary Tree

递归 求出 左子树 和 右子树 的左叶子节点的值的和
if 左子树不为空，但其左右节点为空时， 记录当前左子树的值，
递归 累加sum。

Time: 100.00% O(n)
Space: 99.25% O(logn)

70. Climbing Stairs

动态规划DP

F = climbingStairs(i)
F[i] = f[i-1] + f[i-2]

斐波那契数列
递归解决。

Time: O(n)
Space: O(n)[/i]

79. Word Search

Search
BFS vs DFS

遍历搜索首字母，然后用BFS递归搜索下一个字符。
search (x,y,d):
if out_of_bound return false;
if word[d] != grid[x][y] return false;
if d == word.size()-1 return true;
return search(上下左右，d+1)

Time: O(m*n*4^l)  98.97%
Space: O(m*n + l)  98%

optimize:  const string& word   word定义为常量指针