在职跳槽 刷题 记录帖

线段树

• Range Sum Query - Mutable    ,   done
• Range Sum Query 2D - Mutable
• Reverse Pairs
• Falling Squares
  

扫线算法（加深学习）
https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/
https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/

• Merge Intervals
• Insert Interval
• Number of Airplane in the sky
• Minimum Number of Arrows to Burst Balloons
• The Skyline problem
• Meeting Rooms II
• Rectangle Area II
• Non-overlapping Intervals
• Summary Ranges
• Employee Free Time
  

11/22  动态规划 (配合jz和xc)

• Unique Paths     ,    done
• Unique Paths II     ,    done
• Minimum Path Sum     ,    done
• 
  

11/23  动态规划

• Edit Distance      ,     done
• Palindrome Partitioning II        ,     done
• Arithmetic Slices      ,     done
• Regular Expression Matching        ,     done
• Wildcard Matching        ,      done
  

• 
  
• Word Break II        ,      done
• Dungeon Game        ,      done
• Cherry Pickup       ,      done
  

11/24  动态规划

• House Robber      ,     done
• Frog Jump      ,     done
• Burst Balloons      ,     done
• 4 Keys Keyboard      ,     done
• 2 Keys Keyboard      ,     done
• Paint Fence      ,     done
• Paint House II      ,     done
• Sentence Screen Fitting  ,  极难！
• Integer Break      ,      done
• Student Attendance Record II      ,     极难
• Best Time to Buy and Sell Stock III      ,     done  压缩空间
  

• Best Time to Buy and Sell Stock IV     ,     done   普遍case
• Best Time to Buy and Sell Stock with Transaction Fee      ,     done  压缩空间
• Best Time to Buy and Sell Stock with Cooldown      ,     done  压缩空间
• Unique Binary Search Trees      ,     done
• Counting Bits       ,      done
• Partition to K Equal Sum Subsets      ,      done
• Cheapest Flights Within K Stops        ,      done
• Maximum Vacation Days        ,      done
  

11/25 Heap

• Minimum Number of Refueling Stops        ,      done    有些贪心算法
• Shortest Path to Get All Keys        ,       BFS
• IPO        ,       done    有些贪心算法
  

11/26 计数型DP

• Number of Music Playlists
• Knight Dialer
• Knight Probability in Chessboard
• Student Attendance Record II
  
  

11/26  动态规划

• 大回顾 (包括两个月前做过的DP)
• jz背包问题
  

11/27 记忆化搜索 TODO

• Super Egg Drop
• Shopping Offers
• Longest Increasing Path in a Matrix
• Freedom Trail
• Triangle
• Coin Path        ,      done
  

11/27 背包  计数型

• Profitable Schemes
  

11/28 复习  Union Find


11/29 复习  Union Find



11/30

• 复习  Graph
• Range Module
  

12/01

• 复习  Graph, 普林斯顿算法课
• 
  

复习 11/14到11/20之间的题目

12/02 ~ 12/05  Array

• Find the Celebrity        ,       done
• Peak Index in a Mountain Array       ,      done
• Valid Mountain Array       ,      done
• Array Nesting        ,       done
• Max Area of Island        ,       done
• Max Chunks To Make Sorted        ,       done
• Image Overlap        ,       done
• Flipping an Image        ,       done
• Rotate Image        ,        done
• Median of Two Sorted Arrays        ,        done
• Jump Game II           ,         done
• Flip String to Monotone Increasing          ,          done
• Longest Line of Consecutive One in Matrix          ,          done
• Find All Duplicates in an Array          ,          done
• Single Element in a Sorted Array    二分！困难！
• Maximize Distance to Closest Person    ,     注意左右边界是0的corner cases.
• Find Pivot Index          ,          done
• Plus One          ,         done
• Perfect Rectangle          ,         done
• Add Binary          ,         done
• Beautiful Arrangement II          ,         done
• Minimum Increment to Make Array Unique      困难，用bucket
• Global and Local Inversions         ,          done
• Rotate Array          ,          done
• Flatten 2D Vector          ,          done
• First Missing Positive      特性解法
• Wiggle Sort    注意对算法正确性的证明
  

12/06  HashTable类

• Logger Rate Limiter        ,        done
• Line Reflection        ,        done
• Palindrome Permutation        ,        done
• Strobogrammatic Number II        ,        done
  

12/07  Array

• Transform to Chessboard          ,         done
• Exam Room          ,         done
• Next Permutation        ,       done
• Permutation Sequence         ,         done
• Spiral Matrix          ,         done
• Wiggle Sort         ,         done
• Split Array With Same Average    转化成回溯问题！
• RLE Iterator          ,         done
• Valid Triangle Number          ,         done
• Zigzag Iterator          ,          done
• Jump Game          ,          done
• Split Array with Equal Sum         ,         done
• Maximum Swap          ,          done
• Maximum Distance in Arrays          ,         done
• Candy          ,         done
• Longest Consecutive Sequence          ,         done
  

12/08  Review

