LeetCode刷题日常记录

本人作为19fall入学学生，深感转专找cs实习和full time的不易，决定入学前抓住个人时间上相对自由的机会，刷够一定的题量，尽早做好面试准备。

从1月份开始刷题，目前我已经刷了200题，正好借此机会开个帖子记录一下刷题的日常。

不过我不希望因为打卡而把刷题变成每天的负担。我希望细水长流，只要每天多少有点感悟，就是刷题的意义。


LeetCode总结已经转移至github上：https://github.com/GarhomLee/LeetCode

加油加油！我现在面临两个月找到下家！也要开始奋斗刷题了！

3/21

45. Jump Game II
属于Greedy method，目前还不太熟练。题目假定一定能跳到last index，所以只需遍历找出目前的jump range里能跳到的最远index，当遍历到当前记录的最远index时jump++，同时更新jump range到最远index。

179. Largest Number
要利用数组里的数组成Largest Number，观察可知规律为把每个数转化成string然后从大到小排序。关键点在于当空digit和0比时（如"3"和"304"）必定是前者排在前面。思路是比较a+b和b+a（如a="3", b="304", a+b="3304", b+a="3043"），构造新Comparator用以比较。

324. Wiggle Sort II
Intuition：先排序，然后从前半部分挑一个到新数组，接下来从后半部分挑一个到新数组。从low index挑数字会导致错误（如[4,5,5,6]），因此需要从high index挑数字，才能满足题目要求。
Follow up：看不懂

371. Sum of Two Integers
Bit manipulation熟练度也是很低。需要用到的operator：&，^，<<。其中&用来记录carry，^用来模拟addition但without carry，<<用来把carry挪到正确的位置。维护两个variable，其中一个记录目前计算结果，另一个记录carry。

191. Number of 1 Bits
比较tricky，需要知道一个规律：the least 1  in n in bit can be diminished by (n & (n - 1))。因此当n!=0时，每做一次(n & (n - 1))，结果数就+1。

231. Power of Two
Inspired by 191. Number of 1 Bits，只需做一次(n & (n - 1))然后看n是否等于0.

318. Maximum Product of Word Lengths
关键在于如何判断是否有shared letters。方法是维护一个integer array，每个元素是一个mark，对应每个word用了哪些letter。具体方法是用1<< (c - 'a')给出现的letter一个1作为mark并“推”到相应，然后mark[i] |= 1<< (c - 'a')和之前的结果合并。

04/11


76. Minimum Window Substring

属于sliding window的经典题目。解法可分为两种：可以用HashMap储存T中出现的字符和次数，那么在S的遍历中可以不考虑其他字符；也可以用长度为128（或256）的数组，这时要注意除了T中出现的字符，其他字符的次数最大为0。
解法一：HashMap
1）遍历T，在HashMap中key为T的字符，value为字符出现的次数。维护一个total变量，表示T字符总数。total的意义：和HashMap中的value共同确定是不是找到了所有的所要求字符。如果不用total，只能不停遍历key来询问是不是所有value都<=0（即所有字符都出现了），效率很低。
2）维护left和right两个pointer，作为sliding window的边界；同时维护minLen来获得最短长度的信息，维护minLeft，minRight找到最短长度对应的substring起止位置
3）right右移，遇到T中的字符，对应的value--。如果这时value >= 0，说明还没找完（或刚找完）所有字符，那么total--
4）当total == 0时，说明在window当中已经包含了所有T的字符，那么开始通过移动left来尝试缩小window
5）进行while循环，left左移。遇到T中的字符，对应的value++。如果这时value >= 0，说明还没找完（或刚找完）所有字符，那么total++，这时候total将会大于0，window不满足要求，会跳出循环
6）比较当前找到的window和minLen
7）Time complexity: O(S的长度)，因为每个元素被扫描了两遍; Space complexity: O(T的长度)


解法二：数组
1）基本过程和解法一相同。唯一不同点在于，没有查找S字符是否在T中，而是通过对应的数组value来判断。这是因为，只有T中出现的字符value才会大于0，其他字符的次数初始都为0。只有数组value > 0，才能对total进行++和--操作，原因还是在于total记录的是与T中的字符有关的信息。
2）Time complexity: O(S的长度)，因为每个元素被扫描了两遍; Space complexity: O(T的长度)

