10.4 - hard总结3

212. Word Search II: 创造一个Trie，然后依loop整个矩阵
214. Shortest Palindrome: 翻转一下再进行判断
218. The Skyline Problem： 先拆分点，然后把所有复合的building都加入到heap里，并且把所有不符合的都pop出来，最后取heap的第一个值作为这个点的高度，并且加入到最后的结果里
224. Basic Calculator: 利用stack的一道题，不过写起来不是那么容易写
233. Number of Digit One：一道数学运算题。。。希望不要考吧。。。
239. Sliding Window Maximum: 用deque维护一个递减序列
248. Strobogrammatic Number III: 先找出等长度范围内的所有的值，然后再去掉不在low和high之间的值
265. Paint House II: 二维dp，三重循环
269. Alien Dictionary: 拓扑排序
272. Closest Binary Search Tree Value II: 要用inorder traversal还挺简单的，但是如果要小于O(n)的时间复杂度就有点麻烦了，要先做两个iterator，然后依次来做
273. Integer to English Words: 这题比较扯淡
282. Expression Add Operators： 一道backtracking的题目，只是在backtracking的时候要注意保存了前一个值，因为后面可能会出现乘号
291. Word Pattern II: 一道backtracking的题目
295. Find Median from Data Stream: 两个heap来做
296. Best Meeting Point: 找横坐标和纵坐标的中位数
297. Serialize and Deserialize Binary Tree: 直接用preorder加上括号来做
301. Remove Invalid Parentheses: 一层一层remove，先remove 1个获得一系列，然后在这一系列里再remove一个，如果一系列的result都是valid，那么返回这一系列
302. Smallest Rectangle Enclosing Black Pixels: 基本的想法是，给定一个点，然后以这个点
305. Number of Islands II: 针对其上下左右四个点，每成功的union一次就减去一个count
308. Range Sum Query 2D - Mutable: 获取一个按行或者按列的prefixsum就好了