转型刷Leetcode记录帖

今天刷了传说中的google OA题
Max Distance和Words compression都是考了 简单的数据结构+复杂的运用

KMP：
随着刷hard的频率增加，慢慢觉得KMP还是一个值得掌握的算法，我自己个人有一个特别简短（nxt3行，match3行）的Python模板，需要的可以私信我
网上的KMP模板分两类，一类的next数组记录的下一个需要检查的位置，一类记录的是最长匹配前缀。前者的递归通常是pos = next[pos]，后者的递归通常是pos = next[pos-1]。各位初学者需要注意一下
比如aaab的pattern，第一类的next是[-1, -1, -1, 0] 或者[0, 0, 0, 1]。而第二类的next可能是[0, 1, 1, 0]（不确定，因为我是写第一种的）。
我是写第一种的，参考维基百科的定义（加代码简化）可以写出很简短精巧的代码。自己总结的模板才是能理解和记得的
KMP想练一下可以用LC 28Implement strStr()，变种还有LC的Add Bold Tag in String、Repeated String Match。

PS：
差一道(lintcode) 1628. Driving problem实在有点恶心没做下去，明天把它做了。

- 10/04
    - (lintcode) 1624. Max Distance
        - Trie. good problem. buggy, notice also need to record the min
    - (lintcode) 1625. Words Compression
        - KMP. good problem. 1Pass!
    - (lintcode) 1627. Word Segmentation
        - imple
    - (lintcode) 1629. Find the nearest store
        - same as 1623. sort+binsearch
    - (lintcode) 1630. Interesting String
        - dfs+mem
    - (lintcode) 1631. Interesting Subarray
        - simple twopointers
    - (lintcode) 1626. Salary Adjustment
        - binsearch
    - (lintcode) 1621. Cut Connection
        - simple imple
    - (lintcode) 1623. Minimal Distance In The Array
        - sort binary search
    - (lintcode) 1632. Count email groups
        - trie

楼主好厉害，一天能刷这么多，加油

今天心累。只刷了三道有难度的题，其他都是水题
(lintcode) Driving problem 感觉设计的不错：假设道路长L宽W，有一些半径为1的圆柱体障碍物(N=1000)，问半径为2的圆能否从左边走到右边，不能与上下边界或者障碍物相切或相交。
(hackerrank) Lexicographic paths 把N个“H”，M个“V”，拼接成一个字符串。在所有可能的字符串中，求字典序第K小的字符串是什么。
(leetcode) Single Number II 数组里只有一个正整数只出现了一次，其他正整数都出现了三次。求那一个只出现一次的数字

- 10/05
    - Single Number II
        - requires 2 extra bits to maintain the information of 1 bit
        - (1, 0) -> (0, 1) -> (0, 0) group theory. induce the operation
    - simple problems
        - Two Sum
            - hash
        - Move Zeroes
            - two pointers
        - Plus One
            - imple
        - Intersection of Two Arrays II
            - imple
        - Best Time to Buy and Sell Stock II
            - construct. property of increasing
        - Rotate Array
            - rotate by reversing
        - Contains Dulicate
            - hashing
        - Single Number
            - xor
            - extensions: single Number II
    - (lintcode) 1628. Driving problem
        - graph+geometry+union-find set. good problem.
    - (hackerrank) Lexicographic paths
        - pattern find.

本来想着放个周末假，刷俩练习赛就好了，结果发现压轴还蛮难的。。

codeforce 1059
- 1059C 给一个数组，元素从1到n。每回合先记录下所有数字的GCD（最大公约数），然后从数组中删去一个数字。n回合后数组为空，期间记录下的GCD会组成一个序列。因为删除顺序不同，期间组成的序列可能不同。问在所有可能的序列中，字典序最大的是什么。
CF的难度还是太ACM了，一般div2做到第4或者第5题就差不多了，可以跳几何和数论的题目。

leetcode weekly 105
第三题太饿卡太久了，导致第四题dp没想完，最后也没挤进前200。。
918 当时用了O(N)的space写，其实没必要，思考下互补的问题就可以O(1)空间做出
919 其实是裸实现题，但是写起来有很多细节坑。错了不应该
920 其实不是太难的DP。但是一开始自己没把题看清，看清题后硬在原来的递推方程中改，这样一般都会有bug。应该吸取教训，下次看到新的条件后直接重新思考递推。

意外收获：
1、codeforces用pypy提交能大幅提升python的运行速度，尤其是循环嵌套的时候。
2、function.lru_cache是一个挺有用的decorator，能够自动实现带记忆的调用。比如写DP的时候可以直接套上这个decorator，不用自己做hash，难点就是比较难估计cache的大小。