1. // 解法一
   
2. class Solution {
   
3.     public String minWindow(String s, String t) {
   
4.         if (s == null || s.length() == 0 || t == null || t.length() == 0) return "";
   
5.         String minWindow = "";
   
6.         //int[] mapping = new int[128];
   
7.         char[] sArray = s.toCharArray(), tArray = t.toCharArray();
   
8.         Map<Character, Integer> map = new HashMap<>();
   
9.         
   
10.         for (int i = 0; i < tArray.length; i++) map.put(tArray[i], map.getOrDefault(tArray[i], 0) + 1);
    
11.         int total = tArray.length;
    
12.         
    
13.         int left = 0, right = 0;
    
14.         int minLen = sArray.length + 10, minLeft = -1, minRight = -1;
    
15.         while (right < sArray.length) {
    
16.             if (map.containsKey(sArray[right])) {
    
17.                 if (map.get(sArray[right]) > 0) total--;
    
18.                 map.put(sArray[right], map.get(sArray[right]) - 1);
    
19.             }
    
20.             right++;
    
21.                
    
22.             while (left < right && total == 0) {
    
23.                 if (map.containsKey(sArray[left])) {
    
24.                     map.put(sArray[left], map.get(sArray[left]) + 1);
    
25.                     if (map.get(sArray[left]) > 0) total++;
    
26.                 }
    
27.                 left++;
    
28.                     
    
29.                 if (right - left + 1 < minLen) {
    
30.                     minLen = right - left + 1;
    
31.                     minLeft = left - 1;
    
32.                     minRight = right;
    
33.                     //System.out.println(minLeft + ", " + minRight + ", minLen: " + minLen);
    
34.                 }
    
35.             }
    
36.         }
    
37.         if (minLeft != -1 && minRight != -1) minWindow = s.substring(minLeft, minRight);
    
38.         return minWindow;
    
39.     }
    
40. }
    
41. 
    
42. // 解法二
    
43. class Solution {
    
44.     public String minWindow(String s, String t) {
    
45.         if (s == null || s.length() == 0 || t == null || t.length() == 0) return "";
    
46.         String minWindow = "";
    
47.         int[] mapping = new int[128];
    
48.         char[] sArray = s.toCharArray(), tArray = t.toCharArray();
    
49.         //Map<Character, Integer> map = new HashMap<>();
    
50.         
    
51.         for (int i = 0; i < tArray.length; i++) mapping[tArray[i]]++;
    
52.         int total = tArray.length;
    
53.         
    
54.         int left = 0, right = 0;
    
55.         int minLen = sArray.length + 10, minLeft = -1, minRight = -1;
    
56.         while (right < sArray.length) {
    
57.             if (mapping[sArray[right]] > 0) total--;
    
58.             mapping[sArray[right]]--;
    
59.             right++;
    
60.             
    
61.             while (total == 0 && left < right) {
    
62.                 mapping[sArray[left]]++;
    
63.                 if (mapping[sArray[left]] > 0) total++;
    
64.                 left++;
    
65.                 if (right - left + 1 < minLen) {
    
66.                     minLen = right - left + 1;
    
67.                     minLeft = left - 1;
    
68.                     minRight = right;
    
69.                     //System.out.println(minLeft + ", " + minRight + ", minLen: " + minLen);
    
70.                 }
    
71.             }
    
72.         }
    
73.         if (minLeft != -1 && minRight != -1) minWindow = s.substring(minLeft, minRight);
    
74.         return minWindow;
    
75.     }
    
76. }

复制代码

189. Rotate Array

题目要求三种解法，甚至需要用O(1)空间。
解法一：copy新数组，根据新index一个个赋值，用O(n)空间。
解法二：循环替代。每次循环中，把当前元素赋值给右边相隔k的位置，直至回到原点。
解法三：三次翻转。第一次，翻转整个数组；第二次，翻转前k个数；第三次，翻转后n - k个数。很精妙。


1. Two Sum

老朋友了。直接上最最优解HashMap。


167. Two Sum II - Input array is sorted

1的follow-up，也没什么难度，常规经典的two pointers从nums[0]和nums[length - 1]向中间缩小范围。


653. Two Sum IV - Input is a BST

