I am an first-year computer science major master student at the University of Southern California
1143. Longest Common Subsequence 1026. Maximum Difference Between Node and Ancestor 386. Lexicographical Numbers 150. Evaluate Reverse Polish Notation 679. 24 Game 134. Gas Station
The core of dynamic programming: recursion with memorization. Breaking a big problem into small sub-problems and only computing each sub-problem once. Notice dynamic programming is an algorithm that will essentially search the entire solution space It’s usually helpful to think what’s the last step in your solution (top-down) and what sub-problem will it generate. But … Continue reading “Dynamic Programming Revisit”
Problem Statement: Giving m unsorted arrays, return the k smallest elements Method #1: Min-heap Method 1: Using bottom-up heap construction to build a min-heap, then pop the smallest element n times Complexity analysis: Time to construct min-heap: O(n) Time to extract min k times: O(k * lgn) Total time complexity: O(n + k * lgn) … Continue reading “Full Analysis of Finding K Smallest in Sorted/Unsorted Arrays”
Follow My Blog
Get new content delivered directly to your inbox.