- 10/06
    - leetcode weekly 105
    - 920 Number of Music Playlists
        - {2hour+} DP
    - 919 Complete Binary Tree Inserter
        - imple recursion
    - 918 Maximum Sum Circular Subarray
        - prefix sum
        - or find the complementary problem
    - 917 Reverse Only Letters
        - simple imple
    - [(1059) Codeforces Round #514 (Div. 2)](http://codeforces.com/contest/1059)
    - 1059A. Cashier
        - simple imple
    - 1059B. Forgery
        - matching problem
        - pypy speed up (but more memory)
    - 1059C. Sequence Transformation
        - constructive
    - 1059D. Nature Reserve
        - {DNF} binsearch

早上刷了Lyft在Codeforces的比赛，前四题div2难度的虽然卡了一会，但是还是能做出来的
题目D很巧妙，数论、计数（哈希）都考察到了，然后还需要构造比较巧妙的解，值得一做：

CF1033D： 给出n个正整数，每个数字都有3到5个约数。问所有数的乘积总共有多少个约数。n小于等于500，每个正整数小于2*10^18（也就是说暴力拆解质因子会超时）。

C题和LC486、LC913都是max-min search，由于我自己复杂度估算错误了，导致迟迟不敢写搜索。C题复杂度是N+N/2+N/3+...+N/N，我以为调和级数是发散的，但其实这个序列和是O(NlogN)的。

- 10/07
    - [Lyft Level 5 Challenge 2018 - Elimination Round](http://codeforces.com/contest/1033)
    - [1033D Divisors](http://codeforces.com/contest/1033/problem/D)
        - {buggy} number theory, hash
    - [1033C Permutation Game](http://codeforces.com/contest/1033/problem/C)
        - minmax search, brutal force!
    - [1033B Square Difference](http://codeforces.com/contest/1033/problem/B)
        - simple math
    - [1033A](http://codeforces.com/contest/1033/problem/A) King Escape
        - simple logic

- 10/09
    - 264. Ugly Number II
        - heap+hash
        - 3pointers (2ptr, 3ptr, 5ptr)
            - idea: regrouping
            - (x\*2,x\*3,x\*5),(y\*2,y\*3,y\*5)... -> (x\*2, y\*2,...), (x\*3, y\*3,...), (x\*5, y\*5,...)
    - 845. Longest Mountain in Array
        - Automata
    - 787. Cheapest Flights Within K Stops
        - DP
    - 782. Transform to Chessboard
        - constructive. good one.
    - 210. Course Schedule II
        - topological sort
    - 332. Reconstruct Itinerary
        - backtrack. {buggy} duplicated edges.

今天清理了一波DNF的题（Did not finish，相信有玩魔方的应该知道这个）
这些题是第一次刷看了discussion才做出最优解的题目，大部分都是脑洞构造答案的题目，基本上很难泛化到其他情况。

此外花30分钟刷了visa的OA....基本上就easy或者medium偏easy难度。

- 10/10 (DNF review day)
    - 406. Queue Reconstruction by Height
        - constructive. O(N^2)
        - has a shorter version with `insert`.
    - 496. Next Greater Element I
        - stack
    - 632. Smallest Range
        - heap.
    - 446. Arithmetic Slices II - Subsequence
        - DP with hash
    - 260. Single Number III
        - Get x1 ^ x2. Split into two conditions.
    - 448. Find All Numbers Disappeared in an Array
        - use negative/positive as hashing.
    - 667. Beautiful Arrangement II
        - constructive
    - 371. Sum of Two Integers
        - it can be solve with recursive code.
        - Use C++. Since python don't have complementary
    - 128. Longest Consecutive Sequence
        - hash.
    - 421. Maximum XOR of Two Numbers in an Array
        - Trie. Notice time complexity is O(N\*#bits) = O(N\*32) = O(N)
    - 898. Bitwise ORs of Subarrays
        - brutal force. But the time complexity is tricky.
    - 523. Continuous Subarray Sum
        - hash. Notice the range of K
        - O(N) with prefix_sum_hash. prefix_sum-prefix_sum = any range
    - 42. Trapping Rain Water
        - greedy+two pointer
    - 683. K Empty Slots
        - segtree. O(nlogn)
        - bucket. O(n)
    - 109. Convert Sorted List to Binary Search Tree
        - two pointers + recursive
    - 324. Wiggle Sort II
        - O(N) to locate Kth smallest number

楼主加油...

刷了两道hard，深深感受到语言的恶意
要不就是Python3不能过，相同代码python2就过了。
要不就是Python2也不能过，换C++就过了。。。
虽然最最优化的情况下所有语言都能过，但是卡常数的时候python就很吃亏...


- 10/11
    - 803. Bricks Falling When Hit
        - brutal force. TLE with Python3, python2. pass with C++
        - {DNF} reverse time+union-find
    - 321. Create Maximum Number
        - {DNF} Greedy+DP. dont be afraid of the complexity
        - Passed with Python2 but not Python3.

ppsf 发表于 2018-10-12 05:14
楼主加油...

共勉共勉