将2sum的input变为了BST，做法有所改变。两种解法。
解法一：利用BST inorder traversal转化为sorted array的特性，转化为167题。
解法二：利用HashSet
1）HashSet储存两个加数当中已经被遍历的一个，那么只需当前node的value和HashSet里的某个数加和为target即可。
2）如果没有，那么把当前node的value加入HashSet备用，同时用recursion查找左右子树，直至null时返回false。
3）Time complexity: O(n); Space complexity: O(n)

1. class Solution {
   
2.     Set<Integer> set = new HashSet<>();
   
3.     public boolean findTarget(TreeNode root, int k) {
   
4.         if (root == null) return false;
   
5.         if (set.contains(k - root.val)) return true;
   
6.         set.add(root.val);
   
7.         return findTarget(root.left, k) || findTarget(root.right, k);
   
8.     }
   
9. }

复制代码

152. Maximum Product Subarray

属于dynamic programing，可以看作是53. Maximum Subarray的升级版。
1）维护currMax表示包含当前nums[i]元素在内的局部最大值（局部的定义是从最近一个0元素到当前nums[i]）；维护currMin表示包含当前nums[i]元素在内的局部最小值；维护max表示全局最大值，最后返回之
2）在遍历array元素的过程中，不断更新currMax，currMin，和max。当nums[i] < 0时，currMax * num[i]会变为最小，currMin * num[i]会变为最大，所以有两种更新的方式：
（a）因为currMax要取currMax * num[i]，currMin * num[i]，和nums[i]三个数的最大，同理currMin要取currMax * num[i]，currMin * num[i]，和nums[i]三个数的最小，如果不做临时储存，那么更新了currMax必然会导致更新currMin时用以比较的数发生改变，导致错误。所以先tempMax = currMax，tempMin =currMin，然后根据tempMax * num[i]，tempMin * num[i]，和nums[i]来更新，避免currMax和currMin的纠缠产生的错误。
（b）当nums[i] < 0时，currMax和currMin先行交换，然后currMax取currMax * num[i]和nums[i]的最大，currMin取currMin * num[i]和nums[i]的最小，同样可以避免由于currMax和currMin的纠缠产生的错误。
3）遍历过程中更新max。
4）Time complexity: O(n); Space complexity: O(1)

1. class Solution {
   
2.     public int maxProduct(int[] nums) {
   
3.         if (nums == null || nums.length == 0) return 0;
   
4.         int currMax = nums[0], currMin = nums[0], max = nums[0];
   
5.         for (int i = 1; i < nums.length; i++) {
   
6.             int tempMax = currMax * nums[i], tempMin = currMin * nums[i];
   
7.             currMax = Math.max(Math.max(tempMax, tempMin), nums[i]);
   
8.             currMin = Math.min(Math.min(tempMax, tempMin), nums[i]);
   
9.             max = Math.max(currMax, max);
   
10.         }
    
11.         return max;
    
12.     }
    
13. }

复制代码

128. Longest Consecutive Sequence

挺有意思的一道题。最开始想用union find，然而发现当元素为负数时array-based union find不适用，只好放弃。
有online和offline两种解法。
解法一：offline的HashSet解法，实际上是利用了HashSet的特性将unsorted array转化成了类似sorted array的性质。
1）先遍历一遍，把所有元素加入HashSet
2）第二次遍历，寻找可能的consecutive sequence最左边的元素，并以之为起点寻找是否有+1的元素来组成consecutive sequence，记录length并更新maxLen
3）Time complexity: O(n); Space complexity: O(n)


解法二：online的HashMap解法，模拟已发现的consecutive sequence。其中重要的key为已发现的consecutive sequence的两个端点，重要的value为这两个端点之间的consecutive sequence的长度。
1）如果num[i]的-1和+1的数同时存在，说明nums[i]可以连接两个consecutive sequences，那么根据端点保存的长度信息找到连接后新sequence的左右端点，并更新为最新的长度
2）如果只有num[i]的-1的数存在，说明nums[i]是作为新的右端点，那么找到左端点，并更新长度信息
3）如果只有num[i]的+1的数存在，说明nums[i]是作为新的左端点，那么找到右端点，并更新长度信息
4）遍历的过程中更新maxLen
5）Time complexity: O(n); Space complexity: O(n)

1. // 解法一
   
