Programming

vector 的介紹 vector 是可變大小陣列的序列容器，採用連續的儲存空間來儲存元素，意味著可以採用下標來對 vector 的元素進行存取，和陣列 array 一樣高效，但是又不像陣列的大小是固定的，vector 的大小可以被動態處理，隨著元素量而增加。 #include <vector> vector 的使用 建構式 constructor vector<int> v1; // 不進行初始化 vector<int> v2 = {1,2,3}; // 像陣列一樣初始化 vector<int> v3(v2); // 利用vector初始化 vector<int> v4(v2.begin(), v2.end()-1); // 利用iterator初始化 vector<int> v5(3, 0); // 含有3個0的vector 談一下特殊的二維vector，其實就是二維矩陣，寫法為 vector<vector<int>> vv(3, vector<int>(5, 0)); // vv[0] = [0, 0, 0, 0, 0] // vv[1] = [0, 0, 0, 0, 0] // vv[2] = [0, 0, 0, 0, 0] 遍歷 traverse 遍歷的方法有三種，分別是iterator，for loop，[]，其中**[]下標運算子只有string和vector**可以使用，因為他們的地址是連續的。 三種方法均是可讀、可寫。 vector<int> v = {0, 9, 3, 1, 6, 3, 9, 4, 3, 3}; // 1. iterator vector<int>::iterator it = v.begin(); while (it != v.end()){ cout << *it << " "; it++; } cout << endl; // 2. for loop for (int e : v){ cout << e << " "; cout << endl; } // 3. [] for (size_t i = 0; i < v.size(); ++i){ cout << v[i] << " "; cout << endl; } 資料的資刪查改 \( \def\arraystrecth{1.4}\begin{array}{|l|l|}\hline \text{methods}&\text{description}\\\hline\hline \text{push\_back}&\text{Add element at the end}\\\hline \text{pop\_back}&\text{Delete last element}\\\hline \text{insert}&\text{Insert elements}\\\hline \text{erase}&\text{Erase elements}\\\hline \end{array} \) ...

1. 請說明 Final, Finally, Finalize 三者不同? Final: 一種修飾關鍵字。 加在變數前，使變數成為常數。 加在方法前，使方法無法被覆寫(override)。 加在類別前，使類別不能被繼承(extend)。 Finally: 例外處理關鍵字，Try-Catch-Finally 功能為保證一定執行，用意是做資源釋放。 Finalize: 是Object類別的方法，故所有物件都一定有此方法。 當物件要銷毀前會執行的方法，此外可以透過 System.gc() 呼叫資源回收。 2. 請說明 String 字串中 == 與 .equals() 哪裡不同? ==: 比較儲存的值，基本型別(primitives)是儲存在 Stack 中，因此值會相同，字串是儲存在 String Pool 中，故 Stack 中存的是址。 使用 == 比較字串時，其實是比較他們的址。 equals(): 是 String 覆寫後的 equals 方法，比較值。 補充： Java 的字串有 String Pool 機制，當宣告一個新的字串時，Java 會先去 String Pool 中尋找是否有相同的字串，有則共用，無則新增。 若使用 String s1 = "Hello World"; 來宣告，則會透過字串池。 若使用 String s2 = new String("Hello World") 來宣告，則字串會存在 Heap 中，與上者的址不同。 3. 使用 “abc”.equals(s) 比較好還是 s.equals(“abc”)? 等效。 前者不會出現 NullPointerException。 4. Arrays 與 ArrayList 的差異? Arrays 可包含原始(primitive)及物件(object)，ArrayList只允許物件。 Arrays 大小固定，ArrayList 可動態調整。 ArrayList 提供許多方法，如 removeAll、iterator等。 5. stack 與 heap 的區別? stack: 可被預測生命週期的變數或函數資訊都放在 stack，例如：區域變數(local variable)、物件或陣列的返回位址(function/method return address)等資訊。 heap: 動態配置的記憶體空間，放置被 new 出來的物件以及內含的成員變數。 6. Arrays 與 String 的大小 Arrays 有 length 這個屬性。 String 有 legnth() 這個方法。 7. throw 與 throws 的區別 throws: throws 關鍵字通常被應用在聲明方法時，放在方法的大括號前，用來拋出異常，多個異常可以使用逗號隔開。後續使用者要調用方法時必須要拋出異常或者使用 try-catch 語句處理異常。 throw: throw 關鍵字通常用在設計方法時，預先宣告可能會產生的例外，後續方法使用者需要使用 try-catch 處理例外，或者使用 throws 關鍵字再拋出例外。 補充： throw 用於方法內，throws 用於方法的聲明。 throw 用於方法內拋出異常，throws 用於方法聲明上拋出異常。 throw 後面只能有一個異常，throws 可以聲明多個異常。 8. int 和 Integer 何者會占用更多記憶體? Integer，Integer 是一個物件，會在 heap 中儲存，並儲存址的值到 stack 中，而 int 只會保存值在 stack 中。 9. 是否能將 int 強制轉型為 byte? 可以，可以使用 b = (byte) a 來進行強制轉換，但是超過範圍的部分會被丟棄。 10. 是否能保證 gc 的執行? 否，垃報回收機制程式設計師無法保證，但可以透過 System.gc() 呼叫。 11. abstract class 與 interface 的區別? abstract class 可以宣告抽象方法，提供子類別實作。 interface 的方法必定是抽象方法。 一個類別可以繼承多個介面，但只能繼承一個抽象類別。 12. List 與 Set 區別? List: 有順序性(索引值)。 可重複。 ArrayList 實作了 List 介面。 ArrayList: 插入、刪除速度 \(O(n)\)，走訪速度\(O(1)\)。 LinkedList: 插入、刪除速度 \O(1)\)，走訪速度\(O(n)\)。 Set 無順序性(配合 iterator) 不可重複，走訪速度\(O(1)\)。 HashSet 實作了 Set 介面。 HashSet: 無順序性，查找速度快。 LinkedHashSet: 有順序性 TreeSet: 有排序性(依字母) Map 1.有元素鍵值(Key-Value)，搜尋快 2.元素可重複，鍵值如果重複新加入值會覆蓋舊有值 3.HashMap: 查找速度慢，插入刪除速度快 4.TreeMap: 有排序性

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 消去不必要的位數

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)中，但也順帶一提。 ...

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