• KMP算法
• 复习  HashTable + String
  

• Contains Duplicate III    ,    bucket思想！
  

12/09  Review

• 博弈论 + 策略游戏
• 普林斯顿 -- 图论   最短路 最大流  二分图匹配
  

12/10  Review

• 复习  HashTable + Array
• 复习  这近10天做过的Array题目
• Brick Wall
• Sentence Similarity
• Implement Magic Dictionary
• Data Stream as Disjoint Intervals
• Merge k Sorted Arrays
• Kth Largest Element in an Array
• 
  

Graph Shortest Path问题

Maximum Vacation Days
Cheapest Flights Within K Stops

12/10  BST思想  复习

• Data Stream as Disjoint Intervals
• Count of Smaller Numbers After Self
• Reverse Pairs
• Count of Range Sum
  

12/11  随机复习这两个多月做过的题




12/12 ~ 12/13  回溯

• Word Squares            ,             done
• Letter Combinations of a Phone Number             ,             done
• Factor Combinations            ,             done
• Permutations             ,             done
• Combinations            ,             done
• Combination Sum            ,             done
• Subsets             ,             done
• Count Numbers with Unique Digits
• Split Array into Fibonacci Sequence      ,      注意recursion终止条件和overflow
• Sudoku Solver            ,             done
• N-Queens            ,             done
• Gray Code            ,             done
• Restore IP Addresses            ,             done
  

12/14 ~ 12/15  DFS (not including Tree)

• Number of Islands             ,            done
• Number of Distinct Islands             ,            done
• Number of Islands II             ,            done
• Ternary Expression Parser             ,            Stack解
• Shortest Bridge            ,            done
• Making A Large Island       好题
• Possible Bipartition            ,            done
• Employee Importance            ,            done
• Flatten a Multilevel Doubly Linked List            ,            done
• Nested List Weight Sum II            ,            done
• House Robber III            ,            done
  

• Freedom Trail
• Minimize Malware Spread
  

• Remove Duplicate Letters            ,            困难！！
• Length of Longest Fibonacci Subsequence
  

12/16   Tree (not BST)

• Binary Tree Paths           ,           done
• Find Mode in Binary Search Tree           ,           done
• Balanced Binary Tree           ,           done
• Print Binary Tree           ,           done
• Lowest Common Ancestor of a Binary Tree  (LCA)           ,           done
• Lowest Common Ancestor of a Binary Search Tree           ,           done
• Flip Equivalent Binary Trees           ,           done
• 
  
• Count Complete Tree Nodes           ,            困难！
• Complete Binary Tree Inserter           ,           done
• All Possible Full Binary Trees           ,           done
• Maximum Width of Binary Tree           ,           done
• Longest Univalue Path   思路独特
• Diameter of Binary Tree           ,           done
• 
  
• Construct Binary Tree from Preorder and Postorder Traversal     困难！
• Closest Leaf in a Binary Tree           ,           done
• Boundary of Binary Tree           ,           done
• Binary Tree Right Side View            ,           done
• Kill Process           ,           done
  

  

12/18 Tree (not BST)

• 用Stack遍历树！
• Binary Tree Longest Consecutive Sequence            ,           done
• Binary Tree Longest Consecutive Sequence II            ,           类似Binary Tree Maximum Path Sum
• Binary Tree Maximum Path Sum            ,           done
• 
  
• Find Leaves of Binary Tree            ,           done
• Find Bottom Left Tree Value            ,           done
• Encode N-ary Tree to Binary Tree           ,           done
• Serialize and Deserialize N-ary Tree           ,           done
• Construct Binary Tree from String           ,           done
• Maximum Binary Tree
• Populating Next Right Pointers in Each Node            ,           done
• Flatten Binary Tree to Linked List            ,           done
• Binary Tree Upside Down            ,           done
• Leaf-Similar Trees            ,           done
  

• Find Duplicate Subtrees            ,           done
• Add One Row to Tree
  

• 二叉树morris 遍历  ，   看中序遍历那一题！
  

12/19  BST  看普林斯顿复习复习

• Range Sum of BST            ,           done
• 
  
• BST 第K大！！！
• Find Median in BST
• 
  
• Split BST            ,           done
• Largest BST Subtree     一类典型的题！！！
• Delete Node in a BST            ,           done
• Serialize and Deserialize BST            ,           done
• Closest Binary Search Tree Value II      极难！！
• Unique Binary Search Trees II
• Recover Binary Search Tree           不容易！
  
• Convert Sorted List to Binary Search Tree            ,           done
• Convert Binary Search Tree to Sorted Doubly Linked List           ,           done
• Two Sum IV - Input is a BST           ,           done
• Kth Smallest Element in a BST           ,           done
  

12/20 设计

