蜗居匹兹堡孤独刷题中

Day 17 - 2019/02/21

310. Minimum Height Trees
一道很好的树和图结合的题。了解到了一些基本概念：比如A path graph is a tree with two or more vertices that is not branched at all.
多点出发的BFS，从leaf出发，如果两个leaf相遇了，就合成一个，继续往前走，终止条件是只剩下两个或者两个以下的node。具体实现是根据degree of a vertex实现的。这道题要多次练习。
时间复杂度是O(n)

847. Shortest Path Visiting All Nodes
这也是一道非常好的图的题。难得可以练到多路径同时BFS。而且也难得练到了override equals and hashcode
在给定路径下，如何不重复走是关键。这里用到了Bitmask
时间复杂度time complexity is also n*(2^n), because each node may be visited 2^n times
DP方法暂时没练，貌似时间复杂度并未优化。

317. Shortest Distance from All Buildings
这道题显然也是在图上多点出发的BFS，区别是在二维矩阵上进行。思路上和310很相似，但实现方式非常值得一练
基本上可以说是暴力法。就是用BFS求每个空地到所有building的最短距离之和。
对于一个给定building做BFS的时候，途径#empty，所以总时间复杂度是O(#Building * #Empty) = O(n^2 * m^2)
空间复杂度是 O(n^2 * m^2)

如何优化？可以在BFS过程中进行一些剪枝。讨论区的做法是，只走前一个building走过的路，这样还省了visited set，但是坏处是改变了input。

863. All Nodes Distance K in Binary Tree
也是一个Tree和Graph结合的题目。怎么建图呢？用parentMap，然后就可以BFS了。

787. Cheapest Flights Within K Stops
这是第二次碰到权重图的题，一看就是Dijkstra算法啦。
Dijkstra's single source shortest path Algorithm(权重图最短路径算法)

Day 18 - 2019/02/22
913. Cat and Mouse
研究了一个小时，果断放弃吧

675. Cut Off Trees for Golf Event
这样的题目才是应该多练的好题，思维难度和编程量都比较中肯。BFS
Build minHeap用了O(mn)时间，一共有O(mn)棵树，BFS是O(mn)，一共是O(mn) + O(mn * mn)) = O(m^2n^2);

490. The Maze
没有仔细读题，想当然写了一个BFS。
DFS和BFS都练了一下。通过这道题，掌握了在矩阵中朝一个方向滚动的技术。

505. The Maze II
完全按照Dijkstra算法做的。将可以滚到的点看作权重图中的点，将每次滚动的距离看作权重，用Map记录node到原点的距离，通过extractMin和decreaseKey的操作找到最短路径。因为没有用heap，所以很慢，想用heap做，但是不知道如何实现decreaseKey操作，因为pq没有提供update的操作。总不会为了优化再实现一个HashHeap吧？

根据讨论区里的一个高票答案写了一遍，不用update，而是再加入一个新的node，这个node有相同的坐标，不同的distance。。
这是Dijkstra的变形写法，总结下来就是用PQ实现extractMin，不用decreaseKey操作，而是创建add新node进入PQ，此时相同位置的两个点同时存在PQ里，但是总距离近的那个会被先poll出来。这时候用一个Set记录走过的path，相同位置的两个点，只有距离近的那个点会走到。因此间接实现了decreaseKey操作。

499. The Maze III
几乎和505完全一样
注意：这道题可以练习一下override compareTo方法
注意： Arrays.equals(array1, array2) will not work as you expect on 2D arrays.

Day 19 - 2019/02/23

告诫自己的话：
刷题的时候要注意算法的通用性，不要浪费时间在奇技淫巧的算法上，没有一般意义就没必要研究。
不过过分追求时间复杂度的优化。多注意代码质量，注意大函数分成多个小函数。

323. Number of Connected Components in an Undirected Graph
练了一下DFS和BFS，并查集以后集中练吧。
DFS的时间复杂度我觉着是O(n^3),讨论区大部分说是O(n^2),再想想，确实应该是O(n^2)
BFS的时间复杂度应该也是O(n^2)。

