當你上 code 時，有 reviewer 看你的程式碼時，通常會用 meld 等軟體 review。當你的程式碼加了多餘的空格時，都會被這些程式碼 highlight，使得 reviewer 在查看你的程式碼時有一定的不便。
手動刪除空格 (Remove trailing spaces manually)
ctrl + alt + p，輸入 trail 你應該就可以看到相關快捷鍵。
自動刪除空格 (Remove trailing spaces automatically)
setting > 右上角的 open setting (JSON) > 加入以下這行。
"files.trimTrailingWhitespace": true
參考資料 :
1.remove-trailing-spaces-automatically-or-with-a-shortcut
最近一直寫 Leetcode，部落格也就荒廢許久，想說突破 200 題來分享一下心得。
Leetcode 上有很多問題是關於距離，這裡紀錄下一些有用的數學概念。
平均值 (mean)
平均值的歐幾里得距離最短 (4*4 + 4*4 < 1*1 + 7*7)
但相乘值最大 (4*4 > 1*7)
中位數 (median)
中位數的絕對偏差值最低 (跟其物件的距離之總和最短)
眾數 (mode)
mode minimizes distance for indicator function (理解不能)
這個我沒寫過類似的，寫過後我再更新。
參考資料 : 1.leetcode/discuss
不同於 Tree 的無方向、無環，DAG 則是有方向、無環。DAG 特性是不斷地前進，有時分流、有時合流，日常常見的 DAG 為族譜、水流以及課程擋修規則。
Topological Ordering
拿課程擋修規則為例，有必須先修的課程及後修的課程，將其完整排列出來視為 Topological Ordering。
// 課程 1 須先修 : None
// 課程 2 須先修 : 課程 1
// 課程 3 須先修 : 課程 1, 課程 2
// 課程 4 須先修 : None
//
// Gragh:
// 課程 1 -> 課程 2
// ↘ ↓
// 課程 4 課程 3
//
// Topological Ordering:
// 1) 1 2 3 4
// 2) 4 1 2 3
// 3) 1 4 2 3
// 4) 1 2 4 3
// 兩個都行，只要順序符合規則就好 (按這個例子，課程 4 的排序位置無關緊要)
Topological Sort ( Kahn's Algorithm )
排序時，首先要找到第一個點 (課程 1 或課程 4)。第一個點有一個特別之處，就是沒有人指向他。找出來該第一點後，把其指向的連接也跟著去掉。使下一次課程 2 變為第一個點。以此排序。
// Gragh:
// 課程 2
// ↓
// 課程 4 課程 3
Code
題目之範例解答
bool canFinish (int numCourses, vector<vector<int>>& prerequisites) {
// Kahn's Algorithm
// http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
// adj 紀錄 node 連出去的所有 nodes
// ref 紀錄 node 被連的次數
vector<vector<int>> adj(numCourses, vector<int>());
vector<int> ref(numCourses, 0);
// init
for (auto&v : prerequisites) {
++ref[v[0]];
adj[v[1]].push_back(v[0]);
}
// Every loop 都可以找到一個 first node, 需要找出 numCourses 個
for (int i = 0; i < numCourses; ++i) {
// 一定有 node 的被連的次數為 0, 是為 first node
// 若所有 node 被連次數都 > 0, 代表有 cycle
int head = 0;
while (head < numCourses && ref[head] != 0) ++head;
if (head == numCourses) return false;
// 找過的 first node 要刪除, 設為 -1
// 把這次的 first node 所連出去 nodes 的 被連次數(ref) 減一
ref[head] = -1;
for (auto & n : adj[head]) --ref[n];
}
return true;
}
參考資料 :
1.leetcode-problem-course-schedule
2.http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
最近一直寫 Leetcode，部落格也就荒廢許久，想說突破 200 題來分享一下心得。
Leetcode 上有很多問題是關於距離，這裡紀錄下一些有用的數學概念。
平均值 (mean)
平均值的歐幾里得距離最短 (4*4 + 4*4 < 1*1 + 7*7)
但相乘值最大 (4*4 > 1*7)
中位數 (median)
中位數的絕對偏差值最低 (跟其物件的距離之總和最短)
眾數 (mode)
mode minimizes distance for indicator function (理解不能)
這個我沒寫過類似的，寫過後我再更新。
參考資料 : 1.leetcode/discuss
主要用來找區間最大值或區間總和。由於我是為了這題所以以區間總和做介紹。下面陣列是應對區間總和，每個 node 紀錄的有起始點, 結束點及區間總和，EXAMPLE: [0,4] 代表 index 0 ~ 4 的總和，其總和為 10，[0,0] 代表 index 0~0 也就是 nums[0] 的本身值。至於樹為什麼長這樣跟 Build tree 有關。
// nums:[-1, 4, 2, 0, 5]
//
// Segment Tree for the Above Array:
//
// 10 [0,4]
// / \
// 5 5 [0,2] [3,4]
// / \ / \
// 3 2 0 5 [0,1] [2,2] [3,3] [4,4]
// / \
// -1 4 [0,0] [1,1]
Build Tree
這邊我用 c++ 概略作介紹。基本上是 top-down 的 build 法，時間複雜度為 O(n)。
// Node 資料結構
class segTreeNode {
public:
int begin, end, sum;
segTreeNode * left = NULL;
segTreeNode * right = NULL;
segTreeNode(int s, int e, int m):begin(s), end(e), sum(m) {}
};
// Build
segTreeNode* buildSegTree(int begin, int end, vector& nums) {
// 若 begin = end，代表是 leaf。
if (begin == end) {
auto node = new segTreeNode(begin, begin, nums[begin]);
return node;
}
// 分割
int mid = (begin + end) / 2;
auto left = buildSegTree(begin, mid, nums);
auto right = buildSegTree(mid+1, end, nums);
auto node = new segTreeNode(begin, end, left->sum + right->sum);
node->left = left;
node->right = right;
return node;
}
Update tree
時間複雜度為 O(log n)。
// Update
void updateSegTree(segTreeNode* node, int index, int val) {
// 若是該 index 的 leaf。則更新其 sum
if (node->begin == index && node->end == index) {
node->sum = val;
return;
}
// 若是中間 node 則分割往下繼續找
int mid = (node->begin + node->end) / 2;
if (index > mid)
updateSegTree(node->right, index, val);
else
updateSegTree(node->left, index, val);
// 最後更新 node's sum
node->sum = node->left->sum + node->right->sum;
}
Sum
時間複雜度為 O(log n + k)。
// Sum
int sumSegTree(segTreeNode* node, int left, int right) {
// 若完美覆蓋區間，直接回傳。
if (node->begin == left && node->end == right)
return node->sum;
int mid = (node->begin + node->end) / 2;
// 要求區間完全在左邊
if (right <= mid)
return sumSegTree(node->left, left, right);
// 要求區間完全在右邊
else if (left > mid)
return sumSegTree(node->right, left, right);
// 兩邊都有
else
return sumSegTree(node->left, left, mid) +
sumSegTree(node->right, mid+1, right);
}
參考資料 :
1.leetcode/hg3994 answer
2.youtube 中文講解
Exceptions 是程式在 run-time 遇到的異常，比如與資料庫的連結斷開或遇到其他程式異想不到的 input。Exception handling 基本上就是當程式無法解決問題或者無法繼續執行時發出警告，或者更進一步根據情況處理 exception。
Exception handling 由 detecting, handling parts of a program 所組成
throw expressions
當 detecting part 表示遭遇無法處理的情況
try blocks
handling part 用來處理 exception。程式碼一開始會有一個 try block 隨後跟著一個或以上的 catch clauses。
exception classes
用來傳遞 information about what happened between a throw and an associated catch.
通常會在 detecting part 發生 exception 時 throw Expression，這麼做原因是有時你不能保證你的程式一定是跟 User 互動的那一個，throw Expression 效果就比你回傳一個錯誤值好用得多。
// Normal version
int throwTest(int num1, int num2) {
if (num1 == num2) {
cout << "Same." << endl;
return 0;
} else {
cerr << "Not the same." << endl;
return -1;
}
}
// throw Expression
void throwTest(int num1, int num2) {
if (num1 != num2)
throw runtime_error("Not the same.");
cout << "Same." << endl;
}
基於 C 風格的錯誤處理，在回傳值代表發生錯誤時予以處理。相比之下 throw 就相對靈活，但也會有終止程式的代價。try catch 的 block 就適合在此情況使用。讓程式有 exception handler。
try {
program-statements
} catch (exception-declaration) {
handler-statements
} catch (exception-declaration) {
handler-statements
} // . . .
正如上面的 try block 示億程式碼所示，程式必須先宣告 exception 的種類才能近一步去做 handle，這裡紀錄 C++ standard library \裡的 exception table。
exception // The most general kind of problem.
// Runtime errors
runtime_error // Problem that can be detected at the run-time.
range_error // Result generated outside the range of value that are meaningful.
overflow_error // Computation that overflow.
underflow_error // Computation that underflow.
// Logic errors
logic_error // Error in the logic of the program.
domain_error // Argument for which no result exists.
invalid_argument // Inappropriate argument.
length_error // Attempt to create an object larger than the maximum size for that type.
out_of_range // Use a value outside the valid range.
