Programming

C 當我們要去評價程式碼的品質時，我們會考慮以下元素： 正確性(correctness): 程式碼是否有正確的解決我們的問題 設計(design): 程式碼的好壞決定於它的效率與可讀性 風格(style): 程式碼在視覺上是否有良好的format 我們的第一個 C 語言程式： #include <stdio.h> int main(void) { printf("hello, world\n"); } 整合開發環境、編譯器、介面 IDEs, compilers, interfaces 在執行程式前，我們必須將程式碼轉變成電腦可讀的 binary codes，也就是 0 與 1。 IDE(integrated development environments) 可以協助我們開發、編譯程式碼。如Visual Studio Code 我們撰寫的程式碼為開源碼(source code)，我們必須將他轉變成機器碼(machine code)，才能被電腦執行。 編譯器(compiler)是將一種語言轉變成另一種語言的程式，例如將開源碼編譯成機器碼。 在 IDE 中，我們可以在一個叫作 terminal 的視窗中輸入指令。 terminal 提供了 command-line interface(CLI) 當我們輸入 make hello，會產生一個叫作 hello 的檔案，我們可以透過輸入 ./hello 執行它。 . 代表當下的目錄，上面的指令代表我們要執行當下目錄中叫作 hello 的檔案。 hello 即是內含機器碼的檔案。 欲刪除檔案可以用 rm 指令。 輸入 ls 列出當下目錄所包含的檔案。 若源碼檔經過修過，則必須重新編譯，才能對執行檔進行修改。 函式、引數、傳回值、變數 Functions, Arguments, Return Values, Variables printf("Hello, world"); 此處，介紹一個叫作 printf 的函數 f 代表 formatted 的字串。字串是多個字元(characters)組成的字詞，在 C 中，我們需要用雙引號("")來包住它。 括號 () 使我們可以輸入引數，也就是 printf 函數的 input。 最後，我們需要分號 ;，來宣告述句的結束。 其中，函式的一種產物叫作 side effect，也就是我們可以觀察到的變化，如螢幕印出字樣，或是發出聲響。 相比與 **side effects，我們也可以將函式的回傳值用於程式中，回傳值通被儲存於變數中。 string answer = get_string("What's your name? "); 此處，示範 CS50 IDE 中的一個函數。 這裡的 get_string為函式，而What's your name? 為引數。 然後，我們可以將回傳值存入到變數中，以上例，我們可利用賦值運算子(=)將右值(r_value)傳給左值(l_value)的answer。 最後，我們宣告變數的變數型別(type)。 如果我們嘗試將上述的變數改為其他變數型別，編譯器會顯示錯誤。 printf("Hello, world\n"); 我們此處為了換行，而使用了 escape sequence \n。

1. transient 的作用及使用方法 當一個物件繼承(implements)了 Serializable 介面，這個物件就可以被序列化，Java 的序列化模式為開發者提供了許多便利，開發者可以不必關心具體序列化的過程，只要繼承了 Serializable 介面，該類別(class)的所有屬性(property)和方法(method)都會自動序列化。 然而在實際開發過程中，有些屬性需要序列化，有些屬性則不需要。 用戶的私密訊息如密碼、銀行帳號等，通常不希望在網路操作時被傳輸。 此時，便可在這些對應的變數前加上 transient。 如此一來，這些私密訊息的生命週期只會存在於調用者的記憶體(memory)中，不會寫到磁碟(disk)裡。 注意讀取時，讀取數據的順序一定要和存放數據的順序保持一致。 範例： import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutput; import java.io.ObjectOutputStream; import java.io.Serializable; public class TransientExample { public static void main(String[] args){ User user = new User(); user.setUsername("Rain"); user.setPassword("12345678"); System.out.println("Read before Serializable: "); System.out.println("Username: " + user.getUsername()); System.out.println("Password: " + user.getPassword()); try { ObjectOutput os = new ObjectOutputStream(new FileOutputStream("/Users/rainhu/workspace/algo/temp/user.txt")); os.writeObject(user); os.flush(); os.close(); } catch (FileNotFoundException e){ e.printStackTrace(); } catch (IOException e){ e.printStackTrace(); } try { ObjectInputStream is = new ObjectInputStream(new FileInputStream("/Users/rainhu/workspace/algo/temp/user.txt")); user = (User) is.readObject(); is.close(); System.out.println("Read after Serializable: "); System.out.println("Username: " + user.getUsername()); System.out.println("Password: " + user.getPassword()); } catch (FileNotFoundException e){ e.printStackTrace(); } catch (IOException e){ e.printStackTrace(); } catch (ClassNotFoundException e){ e.printStackTrace(); } } } class User implements Serializable{ private static final long serialVersionID = 8294180014912103005L; private String username; private transient String password; public String getUsername(){ return username; } public void setUsername(String username){ this.username = username; } public String getPassword(){ return password; } public void setPassword(String password){ this.password = password; } } 輸出的結果是： Read before Serializable: Username: Rain Password: 12345678 Read after Serializable: Username: Rain Password: null ...