Day 20 - 2019/02/24

13. Roman to Integer
分步骤，先把roman string转化成int数组，然后计算的规则是，如果这个num小于下一个num，就减，反之加。

12. Integer to Roman
首先穷举Integer和Roman的所有对应情况
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

6. ZigZag Conversion
这类题就是要看清题意，严格根据题意进行实现。

3. Longest Substring Without Repeating Characters
双指针之sliding window。 注意问面试官对于charset的假设。
Java (Assuming ASCII 128)
The previous implements all have no assumption on the charset of the string s.
If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.
Commonly used tables are:
int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII

14. Longest Common Prefix
Horizontal scanning 和 Vertical scanning都掌握一下，时间复杂度都是O(Ln), 其中L是字符串的平均长度。
这道题也可以用分治法练一下，但时间复杂度没有优化。
答案里这道题还用了二分法，觉着没什么意思就先不看了。
答案中这道题的follow up是一道可以用字典树做的题：
Given an array of strings S，find the longest common prefix among a string q and S. This LCP query will be called frequently.

Day 21 - 2019/02/25

今天主要是时间花在做总结上了

5. Longest Palindromic Substring
1）这道题暴力法是O(n^3);
2）中心线法(Expand around center)可以优化到O(n^2), 好好理解一下这个中心线，说不定其他题可以用的上。
有好几处与下标有关容易写错的地方，需要多练。
3）动归解法。从暴力解里可以看出，很多地方都重复计算了。因此可以用记忆化搜索. 正着反着都可以写。要多练。

38. Count and Say
这种题就是多写。

49. Group Anagrams
排序法比较好

Day 22 - 2019/02/26

8. String to Integer (atoi)
要注意两点：1)more than one sign characters; 2)overflow

657. Robot Return to Origin
注意写的简洁

273. Integer to English Words
这个题就背住了，多打几遍。

804. Unique Morse Code Words

28. Implement strStr()

557. Reverse Words in a String III
三种方法都要会

java.lang.StringBuilder.reverse() method

// Convert ArrayList to Array
return list.toArray(new String[list.size()]);

43. Multiply Strings
光背住是不行的，关键是举一个例子并画出位置关系,想一想哪一位的计算在此时结束了，哪一位未来还有累加。
还有一点要记住的是，num1.length() = n, num2.length() = m, 则乘积的长度为m + n

709. To Lower Case

383. Ransom Note

65. Valid Number
点不能在e后面出现，e前面必须有num，点前面可以没有num，+/-如果出现在中间的话前一位必须是e

345. Reverse Vowels of a String

默默的问一下楼主有去icc吗。。。

Day 23 - 2019/02/27

125. Valid Palindrome
Character.isLetterOrDigit(char c)
Character.toLowerCase(char c)

609. Find Duplicate File in System
下面这些方法学习一下：
String[] name_cont = values.split("\\(");
name_cont[1] = name_cont[1].replace(")", "");
List < String > list = map.getOrDefault(name_cont[1], new ArrayList < String > ());
list.add(values[0] + "/" + name_cont[0]);
map.put(name_cont[1], list);

Follow up值得一看。
https://leetcode.com/problems/fi ... nswers-to-follow-up
其中，不太同意他的时间复杂度分析。如果有n个file，content平均长度k，我觉着仍然是O(nk)

165. Compare Version Numbers
这个题解法非常好，要多练几遍
不用split和Integer.parseInt()写一写

681. Next Closest Time
从最后一位开始替换，规则是如果能找到一个数字比现有数字大，那就可以成功返回了，反之，这一位使用最小可用数字，然后继续往前找。
这个题也值得多练

58. Length of Last Word

71. Simplify Path
第一次使用到了Deque，记住Head是在最右边，pollFirst()相当于stack.pop()
多练。

696. Count Binary Substrings
解法非常巧

68. Text Justification
不好写，多写几遍吧。

第一步是找到当前行能放下哪些词（找到currRowStart和nextRowStart）。
由此，我们知道这一行有几个词，还剩下多少空格。
然后就可以确定是left justfy 还是 full justify。
对于full justify的情况，如果空格不能平均分配，要先往左分配。

