Posts

1pwnch

Play With Docker

Docker has become a trend that every engineer would be familiar with, but most of the people would mistake docker for a kind of virtual machine. In this post, I would like to show the difference between container and virtual machine. Of course, I would like to help people to figure out how to play with docker in easier way. Difference between Container and Virtual machine With the picture above, you should find the difference between virtual machine and container.

Static Link vs Dynamic Link

In this post, I would show the way to create static library and dynamic library and how they link to the executable files. I would not dig into the details of comparison, advantages, or disadvantages between static and dynamic library, please make sure you already have a whole picture before starting on this post. Create static library First, create a source file without main function as our library. Attention, filename should start from lib so that compiler can identify it as library file.

揭開DP狀態壓縮的神秘面紗

DP狀態壓縮可以優化空間複雜度,通常用於狀態只依靠鄰近狀態時,可以把二維的狀態壓縮成一維來表示。是不是聽到這裡覺得,狀壓是一個很猛的,只有聰明人會用的東西?不,這篇文章就是來為你解開狀態壓縮神秘的面紗,希望透過這篇文章,可以讓每個讀者都輕鬆寫出狀態壓縮。 案例介紹 我非常不建議一開始就學狀態壓縮的寫法,應該先寫好高維的表示方式再進行降維。多說無益,這裏就給個案例 - Leetcode 494 - TargetSum。這題的解法不是此篇文章探討的重點,所以我只會focus在優化的部分。這題用dfs會超時,可以換成背包問題:求子集總和為target的方法數。背包問題有兩個狀態:一是目前可以挑的物品,另外一個則是背包剩下的容量,狀態轉移方程如下: 1 2 3 4 //if pick the number dp[i][sum] = dp[i - 1][sum - current_num] + dp[i - 1][sum] //if not pick dp[i][sum] = dp[i - 1][sum] 有了狀態轉移方程就很容易實現了。 1 2 3 4 5 6 7 8 for(int i = 1; i <= n; i++) { for(int j = 0; j <= target; j++) { if(j - nums[i - 1] >= 0) dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j]; else dp[i][j] = dp[i - 1][j]; } } 每一個i的狀態都只需要依賴i - 1的值,所以或許我們根本不需要紀錄那麼多i的狀態,因此這個解法還可以進行優化。下一部分就是本文重點:狀態壓縮。

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).