【自我鼓励帖】1月9号脸家实习二面前的刷题日记

楼主大三小白一个，学编程不到一年，上学期刚刚开始刷LEETCODE，之前根本不知道。运气好朋友内推脸家实习，给了电面，一面侥幸通过，希望剩下这几天二面前好好刷题+复习+总结。接下来有机会奉上脸家TAG的和其他的一些类型的总结

12.27.17

• 227. maximal square, medium
• 
  
  • DP的空间复杂度从2D优化为1D：可以引入temp var来存需要的值，以及注意更新dp/dp[j]
    
    
• 84. largest rectangle in histogram, hard
• 
  
  • 利用stack来做计算，很巧妙，用i—来维持右边最短边，用stack.peek()直到找出左边最短边，求出面积
    
• 85. maximal rectangle, hard
• 
  
  • 和84相比, run time 从O(n)变成了O(mn)，而且最后不能用84中的col—
  • 感觉84和85都没有完完全全吃透，还要再复习
    
• 274. h-index, medium
• 
  
  • bucket sort的妙用，将run time 从 O(nlgn)降到O(n)，但是space从O(1)增加到O(n)
    
• 275. h-index ii, array is already sorted
• 
  
  • medium, 这时用binary search
    
• 404. sum of left leaves, easy
• 
  
  • iterative: DFS, BFS
  • recursive
    
• 27. remove element, easy
• 
  
  • two pointers, very easy
    
• 80. Remove Duplicates from Sorted Array II, medium
• 
  
  • 比较简单，传统的two pointers的题
  • 可以将问题转化为allow at most k duplicates
    
• 122. Best Time to Buy and Sell Stock II, easy
• 
  
  • easy, DP + greedy
    
• 123. Best Time to Buy and Sell Stock III, hard
• 
  
  • 方法真的太骚了
  • DP
    
• 188, Best Time to Buy and Sell Stock IV, hard
• 
  
  • 弄明白了123，其实弄明白188就不难了
  • 总结一下就是将2次交易变成了k次交易，所以需要buy[]与sell[]两个array来存值
    
• 309, Best Time to Buy and Sell Stock with Cooldown, medium
• 
  
  • 方法和123，188很像，但是比它们稍微简单一些，多了一个rest/cooldown，但是可以通过观察之后将它消除，只保存buy and sell
  • 原来的DP space 是O(n)，可以reduce 到O(1)
    
• 714. Best Time to Buy and Sell Stock with Transaction Fee, medium
• 
  
  • 注意714的buy, sell和309 cool down的buy, sell有些不一样，309有prev_sell和存当前sell的old_sell，714只有old_sell
  • 最好在买的时候算fee，这样避免buy(Integer.MIN_VALUE)引起的underflow
    

介于FB tag已经基本刷完，而且刚好也上了20道，现在距离二面也只有一周了，所以现在基本上以分析、总结、归类为主，遇到某个类型的相似题目，可以顺便刷一刷

integer to roman / roman to integer
* 13. Roman to Integer (easy)
    * 从index 0到length-2
        * 如果current char >= next char, sum+= current
        * 如果current char < next char, sum -= current
    * 一个table对应roman 和 integer
* 12. Integer to Roman (medium)
    * return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    * M是千，C是百，X是十，I是一
* 273. Integer to English Words (hard)
    * 像这个系列的题一样，得有一个table或者几个list去存数字到英文的值，本题中存三个list，**注意不包含"zero"，因为“zero”是特殊情况，只有当数为0的时候才会用到**
        * 小于二十: 1~19
        * 十: 10~90
        * 千: 1000, 100,000, 100,000,000
    * 因为这个方法是O(1)的，所以不需要用StringBuilder
    * 在主方法里面检查thousands
    * 在helper方法里面检查小于二十，十和百（加上"Hundred”）

add two (string/binary/number)
* 67. Add Binary (easy)
    * 首先run time不是O(1)，而是linearly related to the size of two input strings, 所以用StringBuilder
    * 从右往左加
    * 这种"add"类的题目，都需要存一个**carry**, 一个**sumOfCurrentDigit**
        * 每次iteration开始时，`sumOfCurrentDigit = carry`
        * 每次iteration中，`sumOfCurrentDigit += digit1 和 digit2`
        * result的`currentDigit = sumOfCurrentDigit % radix(进制)`
        * `carry = sumOfCurrentDigit / radix(进制)`
