leetcode - HackMD

leetcode === - DNF list - 715, 685, 260, 808, 321, 803, 44, 555, 664, 407, 164, 324, 715, 730, 336, 363, 471, 932, 406(nlogn), 936 - Notations - DNF: did not finish by my own - buggy: multiple times of debugging - imple: implementation. trivial solution like scan or string manipulation - H:hard, M: medium, E: easy - g4g: geeksforgeeks, lt: lintcode - interview - 62, 843, 890(8), 489, 855, 853, 857, 750, 843 - 11/07~11/10 - 940. Distinct Subsequences II - DP - (lt)458E. Last Position of Target - {buggy} bin search - (lt)1541H. Put Box - DP - (lt)825H. Bus Station - BFS - (lt)1555H. Flower Problem - union find set - (lt)1538M. Card Game II - search - (lt)903M. Range Addition - {buggy}. imple - (lt)1539M. Flipped the Pixel - imple - (lt)1542M. NextTime Norepeat - imple - (lt)1543M. Unique Path IV - DP - (lt)1545M. Last Closest Time - imple - (lt)1554M. LastTime Norepeat - {buggy} corner-case. - (lt)1086E. Repeated String Match - imple - 11/06 - (lt)315H. Count of Smaller Numbers After Self - (10min). mergesort - (lt)1576H. Optimal Match - (60min). bipartite max perfect matching. hungarian algorithm with weights (dual value+tight edge+augmentation path+delta). O(MN^2) - (lt)1641M. Max Remove Order - (13min). Union-find set - (lt)1646M. CheckWords - (15min). BFS - (lt)1640H. Duplicates Digits - (15min). DP. add another dimension if have to handle different cases - 936H. Stamping The Sequence - greedy simulation - 11/04 - (lt)1640H. Duplicates Digits - (35min+). {DNF} DP. - use top-bottom search when get stuck. - (lt)109M. Triangle - (4min). DP - (lt)1642M. Query String - (10min). pure brutal force. meaningless problem. - (lt)1643M. Pick Fruits - (5min). sliding window - (lt)1634M. Secret Word - (8min). mapping count. - (lt)1644M. Plane Maximum Rectangle - (10min). hash. - (lt)1633E. Strings That Satisfies The Condition - (5min). imple - (lt)1645E. Least Subsequences - (6min). Bin-search - `bisect_left: arr[lo:i]<val arr[i:hi]>=val` - (lt)1580M. Transition String - (20min) {buggy}. hash. find loop - (g4g)E. Check if Tree is Isomorphic - (5min). recursive - 659M. Split Array into Consecutive Subsequences - (12min). queue+hash. dont overkill, just focus on the essential property. - {DNF}. O(1) space. - 11/03 - weekly contest - 936H. Stamping The Sequence - {DNF} - 935M. Knight Dialer - DP - 934M. Shortest Bridge - BFS - 933E. Number of Recent Calls - queue - 815M. Bus Routes - {buggy}. BFS. remember to remove duplicated edge - 750M. Number Of Corner Rectangles - DP or hash-table - 11/01~11/02 - 857H. Minimum Cost to Hire K Workers - sort, heap - 853M. Car Fleet - greedy, sort - 855M. Exam Room - heap (override comparator `__lt__`) - 489H. Robot Room Cleaner - recursive - 498M. Diagonal Traverse - shifting - 890M. Find and Replace Pattern - mapping equality - 843M. Guess the Word - {DNF} Good problem. creative question. - 62M. Unique Paths - simple DP - 685H. Redundant Connection II - two in degree - 684M. Redundant Connection - union find set - 399M. Evaluate Division - DFS - 760E. Find Anagram Mappings - hash - 326E. Power of Three - mod trick - 388M. Longest Absolute File Path - stack - 10/31 - 231E. Power of Two - imple. corner cases - 345E. Reverse Vowels of a String - imple - 421M. Maximum XOR of Two Numbers in an Array - Trie - 448M. Find All Numbers Disappeared in an Array - use negation as hash - 657E. Robot Return to Origin - imple - 316H. Remove Duplicate Letters - hashset + recursion - {DNF} stack - 280M. Wiggle Sort - imple - 228M. Summary Ranges - imple - 463E. Island Perimeter - imple - 832E. Flipping an Image - imple - 208M. Implement Trie (Prefix Tree) - Trie - 66E. Plus One - imple - 218H. The Skyline Problem - {buggy} overlapped boundary. merge - 162M. Find Peak Element - binary search - 739M Daily Temperatures - stack - 10/29+10/30 - 735M. Asteroid Collision - stack - google - 406M. Queue Reconstruction by Height - sort and insert: O(N^2) - {DNF} O(Nlogn): modified merge-sort - {DNF} segtree? - 140H. Word Break II - DP - 315H. Count of Smaller Numbers After Self - divide and conquer - bit - 240M. Search a 2D Matrix II - grid divide and conquer - 295H. Find Median from Data Stream - double heap - 312H. Burst Balloons - rangeDP - 387E. First Unique Character in a String - hash - 10/28 - google: - 341M. Flatten Nested List Iterator - recursion. prefetch. - 239H. Sliding Window Maximum - deque. only maintain necessary elements. - 535M. Encode and Decode TinyURL - relevant hash (compression) vs irrelevant hash (key gen). System Design - 155E. Min Stack - stack - 224H. Basic Calculator - {buggy} imple - 128H. Longest Consecutive Sequence - hashing - 50M. Pow(x, n) - imple - 173M. Binary Search Tree Iterator - generator - manual stack - 289M. Game of Life - mix information with different bits - 54M. Spiral Matrix - imple - oneline (recursive) - 22M. Generate Parentheses - dfs - 10/27 - Weekly contest - 932M. Beautiful Array - {DNF}. constructive answer - 931M. Minimum Falling Path Sum - DP. - 930M. Binary Subarrays With Sum - imple - three pointer solution with O(1) space - 929E. Unique Email Addresses - hash - 10/26 - google: - 297H. Serialize and Deserialize Binary Tree - encoding - 31M. Next Permutation - imple - 139M. Word Break - Trie. - dp with hash. - 253M. Meeting Rooms II - heap. - 17M. Letter Combinations of a Phone Number - dfs - 23H. Merge k Sorted Lists - heap - 10H. {buggy} Regular Expression Matching - mem+dfs - bugs: - p_pos < m when s_pos >= n - s_pos>=n, cannot read s[s_pos] - check equality when * - check s_pos < n when star == False - 56M. Merge Intervals - greedy - 42H. Trapping Rain Water - prefix-sum. S(N)=O(N) - two pointers - 20E. Valid Parentheses - stack - 200M. Number of Islands - flood fill. - -followup: partition, union-find set - 4H. Median of Two Sorted Arrays - binsearch - 146H. LRU Cache - dbl link list+hash - 253M. Meeting Rooms II - heap - 10/25 - new: - 4H. Median of Two Sorted Arrays - binsearch. estimate the final state and binary search the answer - review: - 863M. All Nodes Distance K in Binary Tree - recursion. make use of the return - 307M. Range Sum Query - Mutable - BIT. SegTree - 285M. Inorder Successor in BST - Morris. BST property - 205E. Isomorphic Strings - hash - 10/22~10/23 - 363H. Max Sum of Rectangle No Larger Than K - {DNF}. Binary search Tree - 471H. Encode String with Shortest Length - {DNF} recrusive. Cannot do that bottom to top. - 727H. Minimum Window Subsequence - DP. {buggy} `min` is slower than `else` - 702M. Search in a Sorted Array of Unknown Size - Bin search - 215M. Kth Largest Element in an Array - quick select - 10/20 - 928H. Minimize Malware Spread II - Dfs - 927H. Three Equal Parts - constructive - 926M. Flip String to Monotone Increasing - Prefix - 925E. Long Pressed Name - two pointers - 336H. Palindrome Pairs - Trie+Palidorme - 10/19 - 532E. K-diff Pairs in an Array - hash - 295H. Find Median from Data Stream - double heap - 480H. Sliding Window Median - a lazy remove heap design - 826M. Most Profit Assigning Work - binsearch. {buggy} notice lower cost might have higher reward - 901M. Online Stock Span - stack - 100E. 100. Same Tree - simple recursion - 451M. Sort Characters By Frequency - hash - 10/18 - 830E. Positions of Large Groups - simple imple - 472H. Concatenated Words - Trie. Passed with Python2 not PYthon3 (TLE). - 170E. Two Sum III - Data structure design - simple OOD - 730H. Count Different Palindromic Subsequences - {DNF}. range DP - 519M. Random Flip Matrix - hash, mapping design - {buggy}. interesting problem - 668H. Kth Smallest Number in Multiplication Table - heap. O(Q\*log(N)), since Q is large, it will cause TLE. - binsearch. O(log(Q)\*N). passed - 10/17 - 517. Super Washing Machines - {buggy}. debt counting - can be simpler - Google OA 2 - Google OA 1 - 630. Course Schedule III - heap+greedy - 10/14 - 316. Remove Duplicate Letters - {buggy} hash+greedy - 10/13 (pick one day) - weekly contest - 924 Minimize Malware Spread - Union find+counting - 923 3Sum With Multiplicity - Math+hash - Notice N<=3000 and 0<=a\[i\]<=100 - 922 Sort Array By Parity II - simple sort - two pointer - 921 Minimum Add to Make Parentheses Valid - stack - 246. Strobogrammatic Number - {buggy} two pointer - 244. Shortest Word Distance II - hash+two pointer - 742. Closest Leaf in a Binary Tree - onepass search - 222. Count Complete Tree Nodes - recursive - 393. UTF-8 Validation - simulation - 282. Expression Add Operators - {buggy} dfs - 849. Maximize Distance to Closest Person - prefix - 10/12 (pick one day) - 275. H-Index II - {buggy} binsearch - 117. Populating Next Right Pointers in Each Node II - bfs - 738. Monotone Increasing Digits - constructive - 875. Koko Eating Bananas - binary search - 424. Longest Repeating Character Replacement - sliding window. greedy - 544. Output Contest Matches - simple string manipulation - 645. Set Mismatch - neg/pos hash - 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. - 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 - 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. - 10/08 - (hackerrank) Consecutive Subsequences - DP. number theory. - Passed with C++ but TLE with Python3. - 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) - max-min 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/06 - leetcode weekly 105 - 920 Number of Music Playlists - {2 hour+} hard 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 - 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. - 10/04 - (lintcode) 1624. Max Distance - Trie. good problem. buggy, notice also need to recore 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 - 10/03 - 913. Cat and Mouse - {buggy} minmax search. - Range Sum Query 2D - Mutable - 2d segmental tree. - Zigzag Iterator - imple - Binary Search Tree Iterator - recursion to interation. Use stack to keep track every returns - Peeking Iterator - simple design - Moving Average from Data Stream - simple design - House Robber II - DP. handle the cycle restriction by search(0, n-1) and (1, n) - Minimum Path Sum - basic DP - Edit Distance - 2d DP. note the replacement operator - Maximum Vacation Days - 2d DP - 10/02 - 460. LFU Cache - DoubleLinkedList inside DoubleLinkedList. One pass! :) - Sentence Screen Fitting - Greedy+DP. - Word Break - {buggy}. notice the boundaries - Decode Ways - dp. - Evaluate Reverse Polish Notation - stack. notice the definition of div - Pacific Atlantic Water Flow - BFS - Next Greater Element I - stack - Merge Intervals - {buggy}. - 785. Is Graph Bipartite? - dfs - 261. Graph Valid Tree - union-find set - 10/01 - Diagonal Traverse - imple. generate digonal list first - Longest Palindromic Substring - manacher's alg. notice `'^#'+'#'.join(s)+'#$'` - Insert Interval - {buggy} imple - Range Module - {DNF}. Ultra-hard. - TLE with lazy-growing SegTree - Require BST to achieve O(logN) when querying - 09/30 - Sort Transformed Array - case by case search - Find K Pairs with Smallest Sums - priority queue - Find K-th Smallest Pair Distance - heap: O(NlogK) = O(2NlogN) TLE - sort and binary search the answer: O(nlogn) - Shortest Distance from All Buildings - BFS. reverse thinking - Minimum Window Substring - two pointers search - Android Unlock Patterns - dfs. notice the visited flag for the first element - Word Search II - notice words with only one char - Strobogrammatic Number II - dfs - Word Squares - dfs implementation - 09/29 - Closest Binary Search Tree Value - recursive - Validate Binary Search Tree - Simple recursive - Course Schedule - Simple topological sort - 685. Redundant Connection II - {DNF}. Hard. - indeg with union find set - Robot Room Cleaner - backtrack - dfs; keep track the direction, `move[(ind+k)%3]` - 09/28 - Inorder Successor in BST - {buggy}. Morris traversal. - right children can be a backref-link or a normal link - sol1. judge every where when stepping right - sol2. handle differently when creating a backref-link - 864. Shortest Path to Get All Keys - BFS. states encoding - 262. Trips and Users - sqls. notice to use `u.banned` and `u2.banned` to join `user` table twice on different conditions - 286. Walls and Gates - BFS - Evaluate Division - build graph. notice the value of the reverse edge, same (s, t) - Insert into a Cyclic Sorted List - link. notice the boundary and equality - Merge k Sorted Lists - classic heap. Python3 RTE, use `id()` as secondary key - Remove Duplicates from Sorted Array - two pointer - Move Zeroes - simple twopointer - First Unique Character in a String - hash - First Missing Positive - hash using pos/neg. have to realize that the ans is in 1~n+1 - 09/27 (google list on leetcode) - Shortest Palindrome - palindrome. manacher's alg - Max Consecutive Ones II (if we can flip at most one 0) - imple. - Max Consecutive Ones - simple imple - Intersection of Two Arrays - simple hash - Image Smoother - simple imple - Valid Parentheses - simple imple, stack - Valid Number - regexp - Valid Palindrome - simple imple - One Edit Distance - simple imple: item zip(x, y) in is tuple - Read N Characters Given Read4 II - Call multiple times - {buggy} pay attention to situation when the buffer remains - Read N Characters Given Read4 - buffer: [""] * N (assigned empty space) - Add Bold Tag in String - {buggy} KMP variation - Plus One - simple imple - Spiral Matrix - boundary imple - 270. Closest Binary Search Tree Value - simple imple - 09/26 - Longest Substring with At Most K Distinct Characters - hash - License Key Formatting - string, imple - Longest Univalue Path - recursive - Next Closest Time - imple - K Empty Slots - bucket - Repeated String Match - KMP mutation - Robot Room Cleaner - ideepcopy, imple - Number of Islands - pay attention - Convert Binary Search Tree to Sorted Doubly Linked List - when modifying morris traversal, check the type of right edge (normal/refer-back) - Construct Binary Tree from Preorder and Inorder Traversal - imple - Binary Tree Vertical Order Traversal - notice the tie-breaking condition - 09/25 - **Lintcode Google ladder START** - 507. Wiggle Sort II - {DNF} O(N) search for median - 825. Bus Station - bfs - 1544. Magic Square - pure heuristic imple. waste of time - 1555. Flower Problem - union-find set - 861. K Empty Slots - BST - {DNF} bucket by K - 374. Spiral Matrix - imple - 386. Longest Substring with At Most K Distinct Characters - two pointer scan - 434. Number of Islands II - Union-find set - 513. Perfect Squares - DP - 532. Reverse Pairs - mergesort. - 706. Binary Watch - imple - 724. Minmum Partition - knapsack - 480. Binary Tree Paths - dfs - 937. How Many Problem Can I Accept - math - 1580. Transition String - {buggy} topological sort. - notice the duplicated edge - 949. Fibonacci II - Fast power - 1577. Sum of leaf nodes - {buggy} morris traversal - 956. Data Segmentation - string imple - 1032. Letter Case Permutation - dfs - 1398. K Decimal Addition - imple. notice prefix 0 - **Lintcode Google ladder END** - 09/22 - 23. Merge k Sorted Lists - heap - 09/21 - 209. Minimum Size Subarray Sum - slide window - {buggy} 410. Split Array Largest Sum - O(n^2logn) DP - 566. Reshape the Matrix - generator, imple - 09/20 - ChapFB. Same Tree - recursive - ChapFB. Linked List Cycle - Fast slow pointer - ChapFB. Flatten Binary Tree to Linked List - Morris traversal - ChapFB. Intersection of Two Linked Lists - check the requirement (O(N) vs onepass) - ChapFB. Remove Nth Node From End of List - two pointer - ChapFB. Add Two Numbers - Everytime write a while, write the update operation first - ChapFB. Reverse Linked List - iteratively and recursively - ChapFB. Trapping Rain Water - {DNF}. two pointer. keep a property - ChapFB. Valid Parentheses - stack - ChapFB. Maximum Size Subarray Sum Equals k - hash - ChapFB. Minimum Size Subarray Sum - two pointer - ChapFB. Valid Number - regex - ChapFB. Valid Palindrome II - imple - ChapFB. Valid Palindrome - two pointer - ChapFB. - {buggy} 3Sum - use two pointer to eliminate the duplicates - 09/19 - ChapterFB - Move Zeroes - imple - Add Binary - imple - Intersection of Two Arrays II - hash - 568. Maximum Vacation Days - DP. TLE with python3 but pass with python2 - 179. Largest Number - `sorted(.., key=..)` `cmp` is not in python3 - `from functools import cmp_to_key` - 733. Flood Fill - check assumptions - 695. Max Area of Island - simple imple - 48. Rotate Image - odd even - 207. Course Schedule - topological sort - 82. Remove Duplicates from Sorted List II - read carefully - 09/18 - {buggy} 372. Super Pow - imple - 318. Maximum Product of Word Lengths - counter - 09/17 - 28. Implement strStr() - KMP - ``` python while cnd < len(p): nxt[cnd] = nxt[pos] if p[pos] == p[cnd] else pos while pos >= 0 and p[pos] != p[cnd]: pos = nxt[pos] pos += 1 cnd += 1 - rolling hash - 307. Range Sum Query - Mutable - segment tree - binary indexed tree - 303. Range Sum Query - Immutable - segment tree - 315. Count of Smaller Numbers After Self - Good one. - Mergesort - Segment Tree - sorted. Used the rank as index - `ans += query(0, rank[i]); insert(rank[i], 1) ` - 09/15 - week contest 121 - 905. Sort Array By Parity - simple imple - 904. Fruit Into Baskets - simple hash - 907. Sum of Subarray Minimums - tricky stack. - {buggy} 906. Super Palindromes - constructive. - find the upper bound to try. - 891. Sum of Subsequence Widths - order not matter - DP - preprocess power. - {buggy} 863. All Nodes Distance K in Binary Tree - tree imple. - 25. Reverse Nodes in k-Group - list imple - 835. Image Overlap - imple. need to optimize the condition - 09/14 - 146. LRU Cache - design. - 09/12 - {buggy} 32. Longest Valid Parentheses - greedy, stack - 543. Diameter of Binary Tree - recursive - 563. Binary Tree Tilt - recursive - 713. Subarray Product Less Than K - two pointer, math. - 209. Minimum Size Subarray Sum - two pointer - 452. Minimum Number of Arrows to Burst Balloons - greedy - 704. Binary Search - binary search - 337. House Robber III - tree. check typo - 328. Odd Even Linked List - linked list - 554. Brick Wall - hash - 287. Find the Duplicate Number - inplace hash. - 684. Redundant Connection - Disjoint-set (union-find set) - 477. Total Hamming Distance - bucket. - 869. Reordered Power of 2 - simple impl - 241. Different Ways to Add Parentheses - range DP. String - 178. Rank Scores - SQL. Note ambiguity - {buggy} 845. Longest Mountain in Array - simple imple. details. - 191. Number of 1 Bits - bit manipulation - 09/09 - 894. All Possible Full Binary Trees - recursive - 384. Shuffle an Array - simple impl - 382. Linked List Random Node - reservoir sample - 09/06 (pandas day) - 492. Construct the Rectangle - simple math - 733. Flood Fill - simple dfs - 387. First Unique Character in a String - simple hash - 447. Number of Boomerangs - simple map - 09/05 - 410. Split Array Largest Sum - DP. - O(N^2M). same code can pass with Python2 but not Python3 (WTH). - O(NMlogN)). {buggy} - 91. Decode Ways - DP. onepass. boundaries - 638. Shopping Offers - DP. Multi-dim knapsack - python is slow - 689. Maximum Sum of 3 Non-Overlapping Subarrays - 1D DP. one-pass - 837. New 21 Game - simple DP. optimize! using moving window and deque - 304. Range Sum Query 2D - Immutable - prefix sum. - 09/04 - {buggy} 464. Can I Win - min-max DP - {buggy} 322. Coin Change - step DP. - initial - 09/03 - 787. Cheapest Flights Within K Stops - SPFA - can pass with C++ but not Python (too slow) - 576. Out of Boundary Paths - simple graph DP. mem dfs - {buggy} 801. Minimum Swaps To Make Sequences Increasing - succeed on the 2nd try. - {buggy} 673. Number of Longest Increasing Subsequence - DP. - 95. Unique Binary Search Trees II - recursion. simulation. - use memorization to reduce the space usage. - 264. Ugly Number II - hash heap. - better way with math - 375. Guess Number Higher or Lower II - DP. good one but have less thumbs up than - 09/02 - 847. Shortest Path Visiting All Nodes - BFS+bit hashing. (path DP). - 312. Burst Balloons - Range DP - 357. Count Numbers with Unique Digits - Math - 454. 4Sum II - hash - 383. Ransom Note - imple - 773. Sliding Puzzle - dfs(with hash) (should use bfs). minimal path - 09/01 - {buggy} 221. Maximal Square - DP. - {DNF} 523. Continuous Subarray Sum - better property. boundary. - {DNF} 898. Bitwise ORs of Subarrays - BF. but with careful complexity analysis - 51. N-Queens - 52. N-Queens II - bit manipulation - 503. Next Greater Element II - padding - {buggy} 765. Couples Holding Hands - hash - {buggy} 216. Combination Sum III - boundary - 217. Contains Duplicate - meaningless - {buggy} 819. Most Common Word - details on assumption (input) - {buggy} 769. Max Chunks To Make Sorted - imple - 08/31 - {buggy} 538. Convert BST to Greater Tree - None - 206. Reverse Linked List - recursive way - 717. 1-bit and 2-bit Characters - imple - 122. Best Time to Buy and Sell Stock II - imple - (7) {DNF} 421. Maximum XOR of Two Numbers in an Array - Trie - 08/30 - 648. Replace Words - TrieTree - 895. Maximum Frequency Stack - imple - 858. Mirror Reflection - imple - 169. Majority Element - IQ - 13. Roman to Integer - imple - 676. Implement Magic Dictionary - imple - {buggy} 860. Lemonade Change - imple - 171. Excel Sheet Column Number - imple - {DNF} 128. Longest Consecutive Sequence - hash - 547. Friend Circles - DFS. - 781. Rabbits in Forest - hash - 565. Array Nesting - imple - 653. Two Sum IV - Input is a BST - generator with `yield from` - range search - 653. Two Sum IV - Input is a BST - detail - {buggy} 677. Map Sum Pairs - imple - {DNF} 371. Sum of Two Integers - bit - {DNF} 667. Beautiful Arrangement II - IQ - 08/29 - 696. Count Binary Substrings - imple. detail - 817. Linked List Components - simple imple - {DNF} 448. Find All Numbers Disappeared in an Array - IQ - 495. Teemo Attacking - simple imple - 389. Find the Difference - IQ - 690. Employee Importance - simple hash - 520. Detect Capital - simple. imple - 462. Minimum Moves to Equal Array Elements II - IQ - {buggy} 283. Move Zeroes - two pointer - 789. Escape The Ghosts - simple imple - 748. Shortest Completing Word - hash. imple - 451. Sort Characters By Frequency - simple imple - 508. Most Frequent Subtree Sum - search - {DNF} 260. Single Number III - IQ - {30+}{buggy} 889. Construct Binary Tree from Preorder and Postorder Traversal - Details - {10+}{buggy} 856. Score of Parentheses - Details - {5} 429. N-ary Tree Level Order Traversal - BFS - 485. Max Consecutive Ones - simple imple - 812. Largest Triangle Area - brutal force. - 784. Letter Case Permutation - DFS - 526. Beautiful Arrangement - DFS - 695. Max Area of Island - 200. Number of Islands - dfs. flood fill - 08/28 - 647. {15} Palindromic Substrings - DP - [Manacher’s Algorithm](https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/) ``` if i < right: # in affected area f[i] = min(f[2*center-i], right-i) else: f[i] = 1 # out of range while s[i+f[i]] == s[i-f[i]]: # append different front and end to prevent overflow f[i] += 1 if i+f[i] > right: # update the boundary right = i+f[i] center = i ``` - 446. {1/2DNF} Arithmetic Slices II - Subsequence - hash+DP. - 413. {5} Arithmetic Slices - imple - 739. {5} Daily Temperatures - stack. - rabin-karp - 08/27 - 632. {DNF} Smallest Range - heap. hard - 438. Find All Anagrams in a String - hashing. - 1. Two Sum - hash. - 202. Happy Number - hash. - 242. Valid Anagram - hash - 347. Top K Frequent Elements - hash heap - 349. Intersection of Two Arrays - set, intersection - 350. Intersection of Two Arrays II - hash - 08/26 - 888. Fair Candy Swap - math. - 693. Binary Number with Alternating Bits - details. - 540. {20} Single Element in a Sorted Array - binary search. detail - 762. Prime Number of Set Bits in Binary Representation - bincount - 515. Find Largest Value in Each Tree Row - bfs - 521. Longest Uncommon Subsequence I - imple - 292. Nim Game - logic - 877. Stone Game - tricky logic - 553. Optimal Division - details - 824. Goat Latin - imple - 08/25 - 463. Island Perimeter - detail. transfer summation to subtraction. - 669. Trim a Binary Search Tree - use the returned result to update current node - 412. Fizz Buzzj - imple. - 442. Find All Duplicates in an Array - use the condition provided by the problem. - 566. Reshape the Matrix - imple. - 700. Search in a Binary Search Tree - imple. - 841. Keys and Rooms - Graph dfs. - 496. {DNF} Next Greater Element I - stack and hash - 406. {DNF} Queue Reconstruction by Height - insertion - 513. Find Bottom Left Tree Value - tree bfs. Alg doc (before Aug) === - 1->10 (simplest -> hardest) - Others - Greedy - (3) {10} 861. Score After Flipping Matrix - Greedy - (3) {10} 763. Partition Labels - Note the details. - Implementation - 728. Self Dividing Numbers - one-line python - Data Structure - Tree - 669. Trim a Binary Search Tree - use the returned value to update current node - 872. Leaf-Similar Trees - Note reference equal vs value equal - 814. Binary Tree Pruning - careful about the boundary - (4) 654. Maximum Binary Tree - tricky. Note: change of node doesn't change references that point to it. - simple ones: - 104, 110, 109, 257, 783, 530 - 404. Sum of Left Leaves - use default arguments to separate root from non-root - 226. Invert Binary Tree - Note: the link list will change after changing - 100. Same Tree - base case None - 111. Minimum Depth of Binary Tree - base return inf to avoid min - 124. Binary Tree Maximum Path Sum - return max sum from current note to leaf. - 101. Symmetric Tree - Note: __eq__ of treenode is undefined - 236. Lowest Common Ancestor of a Binary Tree - Clarify the type of input. - Linklist - 83/82/19. Remove Duplicates from Sorted List - Linklist - 707. Design Linked List - Linklist Implementation - 876. Middle of the Linked List - Classic two pointer. - 203. Remove Linked List Elements - Note: Duplicate consecutive value. - Queue - 641. Design Circular Deque - double linked list - 622. Design Circular Queue - fixed length data-structure: use fixed length list with looping indices - Stack - 150. Evaluate Reverse Polish Notation - stack. note: division trap - 155. Min Stack - stack. maintain another stack - 225. Implement Stack using Queues - looped queue. - 232. Implement Queue using Stacks - double stacks. - Leetcode (DP special from July/31) (38) - (2) {10} 467. Unique Substrings in Wraparound String - Simple DP. - (3) {15} 790. Domino and Tromino Tiling - step DP. - (4) {20} 698. Partition to K Equal Sum Subsets - mem search. Bit-status - (4) {DNF} 808. Soup Servings - mem search. Note: estimate the **actual** boundary (p approximates 1.00) - (4) {10} 368. Largest Divisible Subset - simple DP with sol output. - - (3) {14} 376. Wiggle - Greedy. Careful about the beginning. - (5) {20} 213. House Robber II - Step DP. Two cases. - (3) {10} 279. Perfect Squares - Knapsack DP. - (3) {10} 416. Partition Equal Subset Sum - knapsack DP. - (3) {10} 474. Ones and Zeroes - 2d knapsack DP. - (2) {4} 300. Longest Increasing Subsequence - LIS. classic DP - (2) {10} 838. Push Dominoes - Simple sim. - (3) {15} 764. Largest Plus Sign - Grid DP. Prefix sum. - (3) 688. Knight Probability in Chessboard - pure simulation. - (5) {20+} 873. Length of Longest Fibonacci Subsequence - DP + binary search. Good one. - (3) {20} 813. Largest Sum of Averages - Range DP. Note: safe solution first. Don't have to be the optimal at first. - (3) {10} 718. Maximum Length of Repeated Subarray - LCS variation. - (2) {10} 64. Minimum Path Sum - Simple Grid DP. - (4) {15} 309. Best Time to Buy and Sell Stock with Cooldown - Stock DP. Note: be clear about your definition of f[i] - (3) {5} 96. Unique Binary Search Trees - Pattern finding. - (3) {6} 377. Combination Sum IV - search with memorization. - (3) {13} 516. Longest Palindromic Subsequence - range DP. Note: special case handling. - (3) {5} 740. Delete and Earn - 1D DP. - (4) {15} 494. Target Sum - memorization search. Note: if answer is 0, check initialization or boundary (base case). - (4) {10} 392. Is Subsequence - LCS problem. dimension compression (reference in C++). - (6) {20} 486. Predict the Winner - minmax DP. - (2) {7} 650. 2 Keys Keyboard - Split DP. - (3) {10} 343. Integer Break - Split DP. Careful about what `f[n]` means (usually comes with assumption(the splitted score)) - (5) {30} 714. Best Time to Buy and Sell Stock with Transaction Fee - Ascending property. O(N^2) to O(N). Careful about the boundary. - (4) {10} 646. Maximum Length of Pair Chain - LIS problem. TLE with Python but not C++. - (5) {30+} 712. Minimum ASCII Delete Sum for Two Strings - grid DP. Boundary should consider the - (2) 746. Min Cost Climbing Stairs - simple stair DP. - (2) 198. House Robber - simple DP. - (1) 121. Best Time to Buy and Sell Stock - stock DP. - (1) 70. Climbing Stairs - step DP. - (1) 53. Maximum Subarray - ascending prop - (2) 303. Range Sum Query-Immutable - Prefix sum. - (2) 383. Counting Bits - pattern finding. - (1) 413. Arithmetic slice - ascending DP. - (3) 647. Palindromic Substrings - range DP. - (1) 62. Unique Paths - simple #solution counting. - History - Leetcode - (3) 152. Constructive. Swap min, max strategy. - (3) 238. Constructive. Bidirectional prefix. - (3) 42. DP. Bidirectional scan. - cf_edu_r44(985) - (1). A, B - (2). C. Greedy, constructive. - (3). D. Binary search - (5). E. Interval DP. Interval set - (6). F. Vector Hash, use power to replace shift (O(N) to O(1)) - cf_483_div2 - (1). A, B. Simple simulation - (4). C. Number theory. - (4). D. Interval DP. - cf_482_div2 - (1). B. Logit. - (3). Easy graph theory. - (5). Binary Tire. Finding the maximum XOR of $x_i$ with v. Divisor group. - cf_480_div2 - (2) B. Simulation. Logit. Symmetric construction. - (3) C. Greedy. Notice the greedy design (do not exaggerate the assumption). - (5) D. Simplify the numbers first to avoid redundant computation. - LeetCode - (2) [820. Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/description/) - simple string processing. - (2) [821. Shortest Distance to a Character](https://leetcode.com/problems/shortest-distance-to-a-character/description/) - simple. two ways scan. - (3) [822. Card Flipping Game](https://leetcode.com/problems/card-flipping-game/description/) - logic+hash - (5) [823.Binary Trees With Factors](https://leetcode.com/problems/binary-trees-with-factors/description/) - Simple DP. Use `unordered_map` (hash) to make the query to `O(1)`. - (2) [114. Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list) - Recursive. Pay attention to the fakeroot and self loop. - (2) [120. Triangle](https://leetcode.com/problems/triangle) - DP. Reusing the space. - (2) [129. Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers) - Simulation. Pay attention to the boundary. - (5) [131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning) - DP+DFS. Can summarize the answer online without DFS (offline) by accumulate the answer list. - (4) [132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii) - DP. - (6) [134. Gas Station](https://leetcode.com/problems/gas-station) - Increasing seq. Details on the boundary. - (4) [135. Candy](https://leetcode.com/problems/candy) - Logic. Simplify the restriction to larger than left and right and maintain it by two scanning. - [One pass method.](https://leetcode.com/problems/candy/discuss/42770/One-pass-constant-space-Java-solution) Consider the property of being descending. - (7) [137. Single Number II](https://leetcode.com/problems/single-number-ii) - Logic. On/off status of each bit. - Create a group (mathematical) "0->1->2->3/0" to simplify the code. [link](https://piazza.com/class/jbzpcp2r9tg7b3?cid=183). Xor is actual a group operation in binary case. - (5) [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer) - List Logic. Use association to reduce the memory usage. - pile up the original one with the new one. - (3) [139. Word Break](https://leetcode.com/problems/word-break) - Simple DP. - (4) [140. Word Break II](https://leetcode.com/problems/word-break-ii) - Simple DP. Python's speed issue. - (5) [115. Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences) - DP. O(N^3). Should be O(N^2). - (3) [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle) - Link-list Logic. - (6) [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii) - Link-list logic. Hard. - (4)[143. Reorder List](https://leetcode.com/problems/reorder-list) - Link-list impl. - (6) [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal) - [Morris traversal](https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html). Threaded binary tree. Use right child to refer back and use the "refer back " property to judge whether we traversed this node. - use the empty right children (refer parent) and change it back later (judge whether there is a loop) - (1) [147. Insertion Sort List](https://leetcode.com/problems/insertion-sort-list) - (2) [148. Sort List](https://leetcode.com/problems/sort-list)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.