Posts

1pwnch

The Skyline Problem

UVa 105 - The Skyline Problem This problem tests the application of priority queue which is implemented with min-heap. Min-heap takes O(logn) to insert a new node. It takes O(1) to extract current minimum value and O(logn) to sort again. With this data structure, I can iterate the boundaries of building in ascending order. My idea is recording all boundaries and associated heights in priority queue and current existing height in multiset.

Count of Smaller Nums After Self

I use modified-BST to solve this problem. Each time inserting a new node takes O(logn) and also updates the value of count, and there are n nodes; therefore, I think the time complexity of my solution is O(nlogn). Writeup The programming language in video is C++ For the source code in video: Github Conclusion Order of input: left to right or right to left? Definition of node: what member should we define for each nodes in tree?

Single Number II on Leetcode

State machine is common and useful technique to be used in algorithm. I really recommend you to figure the last solution out thoroughly. Then try my extended problem! Writeup The programming language in video is C++ For the source code in video: Github Conclusion Solution 1 and 2 are similiar to each other, and they both try using 3*n + 1 to separate the single number from the others.

N Queens on Leetcode

I spend so much time on solving this problem. My challenge is not just solving this problem, but how to enhance the efficiency of my solution. The only one solution I come up with is DFS + check each of previous rows; however, this solution is too slow. Therefore, in following of my youtube video, I will explain four to five solutions, from idea building, coding by hands, and even debugging.

Stock Problem on Leetcode

I spend much time on completing a series of stock problem on leetcode. Some problem can be solved with greedy while others can be solved with dynamic programming. However, I ran into many challenges while defining the subproblems. Therefore, I would like to take a conclusion in this article, hope someone also try to solve these problems find this article helpful!