Posts

1pwnch

LintCode Weekly Contest 30 Condition String

I ran into the “Condition String” in weekly contest of LintCode and failed to solve it. After spending some time on it after the contest ended, I found that the first idea I came up with was wrong. Here comes my writeup. Problem Description Here I would give the screenshot of challenge: First solution [Fail] First, I tried to handle this problem with longest increase subarray. For example, in acec

LintCode Maximum Conn Area

At first, I thought this was just a simple BFS challenge with a little change. It was evaluated as a medium level; however, the process of solving problem was even interesting out of my expectation. It even helped me solve my myths about Union Find. Problem Description There is a two-dimensional array, only consists of 0 and 1. You can change a 0 to 1 at most once, please calculate the maximum area of connected 1s.

Implementation of PLA

In this article, I would show the by-hand implementation of PLA. I won’t get into the detail of the algorithm, but just help someone wants some practical experience. Also, I recommend everyone to implement it because only do it will you find the points you still not figure out about it. Dataset Here we have ten training sets and one test set. In datasets, we have two features and classification results in (0, 1).

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優化!