如何初始化 vector 事先準備 #include <iostream> #include <vector> using namespace std; 1. 利用 push_back() 函式 vector<int> A; A.push_back(1); A.push_back(2); A.push_back(3); // A = [1,2,3] 2. 利用重載建構子(overloaded constructor) int size = 5; int fill = 2; vector<int> B(size, fill); // B = [2,2,2,2,2] 3. 將 array 傳給 vector 的建構子(-std=c++11) vector<int> C{1, 2, 3, 4, 5}; // C = [1,2,3,4,5] 4. 利用既有的 array int array[] = {1,2,3,4,5}; vector<int> D(array, array+4); // D = [1,2,3,4] 5. 利用既有的 vector vector<int> E(C.begin()+1, C.end()-3); // E = [2] 6. 利用 fill 函式 vector<int> F(6); fill(F.begin(), F.end(), 3); // F = [3,3,3,3,3,3] Reference ...

Integer.bitCount 的函式解析 要計算整數以二進制的方式表示時，所有 bit 位為 1 的總和。 雛形 從低位開始，檢查是否為 1。 public static int bitCount(int i){ int count = 0; while (i > 0) { if ((i & 1) == 1) // 如果最低位為 1，count就加 1 count++; i >>= 1; // 向右推進 1 位，等同於 num /= 2; } return count; } 時間複雜度為 \(O(n)\)，\(n\) 為整數的位數(bit 數)。 優化 利用(i - 1) & i 可以消除最低位數的 1 的性質來計算。 public static bitCount(int i){ int count = 0; while (i > 0){ i = i & (i - 1); // 0b0101_1100 - 1 = 0b0101_1011, 且 0b0101_1100 & 0b0101_1011 = 0b0101_1000; count++; } return count; } 時間複雜度為 \(O(n))\)，\(n\) 為位數為 1 的個數。 利用 int 的特性再優化 因為 int 的最大正整數為 2^31，故我們可以兩兩錯位相加來求和 private static int bitCount(int i){ i = (i & 0x55555555) + ((i >>> 1) & 0x55555555); // 0b0101_0101_0101_0101_0101_0101_0101_0101 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); // 0b0011_0011_0011_0011_0011_0011_0011_0011 i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f); // 0b0000_1111_0000_1111_0000_1111_0000_1111 i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff); // 0b0000_0000_1111_1111_0000_0000_1111_1111 i = (i & 0x0000ffff) + ((i >>>16) & 0x0000ffff); // 0b0000_0000_0000_0000_1111_1111_1111_1111 return i; } 時間複雜度為 \(O(1))\)。 Source Code(final) public static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; } 一、三、四、五步不進行消位，在最後再利用 i & 0x3f 消去不必要的位數

一、OS 簡介 作業系統(Operating system, OS) 是管理電腦硬體與軟體資源的電腦程式，同時也是電腦系統的核心與基石。OS主要有以下兩個功能： 資源分配者 監控使用者程式的執行，以防止不正常的運作造成對系統的危害。 一個標準 PC 的作業系統應該提供以下功能： 行程管理 (processing management) 記憶體管理 (memory management) 檔案系統 (file system) 網路通訊 (networking) 安全機制 (security) 使用者介面 (user integerface) 驅動程式 (device drivers) OS 系統依大小來區分： 大型電腦：IBM OS/360 個人電腦：Windows、Linux、BSD、Mac OS X 嵌入式：VxWorks、eCos、Sysbian OS、Palm OS 依品牌來區分： 類 Unix 家族：包含 System V、BSD 與 Linux。 微軟 Windows：Windows NT 核心，包含 Windows 2000、Windows XP。 蘋果 mac OS：執行於蘋果 Macintosh 系列電腦上的作業系統 Chrome OS：基於 Google 的瀏覽器 Google Chrome 的 Linux 核心。 ...

HashMap.comparableClassFor(Object x) 的函式解讀 原文敘述 Returns x’s Class if it is of the form “class C implements Comparable”, else null. 我的翻譯 當x的類別為Comparable的實作時，返回x的類別；否則返回 null。 藉由這個函式實例的解讀，可以了解一下類別、泛型的相關概念。 Source Code static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (Type t : ts) { if ((t instanceof ParameterizedType) && ((p = (ParameterizedType) t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } instanceof insanceof 可理解成某類別的實作，無論是執行期時的類別，或是父類別，或是它實現的介面，或父類別實現的介面…，總之只要在繼承鏈上有這個類別就可以了。 getClass() 與instanceof相對應的是getClass()函式，無論該物件如果轉型，getClass()都會返回它執行時期的類別，可以簡單理解成實際類別，換言之也就是我們 new 出來物件時使用的類別。 有一種例外情形是匿名物件，當匿名物件調用getClass()時，返回的是依賴它的物件在執行期的類別，並以1,2,3…的index區分。 getGenericInterfaces() getGenericInterfaces()方法返回的是該物件在執行期時直接實作的介面。必然是該類別自己實作的介面，繼承的則不可。 getGenericSuperclass()和getSuperclass() 這兩個函式雖然沒有出現在 comparableClassFor(Object x)中，但也順帶一提。 ...

什麼是 Computer Science(CS)? CS 意在解決問題，更精準地說，是將問題 (input) 轉換成答案 (output) 的過程。 在計算機的世界，為了表達 inputs 和 outputs，我們必須將資訊標準化來儲存與操作它們，因為計算機只讀得懂 0 與 1 (開路/通路)。 如何表達數字? 在人類的世界，人們使用十進制(Decimal)。 在計算機的世界，用的是二進制(Binary)，也就是 0 與 1。 \(1+1=10\) \((1,2,3,4,5,6,7,…)_{10}=(001,010,011,100,101,110,111,…)_2\) 每個二進制的位元(digit)稱為 bit。 在現代計算機結構中，是由數以億計的電晶體(transistors)所組成的。 電晶體是一種具有開關(switch)性質的邏輯元件。 大部分的計算機一次用 8 個 bits，或稱 1 bytes，來表達數字。 \(8 \text{bits}=1 \text{bytes}\) 如何表達文字? 要表達文字，只需將不同的字元定義到對應的數字即可。 ASCII，American Standard Code for Information Interchange，即是一種基於拉丁字母的編碼系統，可應用顯示現代英語。 A->65, B->66, …etc a->97, b->98, …etc H->72, I->73, !->33, so HI!=72, 73, 33 在不同語言，有不同的字符，就必須定義新的編碼系統，來容納更多的字符。 如 Unicode。 如 emojo 顏文字也是一種字符。 如何表達顏色? 同理，可以把不同的數字定義給不同的顏色，其中最常見的就是 RGB 系統。 由紅綠藍色塊所組成。 紅、綠、藍又個別以 8 bits 儲存的 256 種不同層度的顏色強度表示。 一共由 24 bits 來表達，超過1百萬種顏色。 那圖案、影片、音樂呢? 圖案是由數以萬計的色塊(dots)所組成，在螢幕顯示器上我們稱作畫素(pixels)。 影片則是由連續的圖案經由連續播放所建構而成的。 音樂同樣可以用 bits 來表達，其中 MIDI 是一種用數字來表達音符的形式。 All are composed by 0 and 1 in the computer world. ...

List of Generics equality Case In leetcode no. 39 Combination Sum gives Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. ...

How to say hello to the world? Java class Hello{ public static void main(String[] args){ System.out.println("Hello World!"); } } C #include <stdio.h> int main(){ printf("Hello World!"); return 0; } C++ #include <iostream> int main(){ std::cout << "Hello World!" << std::endl; return 0; } ###C# namespace HelloWorld{ class Hello{ static void Main(String[] args){ System.Console.WriteLine("Hello World!"); } } } Python print("Hello World!") Ruby puts 'Hello World!' TCL Language puts "Hello World!" JavaScript console.log("Hello World!"); TypeScript console.log 'Hello World!' Perl print "Hello World!"; R cat('Hello World!'); Swift println('Hello World!'); Kotlin fun main(args: Array<String>){ println("Hello World!") } Go println('Hello World!'); PHP echo "Hello World!"; VBA msgbox "Hello World" Assembly Language global _main extern _printf section .text _main: push message call _printf add esp, 4 message: db 'Hello World!', 11, 0 Me Hello the fucking world

Coding Interview University John Washam: I originally created this as a short to-do list of study topics for becoming a software engineer, but it grew to the large list you see today. After going through this study plan, I got hired as a Software Development Engineer at Amazon! You probably won’t have to study as much as I did. Anyway, everything you need is here. I studied about 8-12 hours a day, for several months. This is my story: Why I studied full-time for 8 months for a Google interview ...