* 2. Add Two Numbers [linkedlist] (medium)
    * 思路和67 add binary基本一致
    * 每次iteration中，sumOfCurrentDigit += digit1 和 digit2
    * 每次iteraton结束之前
        * result的currentDigit = sumOfCurrentDigit % radix(进制)
        * carry = sumOfCurrentDigit / radix(进制)
    * 因为要新建一个LinkedList，所以需要新建一个dummy，然后node = dummy，最后return dummy.next
* 445. Add Two Numbers II (medium)
    * 和2. add two number的区别是most significant digit comes first，这样的话在建dummy的时候，建成null即可，然后每次都新建一个newHead，让newHead.next = dummy；同样最后还要check一下sum是否为1，如果是1的话，再加一个val为1的newHead
* 415. Add Strings (medium)
    * 和67. add binary基本一样，只是换了进制而已
* 43. Multiply Strings (medium)
    * num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]
    * if(sb.length() != 0 && p != 0) sb.append(p)，这样能够把开头的0去掉

subarray
* 325. Maximum Size Subarray Sum Equals k (medium)
    * sum list, hash map，思路类似two sum
* 1. Two Sum (easy)
    * hash map
* 209. Minimum Size Subarray Sum (medium)
    * 2 pointer: O(n)
        * 用start和end创造一个subarray的window
        * start = 0, end = 0, min = Integer.MAX_VALUE, sum = 0
        * `while (end < nums.length)`
            * 正常情况下sum < k，这时候end++, 更新sum: sum += nums[end]
            * 如果sum >= k了，那么start++, 更新sum: sum -= nums[start]
    * binary search : O(nlgn)，其中binary search是O(lgn), helper method是O(n)
        * 用一个helper叫windowExists的方法，把主方程里的mid当成size来搜索

substring (sliding window)
* 209. Minimum Size Subarray Sum (medium)
    * 2 pointer: O(n)
        * 用start和end创造一个subarray的window
        * start = 0, end = 0, min = Integer.MAX_VALUE, sum = 0
        * `while (end < nums.length)`
            * 正常情况下sum < k，这时候end++, 更新sum: sum += nums[end]
            * 如果sum >= k了，那么start++, 更新sum: sum -= nums[start]
* 76. Minimum Window Substring (hard) 【不用hash map的方法，用hash map的话更具有普适性】
    * two pointers: start and end to represent a window.
    * Move end to find a valid window.
    * When a valid window is found, move start to find a smaller window.
    * 不要用hash map存pattern的char，用int[128]就行了，因为unicode 0~127就包含了基本的拉丁字母和符号了，hash map反而更复杂

    * map里存的是window中待include的char的数量
    * counter: the number of chars of pattern to be found in text
    * (while end < text.length())从end = 0 到 text.length()扫描：
        * if 扫描的endChar对应map的值>0，将它的值-1, counter--
        * 让map里对应的endChar的value-1，（map中对应的char如果是pattern的char，不会<0，如果不对应则会<0）
        * end++，相当于window变大，所以待include的数量减少
        * (while counter == 0)，说明在这个[start, end]区间内有一个valid window
            * update minLength与minStart
            * 让map里对应的startChar的value+1，（如果map里对应的char是pattern的char，此时它的数量会>0）
            * if 该value > 0, counter++
            * start++，相当于window变小，所以待include的数量增加
* 159. Longest Substring with At Most Two Distinct Characters (hard)
    * 套用substring类的题目的模板
    * 区别是，因为只有text，没有pattern，往map里put的时候，可以放在第一个while loop里面
    * if (map.get(c1) == 1) counter++; // new char
* 340. Longest Substring with At Most K Distinct Characters (hard)
    * 159的follow-up
    * 把159中的`while (counter > 2)`换成`while (counter > k)`就好了