2. class Solution {
   
3.     public int longestConsecutive(int[] nums) {
   
4.         if (nums == null || nums.length == 0) return 0;
   
5.         Set<Integer> set = new HashSet<>();
   
6.         for (int i = 0; i < nums.length; i++) {
   
7.             set.add(nums[i]);
   
8.         }
   
9.         
   
10.         int maxLen = 0;
    
11.         for (int num : nums) {
    
12.             if (set.contains(num - 1)) continue;
    
13.             int currLen = 0;
    
14.             while (set.contains(num)) {
    
15.                 currLen++;
    
16.                 num++;
    
17.             }
    
18.             maxLen = Math.max(maxLen, currLen);
    
19.         }
    
20.         return maxLen;
    
21.     }
    
22. }
    
23. 
    
24. // 解法二
    
25. class Solution {
    
26.     public int longestConsecutive(int[] nums) {
    
27.         if (nums == null || nums.length == 0) return 0;
    
28.         
    
29.         Map<Integer, Integer> map = new HashMap<>();
    
30.         int maxLen = 1;
    
31.         
    
32.         for (int i = 0; i < nums.length; i++) {
    
33.             if (map.containsKey(nums[i])) continue;
    
34.             int newLen = 1;
    
35.             map.put(nums[i], 1);
    
36.             if (map.containsKey(nums[i] - 1) && map.containsKey(nums[i] + 1)) {
    
37.                 int leftBoundary = nums[i] - map.get(nums[i] - 1), rightBoundary = nums[i] + map.get(nums[i] + 1);
    
38.                 newLen = map.get(nums[i] - 1) + map.get(nums[i] + 1) + 1;
    
39.                 map.put(leftBoundary, newLen);
    
40.                 map.put(rightBoundary, newLen);
    
41.             } else if (map.containsKey(nums[i] - 1)) {
    
42.                 int leftBoundary = nums[i] - map.get(nums[i] - 1);
    
43.                 newLen = map.get(nums[i] - 1) + 1;
    
44.                 map.put(leftBoundary, newLen);
    
45.                 map.put(nums[i], newLen);
    
46.             } else if (map.containsKey(nums[i] + 1)) {
    
47.                 int rightBoundary = nums[i] + map.get(nums[i] + 1);
    
48.                 newLen = map.get(nums[i] + 1) + 1;
    
49.                 map.put(rightBoundary, newLen);
    
50.                 map.put(nums[i], newLen);
    
51.             }
    
52.             maxLen = Math.max(newLen, maxLen);
    
53.         }
    
54.         
    
55.         return maxLen;
    
56.     }
    
57. }

复制代码

加油啊 我也是转码 从最近开始刷题

ljx123456 发表于 2019-3-22 08:53
加油啊 我也是转码 从最近开始刷题

加油加油

3/22

199. Binary Tree Right Side View
可以用DFS和BFS两种方法做。其中DFS用helper method做recursion，BFS用Queue，都是先看right child再看left child。

226. Invert Binary Tree
同样可以用DFS和BFS两种方法做。DFS还是recursion；BFS用Queue，先从Queue里拿一个TreeNode，交换left child和right child位置，再把children nodes加入Queue。

加油，我也刷，不过刷得很慢

3/25

235. Lowest Common Ancestor of a Binary Search Tree
可以用DFS，很显然可以用recursion。既然是BST，如果要找的两个node都比root小，就找left child；如果都比root大，就找right child；否则root即为所求。也可以用BFS，维护一个node记录当前node，node的改变方向同上。

236. Lowest Common Ancestor of a Binary Tree
Intuition用DFS的recursion，不同于235题之处在于此时不是BST。思路是recursively得到左右子树的Lowest Common Ancestor (LCA)，如果一边为空，那么LCA即为从另一边得到的node。如果都不为空，说明被查找的node分布两侧，所以LCA为当前node。既然是从root往leaf找，那么边界条件是：如果root == null，return null；如果root和p（或q）相等，那么LCA即为p（或q）。

257. Binary Tree Paths
利用helper method，维护一个list、当前path、和当前node。当到达leaf（即左右子树为空）时，将当前的path加入list。

