刷题打卡

刷题打卡，每天5道+1bq，坚持一个月。

现在LZ一周兼职三天，剩下两天三门课，希望自己坚持下去，以后也觉得自己是个曾经拼搏过的人。


分享的题目格式是：【Leetcode题号】【pass/fail】【做题耗时】【打败了百分之多少的人】

25天 Goolge onsite 倒计时

12.13 打卡

• 【Longest Common Prefix】find longest common prefix among all input words, sort 或者 trie, O(NklogN) 或者 O(Nk)
• 【Whether a Binary Tree Contains All Chars of a Input String】inorder traversal, 每个节点一个char一个char地check, 17 min
• 【Decoder Iterator】input sequence like [2,4,0,3], it means 2 times of integer 4 and 0 times of integer 3, implement an iterator, 15 min, 多线程则读(hasNext)写(next)锁，两个lock+readCnt
• 【Shortest Path】given an infinite large chess board, start from (0,0) to a destination, some points cannot be visited, 每次跳一个“日”字, shortest path? 双端bfs, 10 min
• 【LC 375 Guess Lower or Higher II】O(N^3) DP, 实际上increasing dq可以达到O(N^2)，下次再写一下这个算法，16 min
• 【Longest String Sequence】given a list of strings, 构成串的条件是当前string比parent多一个字符，并且除去最后这一个字符与parent相同, buildGraph (sort by length, Map: string -> Node) + dfs recursive，O(NlogN), 18 min
• 【LC 3 Longest Substring without Repeating Chars】2 pointers + map, 13 min
• 【Max Value of a Complete Tree】LC原题, O(h^2), 8 min
• 【Minimum Cost for IDs】given a list of pairs, each pair has an id and its cost, find K pairs with minimum cost, also one ID cannot be chosen for more than M times, sort + map, 5 min
• 【LC 777 Transfer one String to the Other】RXX -> XRX, O(N) 12 min
  

behavior question

11.30 打卡

• 【10 Regular Expression Matching】15 min, 95%, DP
• 【140 Word Break II】10 min, 64%, DP
• 【97 Interleaving String】20 min, 56%, 1d DP
• 【85 Maximal Rectangle】30 min, 43%, stack O(N^2) time + O(N) space，用的是histgram求最大矩形面积的方法，用DP可能更快，不过好晕...
• 【818 Race Car】FAIL, Dijkstra 或者 DP，O(NlogN)
  

Dijkstra还是太不熟练了。

12.01 打卡

• 【LC 354 Russian Doll Envelopes】15 min, 60% sort+LIS
• 【LC 300 Longest Increasing Subsequence】5 min, 95%, binary search + DP
• 【LC 115 Distinct Subsequences】18 min, 51%, 1d DP
• 【LC 727 Minimum Window Subsequence】FAIL, 2d DP （初始条件注意一下）
• 【LC 42 Trapping Rain Water】4 min, 98%
  

希望能够坚持下去

12.2 打卡

• 【LC 403 Frog Jump】52%, DP Map<Int, Set>, O(N^2)
• 【LC 363 Max Sum of Rectangle No Larger Than K】10%, binary search, O(N^3 logN)，这个跑的太慢了.....和1D的subarray no larger than K是一样的
• 【LC 72 Edit Distance】76%, DP
• 【LC 128 Longest Consecutive Sequence】80%, DP, O(N)，这道题map的解法太精妙了！
• 【LC 679 24 Game】99%, Backtracking
  

努力努力！

12.3 打卡

• 【Implement HashMap】rehash + iterator + generic，照着源码撸了一遍
• 【LC 157 Read N Characters Given Read4】10 min, 100%
• 【LC 188 Best Time to Buy and Sell Stock IV】FAIL, 66%, O(kn) time + O(k) space
  

12.4 打卡

• 【LC 689 Maximum Sum of 3 Non-Overlapping Subarrays】20 min, 2d DP, 65%, O(3N)
• 【LC 410 Split Array Largest Sum】DP, 用binarySearch太漂亮了, 100%
• 【LC 265 Paint House II】DP, 69%
• 【LC 628 Maximum Product of Three Numbers】PriorityQueue, O(NlogK)，分别选出最大/最小K个数字
• 【LC 284 Peeking Iterator】89%
  

坚持坚持

12.6 打卡

• 【LC 312 Burst Balloons】FAIL, 2d DP
• 【LC 91 Decode Ways】10 min, 96%, DP
• 【LC 124 Binary Tree Maximum Path Sum】10 min, 99%
• 【LC 493 Reverse Pairs】20 min, 1%, 不要用binary search, 不管是链表还是数组，插入的复杂度都是O(N)，所以这样和暴搜没有区别
• 【LC 315 Count of Smaller Numbers After Self】1h, 11%, AVL, 这种题用merge sort是最方便快捷的，不能用binary search，不管是用数组还是链表，插入的操作都是O(N)线性复杂度，并没有优化算法，AVL只需要插入，记住leftRotate, rightRotate和插入时的4种操作（left-left, left-right, right-left, right-right）就好，至于AVL的binary search，可以记录以每个节点为根节点的子树大小，以及每个节点要记录duplicates的个数
  

12.7 打卡

• 【LC 322 Coin Change】41%, 1d DP, O(amount * N)
• 【LC 518 Coin Change 2】50%, 2d DP, O(amount * N)
• 【LC 315 Count of Smaller Numbers After Self】36%, 复习昨天FAIL的题，AVL, O(NlogN)
• 【LC 632 Smallest Range】29%, PriorityQueue, O(NKlogK)
• 【LC 737 Sentence Similarity II】98%, DFS / Union Find, O(N)
  

另外需要再复习一下树的前中后序遍历。

bq是什么意思？