• Design Log Storage System          ,         done
• Shortest Word Distance II          ,         done
• Design Snake Game          ,         done
• Design Circular Queue          ,         done
• All O`one Data Structure           ,         done
• Moving Average from Data Stream          ,         done
• 
  

12/21 ~ 12/22  

• 复习总结所有Tree题目
  

12/23 ~ 12/25  String

• Valid Parenthesis String        ,       困难！
• Find and Replace Pattern          ,          困难！
• Stamping The Sequence       ,       困难！
• One Edit Distance        ,       困难！
• Compare Version Numbers        ,        done
• Rotated Digits           ,          done
• Buddy Strings           ,          done
• String Compression           ,         done
• Design Compressed String Iterator        ,       困难！
• Expression Add Operators         ,       回溯
• Word Subsets          ,          done
• Output Contest Matches           ,          done
• Bold Words in String           ,          done
• Substring with Concatenation of All Words           ,          done
• Word Abbreviation      ,       困难！
• Parse Lisp Expression        ,       困难！
• Repeated Substring Pattern           ,          双指针！
• Robot Return to Origin           ,          done
• Longest Uncommon Subsequence II           ,          困难！
• Score of Parentheses          ,          done
• String to Integer (atoi)           ,          done
• Interleaving String           ,         done
• Reverse String II           ,          done
  

12/26  最大流和二分图匹配

12/26  复习前两天的String题
12/26  复习Heap HashMap





12/27 ~ 12/28 设计

• Design In-Memory File System        ,       done
• Implement Rand10() Using Rand7()       困难
• LRU Cache        ,       done
• LFU Cache        ,       done
• Peeking Iterator        ,       done
• Flatten Nested List Iterator
• Design Tic-Tac-Toe        ,       done
• Maximum Frequency Stack          困难
• Min Stack
• Max Stack
• Implement Magic Dictionary       ,       done
• Design Compressed String Iterator        ,      done
• Design Hit Counter        ,      done
  

TODO

• Patching Array
• Remove K Digits
• Find Permutation
• Delete Columns to Make Sorted II
• Bag of Tokens
  

TODO

• Car Fleet
• Regions Cut By Slashes
• Ugly Number II
• Super Ugly Number
• Binary Tree Vertical Order Traversal
• Divide Two Integers
• Sparse Matrix Multiplication
• Super Egg Drop
• 
  
• 普林斯顿  sorting 基础知识
• 
  

12/29 ~ 12/31
温习past projects + 改简历

• 先快速改一遍，然后上传到地里，或者网上找人改改
• 然后根据feedback再改一遍
  

12/29

• 复习Binary Search
• 按值二分, while条件一般不带等号, 但不论何时也要遵循区间一致性原则
• Maximum Average Subarray II
• Minimize Max Distance to Gas Station
• Split Array Largest Sum
• Find K-th Smallest Pair Distance
• Kth Smallest Number in Multiplication Table
  
• Kth Smallest Element in a Sorted Matrix
  

01/02 区间类

• Interval
• Meeting Room
• My Calendar
• https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=465898&extra=&page=1
• 第三轮问题
  
• https://www.geeksforgeeks.org/interval-tree/
• Data Stream as Disjoint Intervals
• Falling Squares
• Range Module
  

https://leetcode.com/articles/a- ... s-lazy-propagation/



TODO  

• HashTable
• Stack  
• Array   
• BFS
• Heap
• DP
  

• Prefix and Suffix Search
• Sliding Puzzle
• Flip Game II
  
• Open the Lock
• Domino and Tromino Tiling
• Count Numbers with Unique Digits
• Super Egg Drop
• Wiggle Sort II
  

TODO

• Encode String with Shortest Length
• Encode and Decode Strings
• Reverse Words in a String
• Generalized Abbreviation
• Expressive Words
• Minimum Unique Word Abbreviation
• Delete Operation for Two Strings
• Ambiguous Coordinates
  

二分  BFS  巩固复习


阅读Elements那本书



12/31 链表专题

• Remove Nth Node From End of List          ,        done
• Intersection of Two Linked Lists          ,        done
• Reverse Linked List         ,        done
• Reverse Linked List II         困难！
• Insert into a Cyclic Sorted List       困难！
• Add Two Numbers         困难！
• Add Two Numbers II      用Stack
• Plus One Linked List        困难！
• Split Linked List in Parts       困难！
• Reverse Nodes in k-Group      困难！
• Reorder List       找到中间node，reverse后半段，再merge.  关键一步是mid.next = null
  

01/03 ~ 01/04 数学专题

• Stone Game           困难！
• Rectangle Overlap          ,        done
• Nth Digit           困难！
• Solve the Equation        困难！
• Fraction to Recurring Decimal          ,        done
• Convex Polygon
• Largest Component Size by Common Factor
• X of a Kind in a Deck of Cards          ,        done
• Strobogrammatic Number III            困难！
• 
  
• Smallest Good Base
• Reaching Points
• Count Numbers with Unique Digits
• Water and Jug Problem            ,         done
• Power of Two          ,        done
• Power of Three          ,        done
  

01/03 ~ 01/04 计算几何

• Erect the Fence
• Random Flip Matrix
• Minimum Area Rectangle         ,      用Map建立坐标mapping
• Minimum Area Rectangle II        ,      done
• Mirror Reflection