337. House Robber III
类似于array-based robbery的一个DP问题，只是此时要同时考虑左右子树。对于每个node，维护一个数组，其中[0]表示当前node没有被robbed，[1]表示当前node被robbed了。因此，[0]可以由左子树的两种状态最大值+右子树的两种状态最大值决定，而[1]只能由左子树[0]+右子树[0]得到（因为如果当前node被robbed了，相连的子树都不能被robbed）。最后返回max([0], [1])

200. Number of Islands
经典的二维数组DFS题目。用helper method来recursively“吞掉”岛屿，具体实现是：当遇到‘1’时，替换成‘0’（沉没了），并搜索上下左右的邻居，直至出界或碰到海（即‘0’）为止。

3/26

207. Course Schedule
在graph中DFS。首先construct a graph by adjacency lists (using list of lists)，然后将edge信息依次填入graph。利用helper method，维护一个数组state记录每个vertex的状态：0表示not seen，1表示visiting，2表示visited。当遇到state[vertex] == 1, return CYCLE; 当state[vertex] == 2, return OK; 否则，探索neighbor，更改state，并返回结果。

210. Course Schedule II
相当于207题的follow up。属于topological sort。代码基本和207题一样，helper method也是判断是否出现cycle。不同之处在于，增加一个result数组，并从后往前update（因为DFS找到的第一个vertex一定处于最末尾）。只有当没有cycle时才update result数组。

3/27

332. Reconstruct Itinerary
由于题目要求需要到达城市需要按smallest lexical order，所以在graph construction的时候用list of priority queue。当遍历某个vertex的neighbor时，从pq里poll。最先到头的vertex应该放在result list的最末尾。

394. Decode String
1）使用两个栈，countStack存子串的重复次数，resStack存中间结果
2）读取到的character为一个数字，把count * 10 + 当前character。
3）读取到'['时，需要暂存目前的数字（重复次数）和当前得到的res，分别push进countStack和resStack，重置count和res。
4）读取到']'时，取出最近一次暂存的中间计算结果，也就是resStack的栈顶，再append n次res，n为countStack的栈顶，res为最近一次被[]框住的子串。得到的结果为当前']'所属的n[]的结果。
5）其他情况，将字符追加到res末尾

310. Minimum Height Trees
反向的BFS。Brute force做法是将所有node作为tree root的情况下的height求出来，然后取最小值及其所对应的node。然而，对每个node，都有O(n)时间复杂度的求height过程，这样总的时间复杂度应该是O(n^2)，会造成Time Limit Exceeded。优化的做法是，记录每个node的degree，然后将degree为1的node（即leaf）找出来。接下来，依次删除这些leaf，同时更新与之相连的node的neighbor list（将此leaf从中删去）和degree，完成后如果这个node的degree变为1，即成为新的leaf。每次循环将新产生的leaf存起来。

3/28
399. Evaluate Division
Intuition：构建一个directed graph，这里用map of maps。外层map的key为从numerator，value为内层map；内层map的key为denominator，value为二者之商。因为这是directed graph，所以边的两个方向都要加进去。然后判断，如果query数组中只要有一个数不在map中，即返回-1.0；否则，用一个helper method求解。在helper中，维护一个boolean array，以防走回头路；遍历numerator的value，作为intermediate。如果intermediate即为“final denominator”，返回1.0；如果有再次调用helper求解从intermediate到“final denominator”的解，有解（即返回的数>0），如要求a / c，有a / b和b / c，b为intermediate，那么返回他们的乘积。如果遍历完都没有返回，意味着没有通路，返回-1.0。
另外还能用union find做，不是很懂。

146. LRU Cache
一道design题，实现方法为map（从key到自己构建的node）+ double-linked list（元素为node）。map的意义在于get()用O(1)时间。double-linked list需要提供moveToHead(Node node)，addToHead(Node node)，和removeTail()方法。如果moveToHead调用了addToHead方法，cache capacity由map.size()控制，double-linked list可以不维护size，否则不好维护size。

284. Peeking Iterator
在使用built-in Iterator的基础上，用一个trick，那就是先调用next()并存起来（如peekVal。当peek()被调用时，返回缓存的peekVal。当Peeking Iterator的next()被调用时，返回调用前的那个peekVal，内部Iterator同时也调用next()，此时需检查hasNext()，并更新peekVal。当Peeking Iterator的hasNext()被调用时，可以依据peekVal是否为null，因为它就是被预先调用缓存的next值。