感觉这个题还是蛮好的。主要是要分步骤，然后大函数分成小函数。

227. Basic Calculator II
替换所有空格s = s.replaceAll("\\s", "");
不错的题。

224. Basic Calculator
只有加减和括号。这种题也是要多练。

541. Reverse String II
题意有误导性

686. Repeated String Match
这道题的一个关键点在于We should stop after we try all possible starting positions of B in A.
当repeat后形成的str长度大于B的时候，只要再repeat一次，就可以cover掉所有的开始位置了，如果这时候还找不到，那就是没有。
时间是O(n * (n + m)), 空间是O(n + m)

Day 24 - 2019/02/28

今天用pramp模拟面试了一下，体验非常好！ 面试我的同学非常nice，水平很高，又很有耐心。我感觉学到了很多东西: 首先，拿到题之后，我应该多进行一些clarification，然后讲自己的算法。写完代码之后，一定要带上一个case跑一遍，其实应该不光跑一个case，要像使用auto testing工具一样，使自己的case能够cover代码的所有branch。平时写代码的时候也应该耐心的进行这个过程，养成好习惯。

680. Valid Palindrome II
剔除其中一个数，分别进行双指针操作

170. Two Sum III - Data structure design
这样一道简单的题，其实就很见功力。我就是做的遍数太少，每道题思考的也还不够，虽然做了四百多道，但是做的根本就不够透彻。
既然这是一道设计数据结构的题，就应该考虑到不同操作的性能上的取舍。这些是要和面试官沟通的。同时对于不同的要求，脑子里都要有解决方案。所以这道题写两套程序。

Day 25 - 2019/03/01

15. 3Sum
rst.add(Arrays.asList(nums, nums[left], nums[right]));

611. Valid Triangle Number 可以有重复解
Cant use Arrays.sort() for Array Sort descending

16. 3Sum Closest
注意写的简洁

18. 4Sum

Two Sum - difference equals to target
很想做做这道题

215. Kth Largest Element in an Array
这道题非常重要，Quick Select算法是很多其他题的算法基础，每个细节都一定要清清楚楚。
主要的算法思想是，通过partition，我们可以知道比某个数大的数有多少个，比某个数小的数有多少个，这时候我们就能判断那个第K大的数在哪边，从而排除另外一边。
T(n) = O(n) + T(n / 2)
     = O(n) + O(n / 2) + T(n / 4)
     = ...
     = O(n)
首先，Quick Select的最坏情况是O(n^2),平均情况是O(n), 取决于partition的时候是否能均分，如果每次partition之后，只能把T(n)变成T(n-1),这时候总时间复杂度就是O(n^2)

1）pivot的选定：选最左边和最右边都不好，要选中间。 比如[6，5，4，3，2，1], 找第一大，如果选pivot为1。
2）等于pivot的数的处理：不要规定这个数去某一边，设想一下所有数都相等的时候，会导致时间复杂度为O(n^2).
3）while (left <= right): 这样才能保证partition过程的完成，array会被分成两个部分，或者三个部分。


80. Median  https://www.lintcode.com/problem/median/description
通过这道题，我应该意识到自己非常的瞎。写出while(left < start)这样的东西，怎么就是自己看不出来。
有个控制奇数和偶数除以2的得数的小技巧：(nums.length + 1) / 2

4. Median of Two Sorted Arrays
首先，思维转化，找第K大的数。
然后，如何把K / 2个数排除在外。比较两个数组中的第K/2个数（不管奇偶，是奇的话，就少扔掉一个数），我们可以安全的扔掉第K/2个数较小的数组中的那K/2个数。
最后，递归出口有三种情况，1）A数组起始位置超界；2）B数组起始位置超界；3) K = 1；
还有一个小技巧是处理数组中元素个数不足K/2，int keyA = Integer.MAX_VALUE; if (startA + k/2 - 1 < A.length) keyA = A[startA + k/2 - 1];

Partition Array by Odd and Even
当时面试的时候，这道题我竟然墨迹了半天