Posts

1pwnch

Feel Free to Contact Me

Nice to meet you, I am Rafael. So… In this blog, I would record my learning process including Algorithm, writeup of OJ, System Design, Notes of Machine Learning/Deep Learning, Some myths I always mistake for and so on. You can search tags to find what you want. I would use my home language - which is Chinese to make the notes. Of course, if you are interested in specific articles, I am happy to translate for you in my free time.

Lexical Analysis

The goal of lexical analysis The goal of lexical analysis is to partition the input string into lexemes, identify the token of each lexeme then give to parser. On other hand, first part about lexemes is to partition input to units, and second part about token is to define the class of each units. Given a input string, such as foo = 42 Lexical-Analyzer would identify tokens as <"id", "foo">, <Op, "=">, and <"Int", "42"> Give to parser There are several kinds of token classes, such as Identifier, Integer, Numbers, Keyword, Whitespace.

Learn Compiler - Introduction

Once in college, I regreted not spending much time on learning compiler so hard. However, the opportunity comes to me again. Software analysis is very important for my research field in PhD: Automatic Exploitation Generation. Compiler is the necessary concept for Software analysis such for static analysis or dynamic analysis, I would grab this chance to learn compiler from basics again. This series include the learning notes for the Stanford course on edx, and would start from Introduction to each parts of Lexical Analysis, Parsing, Semantic Analysis, Optimization, and Code Generation.

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的狀態,因此這個解法還可以進行優化。下一部分就是本文重點:狀態壓縮。