Programming

cout Functions 設定顯示小數點位數 setprecision(int n) and fixed #include <iostream> #include <iomanip> using namespace std; int main(){ double a = 5.43/2.653; cout << a << endl; // 2.04674 cout << setprecision(3) << fixed; cout << a << endl; // 2.047 return 0; } 顯示 Boolean 值 std::boolalpha #include <iostream> using namespace std; int main(){ bool a = true; cout << a << endl; // 1 cout << std::boolalpha; cout << a << endl; // true return 0; }

演算法(Algorithms) Non-Manupulating Algorithms 1. sort() sort(first_iterator, last_iterator) 對 vector 作排序 2. reverse() reverse(first_iterator, last_iterator) 反轉 vector 的排序 3. *max_element() *max_element(first_iterator, last_iterator) 找出 vector 的最大值 4. *min_element() *min_element(first_iterator, last_iterator)` 找出 vector 的最小值 5. accumulate accumulate(first_iterator, last_iterator, initial value of sum) 計算 vector 的總和 #include <iostream> #include <algorithm> #include <vector> #include <numeric> using namespace std; void print(vector<int>& vec){ for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++){ cout << *it << " "; } cout << endl; } int main(){ int arr[] = {10, 20, 5, 23, 42, 15}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // print initial vector print(vec); // [10, 20, 5, 23, 42, 15] // sort sort(vec.begin(), vec.end()); // [5, 10, 15, 20, 23, 42] print(vec); // reverse reverse(vec.begin(), vec.end()); // [42, 23, 20, 15, 10, 5] print(vec); // max & min cout << *max_element(vec.begin(), vec.end()) << endl; // 42 cout << *min_element(vec.begin(), vec.end()) << endl; // 5 // accumulate cout << accumulate(vec.begin(), vec.end(), 0) << endl; // 115 return 0; } 6. count() count(first_iterator, last_iterator, x) 計算 vector 中 x 的數量 7. find() find(fist_iterator, last_iterator, x) 回傳 vector 中第一個符合的 iterator，若無則傳回 v.end()。 #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int arr[] = {10, 20, 5, 23 ,42, 20, 15}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); cout << count(vec.begin(), vec.end(), 20); // 2 find(vec.begin(), vec.end(),5) != vec.end() ? // Element found cout << "\nElement found": cout << "\nElement not found"; return 0; } 8. binary_search() binary_search(first_iterator, last_iterator, x) 測試 x 是否存在已排序的 vector 中 9. lower_bound() lower_bound(first_iterator, last_iterator, x) 傳回指向不大於 x 的元素的 iterator 10. upper_bound() upper_bound(first_iterator, last_iterator, x) 傳回指向大於 x 的元素的 iterator #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); sort(vec.begin(), vec.end()); cout << binary_search(vec.begin(), vec.end(), 20) << endl; // 1 cout << (lower_bound(vec.begin(), vec.end(), 20) - vec.begin()) << endl; // 3 cout << (upper_bound(vec.begin(), vec.end(), 20) - vec.begin()) << endl; // 5 return 0; } Manipulating Algorithms 1. vec.erase() arr.erase(position_to_be_deleted) 移除指定位置的元素 2. vec.erase(unique()) arr.erase(unique(arr.begin(), arr.end()), arr.end()) 移除已排序的 vector 中重複的元素 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int arr[] = {5, 10, 15, 20, 20, 23, 42, 45, 20, 20, 20, 20, 20}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // [5, 10, 15, 20, 20, 23, 42, 45, 20, 20, 20, 20, 20] vec.erase(vec.begin() + 1); // [5, 15, 20, 20, 23, 42, 45, 20, 20, 20, 20, 20] sort(vec.begin(), vec.end()); // [5, 15, 20, 20, 20, 20, 20, 20, 20, 23, 42, 45] vec.erase(unique(vec.begin(), vec.end()), vec.end()); // [5, 15, 20, 23, 42, 45] return 0; } 3. next_permutation() next_permutation(first_iterator, last_iterator) 對 vector 作動成下一個字典排序 4. prev_permutation() prev_permutation(first_iterator, last_iterator) 對 vector 作動成上一個字典排序 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int arr[] = {1,2,3,4,5,6,7}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // [1,2,3,4,5,6,7] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,5,7,6] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,6,5,7] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,6,7,5] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,7,5,6] prev_permutation(vec.begin(), vec.end()); // [1,2,3,4,6,7,5] return 0; } 5. distance() distance(first_iterator, last_iterator) #include <iostream> #include <algorithm> #include <vector> #include "print.cc" using namespace std; int main(){ int arr[] = {5,10,15,20,20,23,42,45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); cout << distance(vec.begin(), max_element(vec.begin(), vec.end())) << endl; // 7 // == max_element(vec.begin(), vec.end()) - vec.begin(); return 0; } Array algorithms 1. any_of() any_of(first_iterator, last_iterator, [](passing_value { return statement; })) ? if_true : if_false; vector 中是否有任何元素滿足條件 2. all_of() all(first_iterator, last_iterator, [](passing_value { return statement; })) ? if_true : if_false; vector 中是否有全部元素滿足條件 3 none_of() none_of(first_iterator, last_iterator, [](passing_value { return statement; })) ? if_true : if_false; vector 中是否沒有元素滿足條件 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ vector<int> vec1 {1,3,7,9,11,17,23}; all_of(vec1.begin(), vec1.end(), [](int x) { return (x & 1) == 1;}) ? cout << "All odds\n" : cout << "Not all odds\n"; vector<int> vec2 {1,3,6,8,9,11,13}; any_of(vec2.begin(), vec2.end(), [](int x) { return (x & 1) == 0;}) ? cout << "There are at least one even\n" : cout << "There are no any even\n"; none_of(vec1.begin(), vec1.end(), [](int x) { return (x & 1) == 0;}) ? cout << "There are no any even\n" : cout << "There are at least one even\n"; return 0; } 4. copy_n() copy_n(source_array, array_size, target_array) 複製陣列 #include <iostream> #include <algorithm> using namespace std; int main(){ int arr[] = {1,2,3,4,5,6}; int arr2[6]; copy_n(arr, 6, arr2); for (int i : arr2){ cout << i << " "; } return 0; } 5. iota() iota(array_name, array_size, starting_number) 逐一增加並寫入指定大小的陣列 // C++ code to demonstrate working of iota() #include<iostream> #include<numeric> // for iota() using namespace std; int main(){ // Initializing array with 0 values int ar[6] = {0}; // Using iota() to assign values iota(ar, ar+6, 20); // Displaying the new array cout << "The new array after assigning values is : "; for (int i=0; i<6 ; i++) cout << ar[i] << " "; return 0; } Partition operations C++ 在標準模板資料庫(STL)中有一個 class 可以來做 partition 的演算法。 Partition 就是用來將容器裡面的元素依指定的條件做分隔。 1. partition() partition(begin, end, conditon) 依照指定條件做分隔。 2. is_partition() is_partitioned(begin, end, condition 判斷元素是否依照條件分開。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ vector<int> vec = {2,1,5,6,8,7}; is_partitioned(vec.begin(), vec.end(), [](int x){ return x % 2 == 0; }) ? cout << "Vector is partitioned": cout << "Vector is not partitioned"; cout << endl; partition(vec.begin(), vec.end(), [](int x){ return x % 2 == 0; }) ? cout << "The partitioned vector is : "; for (int &x : vec) cout << x << " "; return 0; } 3. stable_partition() stable_partition(begin, end, condition) 依指定條件作分隔，同時保留元素的相對位置。 4. partition_point() partition_point(begin, end, condition) 返回指向分隔位置的迭代器，也就是在 [begin, end] 範圍內的第一個元素。 This function returns an iterator pointing to the partition point of container i.e. the first element in the partitioned range [beg,end) for which condition is not true. The container should already be partitioned for this function to work. // C++ code to demonstrate the working of // stable_partition() and partition_point() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // partitioning vector using stable_partition() // in sorted order stable_partition(vect.begin(), vect.end(), [](int x) { return x%2 == 0; }); // Displaying partitioned Vector cout << "The partitioned vector is : "; for (int &x : vect) cout << x << " "; cout << endl; // Declaring iterator vector<int>::iterator it1; // using partition_point() to get ending position of partition auto it = partition_point(vect.begin(), vect.end(), [](int x) { return x%2==0; }); // Displaying partitioned Vector cout << "The vector elements returning true for condition are : "; for ( it1= vect.begin(); it1!=it; it1++) cout << *it1 << " "; cout << endl; return 0; } 5. partition_copy() partition_copy(begin, end, begin1, begin2, condition) This function copies the partitioned elements in the different containers mentioned in its arguments. It takes 5 arguments. Beginning and ending position of container, beginning position of new container where elements have to be copied (elements returning true for condition), beginning position of new container where other elements have to be copied (elements returning false for condition) and the condition. Resizing new containers is necessary for this function. // C++ code to demonstrate the working of // partition_copy() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // Declaring vector1 vector<int> vect1; // Declaring vector1 vector<int> vect2; // Resizing vectors to suitable size using count_if() and resize() int n = count_if (vect.begin(), vect.end(), [](int x) { return x%2==0; } ); vect1.resize(n); vect2.resize(vect.size()-n); // Using partition_copy() to copy partitions partition_copy(vect.begin(), vect.end(), vect1.begin(), vect2.begin(), [](int x) { return x%2==0; }); // Displaying partitioned Vector cout << "The elements that return true for condition are : "; for (int &x : vect1) cout << x << " "; cout << endl; // Displaying partitioned Vector cout << "The elements that return false for condition are : "; for (int &x : vect2) cout << x << " "; cout << endl; return 0; } Numeric algorithms 1. apply() apply([](int x){return operation;}) 對陣列所有元素做運算 2. arr.sum() arr.sum() 計算陣列所有元素的總合 // C++ code to demonstrate the working of // apply() and sum() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Declaring new valarray valarray<int> varr1 ; // Using apply() to increment all elements by 5 varr1 = varr.apply([](int x){return x=x+5;}); // Displaying new elements value cout << "The new valarray with manipulated values is : "; for (int &x: varr1) cout << x << " "; cout << endl; // Displaying sum of both old and new valarray cout << "The sum of old valarray is : "; cout << varr.sum() << endl; cout << "The sum of new valarray is : "; cout << varr1.sum() << endl; return 0; } 3. arr.min() arr.min() 傳回陣列中最小的元素 4. arr.max() arr.max() 傳回陣列中最大的元素 // C++ code to demonstrate the working of // max() and min() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Displaying largest element of valarray cout << "The largest element of valarray is : "; cout << varr.max() << endl; // Displaying smallest element of valarray cout << "The smallest element of valarray is : "; cout << varr.min() << endl; return 0; } 5. arr.shift() arr.shift(int n) 對陣列做 n 個位的移動，正為向右移，負為向左移，缺位補零。 6. cshift() arr.cshift(int n) 對陣列做 n 個位的移動，正為向右移，負為向左移，缺位使用循環補位。 // C++ code to demonstrate the working of // shift() and cshift() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Declaring new valarray valarray<int> varr1; // using shift() to shift elements to left // shifts valarray by 2 position varr1 = varr.shift(2); // Displaying elements of valarray after shifting cout << "The new valarray after shifting is : "; for ( int&x : varr1) cout << x << " "; cout << endl; // using cshift() to circulary shift elements to right // rotates valarray by 3 position varr1 = varr.cshift(-3); // Displaying elements of valarray after circular shifting cout << "The new valarray after circular shifting is : "; for ( int&x : varr1) cout << x << " "; cout << endl; return 0; } 7. arr1.swap(arr2) arr1.swap(arr2) 陣列做交換 // C++ code to demonstrate the working of // swap() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main(){ // Initializing 1st valarray valarray<int> varr1 = {1, 2, 3, 4}; // Initializing 2nd valarray valarray<int> varr2 = {2, 4, 6, 8}; // Displaying valarrays before swapping cout << "The contents of 1st valarray " "before swapping are : "; for (int &x : varr1) cout << x << " "; cout << endl; cout << "The contents of 2nd valarray " "before swapping are : "; for (int &x : varr2) cout << x << " "; cout << endl; // Use of swap() to swap the valarrays varr1.swap(varr2); // Displaying valarrays after swapping cout << "The contents of 1st valarray " "after swapping are : "; for (int &x : varr1) cout << x << " "; cout << endl; cout << "The contents of 2nd valarray " "after swapping are : "; for (int &x : varr2) cout << x << " "; cout << endl; return 0; } 你可能會想繼續閱讀… 容器(Containers) 函式(Functions) 迭代器(Iterators) Utility Library

STL 標準模板庫(Standard Template Library, STL)是提供常用資料結構模板的程式庫，其包含了類別(classes)、演算法(algorithms)與迭代器(iterators)。 STL 是通用的程式庫，所以所有的元素都是泛型的，可以點此瞭解更多模板(template)的內容。 STL 的四大組成 演算法(Algorithms) 容器(Containers) 函式(Functions) 迭代器(Iterators) 補充 Utility Library

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