* 3. Longest Substring Without Repeating Characters (medium)
    * 思路同159，340，只需要换三行就行了
        * if (map.get(c1) > 1) counter++; // 把之前的 == 1 换成 > 1
        * while (counter > 0) { // 换成 > 0
            * if (map.get(c2) > 0) counter--; // 换成 > 0
* 438. Find All Anagrams in a String (easy)
    * sliding window，基本同76一样，只需要改一点点
* 30. Substring with Concatenation of All Words (hard)
    *
meeting rooms & intervals
* 252. Meeting Rooms (easy)
    * use lambda expression to sort the intervals by start time
    * start time at index i should be no less than end time at index (i+1)
* 253. Meeting Rooms II (medium)
    * 找到最少需要几个meeting room
    * 方法一：分别sort start time和end time
        * loop over starttime list，需要两个var: rooms, endTimePointer
            * 每当startime[i] < endTime[endTimePointer], rooms++ 【starttime[i]是新的meeting, endTime[endTimePointer]是旧的meeting】
            * else endTimePointer++
    * 方法二：sort start time，用min heap存end time
        * loop over intervals (with sorted start time)
            * 如果intervals[i].starttime >= interval_polled.endtime【intervals[i].starttime是新的meeting, heap.poll()是旧的meeting】，这时需要merge end time: interval_polled.end = intervals[i].end
            * else heap.offer(intervals[i]);
            * heap.offer(interval_polled)
* 56. Merge Intervals (medium)
    * sorting
    * make a new list, compare sorted intervals with new list and do merging
* 57. Insert Intervals (hard)
    * 把所有endtime < newInterval.starttime的interval加到result中
    * 把所有overlapping intervals和newInterval merge成一个新的newInterval，替代之前的newInterval，加到result中（用较小的starttime和较大的endtime）
    * 把其他starttime > newInterval.endtime加到result中去

heap
* 23. Merge K Sorted List (hard)
    * heap，对于stream，或者一直改变的structure的sorting，用heap，本题中每个list都在不停的改变
    * 对所有的node : lists，如果node不为null，就offer到heap上
    * while (heap不空)
        * append heap.poll()的第一个node到tail上，在把第二个node开始（即tail = tail.next之后的tail.next）offer到heap上
*

01.01.18

鉴于还差5道就刷到200道题了，而且接下来这一周主要是复习+总结+刷FB面经了，所以先来几个easy和medium热热身
* 292. Nim Game (easy)，感觉是做过最简单的leet code的题了
    * n不能是4的倍数，然后只要n起始不是4的倍数，每次只要我数到4的倍数就肯定能赢。
* 344. Reverse String (easy)
    * 用two pointers去swap，将time complexity从O(n)降低到O(lgn)
* 541. Reverse String II (easy)
    * 挺简单的
* 458. Poor Pigs (easy)
    * while (Math.pow((minutesToTest / minutesToDie + 1), pigs) < buckets) pigs++;

bit manipulation
* 136. Single Number (easy)
    * bit manipulation
    * a xor a = 0, 0 xor a = a
    * xor可传递
    * ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5.
* 137. Single Number II (medium)

复习与归类

task scheduler
* 358. Rearrange String k Distance Apart (hard)
    * 用一个PQ,一个wait的queue
    * 和621 task scheduler不一样的地方是这个需要输出最后的结果，而621只需要输出一个数量；而且621有idle，即空格，而这个题没有
* 621. Task Scheduler (medium)

valid parentheses
* 20. Valid Parentheses (easy)
    * parentheses是挨在一起的，即{}[]，所以这个题和301 remove invalid parentheses不是太像，301需要用回溯法做，这个简单一些，在每个loop的iteration中只需要遇到一个左括号，就push到stack上，遇到右括号就从stack上pop出来和当前的括号比较（如果不一样或者stack is empty）
* 301. Remove Invalid Parentheses (hard)
    * 因为不像20一样括号挨在一起，所以用回溯法（recursive DFS backtracking）
    * 统计左右括号能删的个数，存到左右两个counter（分别代表有多少个左右括号需要删除）中，进行DFS。每个node（字母）有两个children：使用或者不使用，所以分别对两个child进行DFS，DFS的时候每个char有两个branch，一个是使用current char，一个是跳过/不使用current char
    * 之前的代码没有剪枝，所以用set去存结果，但是这样有很多不必要的DFS
    * 优化的代码：不符合情况的branch直接prune掉，不做DFS
        * “不使用/跳过 current char”branch: 在DFS时引入“lastSkipped”这个parameter，如果上一个跳过的char和现在的char是一样的，那么同理继续跳过
        * “使用 current char”branch：如果current char这个左/右括号需要删除（counter > 0），那么就使用\
* 22. Generate Parentheses (medium)
    * 和remove invalid parenthese思路差不多，recursive DFS backtracking

integer to roman / roman to integer
* 13. Roman to Integer (easy)
    * 从index 0到length-2
        * 如果current char >= next char, sum+= current
        * 如果current char < next char, sum -= current
    * 一个table对应roman 和 integer
* 12. Integer to Roman (medium)
    * return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    * M是千，C是百，X是十，I是一
*

12.30.17

FB TAG:

* 218. The Skyline Problem (hard)
    * java运用方面的总结
        *  TreeMap，可以用来代替sorted list
        * comparator的lambda expression
        * 要iterate一个map: `for (Map.Entry<Integer, List<int[]>> entry : cps.entrySet())`，用entrySet()
    * a heap:  keep track of an active set of integer-keyed objects and return the highest one in O(log⁡n) time: a heap
    * 最终思路
        * sort critical points
        * scan across critical points from left to right
        * when we encounter a left edge, add its height to PQ
        * when we encounter a right edge, remove its height from PQ
        * anytime we encounter a critical point, after updating the heap, we update the height to result to be the value peeked from the PQ
* 639. Decode Ways II (hard)
    * 将O(n)的dp array优化为O(1)space
    * 需要考虑的情况
        * 分别考虑X和Y是否是'*'
        * X可以单独解码的条件是：X != '0' （一位数）
        * XY可以解码的条件是：10 <= XY <= 26（两位数）
* 269. Alien Dictionary (hard)
    * CSP问题
    * CSP问题解题方法：
    * 先构造CSP(这个问题中的map)，再构造辅助的degree
    * 用BFS解题
    * course schedule中CSP已经有了（就是prerequisites[][]）
* 410. Split Array Largest Sum (hard)
    * 很巧妙的binary search的方法
        * if m = nums.length，那么每个数组都是一个子数组，所以返回nums中最大的数字即可
        * if m = 1，那么整个nums数组就是一个子数组，返回nums所有数字之和
        * 所以对于其他有效的m值，返回的值必定在上面两个值之间，所以我们可以用二分搜索法来做。
* 721. Accounts Merge (medium)
    * union find
* 68. Text Justification (hard)
    * 这个题考察的更多的是coding能力

paint house 集合：
* 256. Paint House (easy)
    * DP，用dp[i][j]来表示第i个房子涂成j色 + 涂之前所有的到i-1的房子的最低cost

12.28.17

FB TAG:

* 674. Longest Continuous Increasing Subsequence (easy)
    * DP, dif_list
* 525. Contiguous Array (medium)
    * hash map, 如果两个index i 与 j之间的“zero”值一样，说明他们之间有相同数量的0's and 1's，将result更新为他们之间的差值
* 637. Average of Levels in Binary Tree (easy)
    * BFS
* 572. Subtree of Another Tree (easy)
    * tree traversal: O(n^2)
    * serialization + KMP string matching: O(n)
* 751. Number Of Corner Rectangles (medium)
    * 先用两个outer for-loop构造两个横边，用inner for-loop再count满足要求的竖边的数量，在每个inner for-loop结束时，用combination算出满足要求的边，放进result
* 673. Number of Longest Increasing Subsequence (medium)
    * 没太弄明白
* 10. Regular Expression Matching (hard)
    * 典型的matching类问题，注意把dp的space优化为O(n)
    * 用2D的DP时，考虑清楚各种情况：
    * 例如’a*’，就有match到empty string, ‘a’,’aaa…’等三种情况，分别对应的DP的坐标是什么
    * 注意在dp[i][j]时，text/pattern 的current char是charAt(i-1)和charAt(j-1)
* 44. Wildcard Matching (hard)
    * 类似10，稍微有一些不同，同样注意把dp的space优化为O(n)
* 128. Longest Consecutive Sequence (hard)
    * leetcode上真是有人才，用HashSet，然后保证元素n是consecutive sequence最小的一个，往大的方向加

sentence similarity 系列
* 734. Sentence Similarity (easy)
    * not transitive, a map of set
* 737. Sentence Similarity II (medium)
    * transitive
    * DFS
    * union find（不是特别明白）

其他：
* 300. Longest Increasing Subsequence (medium)
    * DP+java自带的binary search

12.28.17

paint house & house robber 专题
*  256. Paint House (easy)
    * DP，用dp[i][j]来表示第i个房子涂成j色 + 涂之前所有的到i-1的房子的最低cost
* 265. Paint House II (hard)
    * 思路和256 paint house差不多，唯一的区别就是以为颜色是k个而不是3个，所以time需要从O(n)变成O(nk)，k是有多少个颜色
    * 还有一点不同的是我们不能强行用Max.min(其他两个颜色)来算costs[i][j]了，所以必须引入two pointers: min1和min2去存目前这一排最小的两个颜色的index，同时也需要last1和last2来存上一排的min1和min2（类似DP空间优化时引入变量来存上一个loop里面的value的思想），然后再dp过程的时候比较看现在的color index j是不是和last1一样，如果一样就用last2，否则就可以安全地用last1的index
    * 最开始的时候min1和min2都被初始化为-1，这样的时候通过判断min1和min2是否<0，就可以知道目前是不是第一排（即第一个房子）了，如果是第一个房子，我们就让第一个房子的每个颜色的cost保持不变就行了
* 276. Paint Fence (easy)
    * DP
    * maintain two variables: diffColorCount和sameColorCount
    * 到每一个房子的时候都有两种情况：
    * 一种是之前两个房子颜色一样，这时候我们：diffColorCount = (diffColorCount + sameColorCount) * (k-1);
    * 另一种是之前两个房子颜色不一样，那么现在颜色就必须得一样了，这时候我们：sameColorCount = (没更新之前的)diffColorCount;
    * 最后将diffColorCount和sameColorCount加在一起就是最后结果
* 198. House Robber (easy)
    * 和276很像，两种情况，一种rob this house，一种not rob this house
* 213. House Robber II (medium)
    * 类似198，但是将“一排房子”换成了“一圈房子”，所以可以分两种情况探讨
        * 从0抢到n-2
        * 从1抢到n-1
* 337. House Robber III (medium)
    * 类似198，但是将房子变成了binary tree
    * 做法跟198相似，用一个helper dfs method分别dfs(left)和dfs(right)
    * 再把抢root的结果存到result[0]，不抢root的结果存到result[1]
    * 最后再输出Math.max(result[0], result[1])

很棒，加油

12.31.17

number of islands专题
* 200. Number of Islands (medium)
    * flood fill algorithm: DFS implementation & BFS implementation
    * DFS更简单直接：如果grid[x][y]是1，以这个点为中心进行DFS，分别将四个方向的‘1’都标为0，然后最后DFS结束后counter++
* 305. Number of Islands II (hard)
    * union find
    * * 按照union find的套路，
    *     * **首先新建parent list**，这时候相当于每个position都是一个岛，`islandCount++`
    *     * 然后再union find / build tree，把相连的岛连接起来，注意**让neighborParent成为目前这个position的新parent**，而不是让目前这个`position`的`parent`成为`neighbor`的`parent`，这样才能让新的`neighborParent`和之前的`position`的union联系起来，每联系一个岛，`islandCount--`
    * * 用 `int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}`来代表四个方向，four directions for iteration，为了把2D array变成1D position的操作
    * * 同样还是使用helper find function
* 463. Island Perimeter (easy)
    * method 1: DFS
        * boolean start: if grid[i][j] == 0, if start is true, this position is non-island, stop the dfs.
        * else if start is false, the dfs meets the boundary, result++, stop the dfs.
        * mark visited position as -1, stop the dfs when the position is visited.
    * method 2: count positions of island and positions that have neighbors
        * return island * 4 - neighbor * 2
        * 只判断右和下的position是否有neighbor
* 695. Max Area of Island (easy)
    * flood fill algorithm with DFS implementation
* 733. Flood Fill (easy)
    * flood fill algorithm with DFS implementation

下午去中东超市买了羊肉，晚上涮羊肉吃
晚上研究了一下微信跳一跳的外挂/AI算法，找到一个自己学习的，但是跑不了，一个算法不太好的，能跑100多分

问下楼主现在多少题了。。平时大概一题想多久做不出才看答案？

MacJordan 发表于 2018-1-2 02:34
问下楼主现在多少题了。。平时大概一题想多久做不出才看答案？

200题了，fb tag已经刷完，一般easy 5min, medium 10 min, hard 20min，完全没思路/不会的话直接看，而且会看好几个版本的答案，可以的话多用几种解法（比如可以用DFS，尝试用一下BFS），每个题分析思路，分析time and space complexity，尽量找到最优解（例如DP的space尽量做优化让空间复杂度少一个维度），现在没怎么刷题了，在做归类，比如number of island和相关的flood fill算法，string matching, subarray, subsequence, course scheduler，sentence similarity的union find，买卖股票之类的

吐槽一下，刚刚做bit manipulation里面的几个single number的题，发现bit manipulation挺难的，看大神写的分析都看的头疼