Posts

1pwnch

AlgoExpert Longest Peak

This challenge is not difficult; however, I make a mistake when analyzing the time complexity. The reason is that I make a large duplicate and useless calculation in my solution. Take a look into the detail for the challenge “Longest Peak”. Writeup You can see the detail of challenge and my initial solution in this video. However, I can finish this problem in O(n) in fact. Why? Assume there is ten numbers in array:

LeetCode 33 Search in Rotated Array

First, I need to come up with the words, ‘Damn it’. This belongs to my LeetCode Self Challenge for 30 mins. I almost finish the problem, but I forget to check the search space for binary search, which should be the common sense for it. I will provide the writeup and the optimization here. Writeup The programming language in video is C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 int search(vector<int>& nums, int target) { if(nums.

Explore Binary Search

查找一個數組裡面的目標,我們能夠想到最快的方法可能是hash table,然而當數組很大時,內存就會爆掉!第二個選擇則是binary search。Binary search的觀念看似很簡單,然而卻有多種實現方法!最近在做一些題目時(包括面試時)發現binary search的應用面其實很廣,只要dataset有單調性,我們都可以用binary search把時間複雜度縮小到對數等級。特別感謝Leetcode出了Explore篇章幫助我進行摸索。下面我也會針對Explore上的題目做出解析來整理Binary search的訣竅! 解題過程 所有的元素為unique,尋找唯一的index Explore Binary Search 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int search(vector<int>& nums, int target) { if(target < -9999 || target > 9999) return -1; int start = 0, end = nums.size() - 1, mid = 0; while(start <= end) { mid = start + ((end - start) >> 1); // remember your bracket if(nums[mid] == target) return mid; if(nums[mid] < target) start = mid + 1; else end = mid - 1; } return -1; } }; 以上我的解法只有哪到66%的成績,但在我審了一遍前段的code之後,我推斷時間複雜度只差在I/O優化!

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.