ARTS Week 22
Algorithm
本周的 LeetCode 題目為 297. 二叉樹的序列化與反序列化
序列化是將一個數據結構或者對象轉換為連續的比特位的操作，進而可以將轉換後的數據存儲在一個文件或者記憶體中，同時也可以通過網路傳輸到另一個電腦環境，採取相反方式重構得到原數據。
請設計一個演算法來實現二叉樹的序列化與反序列化。這裡不限定你的序列 / 反序列化演算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字元串並且將這個字元串反序列化為原始的樹結構。
提示: 輸入輸出格式與 LeetCode 目前使用的方式一致，詳情請參閱 LeetCode 序列化二叉樹的格式。你並非必須採取這種方式，你也可以採用其他的方法解決這個問題。
1
/ \
2 3
/ \
4 5
輸入：root = [1,2,3,null,null,4,5]
輸出：[1,2,3,null,null,4,5]
二叉樹的序列化後的結果採用先序遍歷的方式。
- 在進行序列化時，先判斷當前節點是否為空，若為空則記錄
null，若不為空，則先將根的值和分隔符（’,’）添加，再依次遞歸處理當前節點的左子樹、右子樹。 - 在進行反序列化時，先判斷當前是否為
null，若為null則返回null，若不為null，則先以當前值構造出根節點，移除第一個元素，再依次構建該節點的左子樹、右子樹。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
realSerialize(root, sb);
return sb.toString();
}
public void realSerialize(TreeNode root, StringBuilder sb) {
if (root != null) {
sb.append(root.val);
sb.append(",");
realSerialize(root.left, sb);
realSerialize(root.right, sb);
} else {
sb.append("null,");
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] dataArr = data.split(",");
List<String> dataList = new ArrayList<>(Arrays.asList(dataArr));
// dataList = Arrays.asList(dataArr);
TreeNode ans = realDeserialize(dataList);
return ans;
}
public TreeNode realDeserialize(List<String> dataList) {
if (dataList.get(0).equals("null")) {
dataList.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
root.left = realDeserialize(dataList);
root.right = realDeserialize(dataList);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
Review
本周 Review 的英文文章為：如何在 git 中使用 squash 和 rebase
作者詳細介紹了使用 squash 和 rebase 的流程，首先你需要備份一個分支用來嘗試：
git checkout my-branch-name
git branch backup-my-branch-name
git push origin backup-my-branch-name
而後查看日誌找到不屬於你的最新提交的 id，別忘了複製它
git log
而後開始 rebase 操作，將 -i 後面的內容替換為你剛剛找到的提交 id
git rebase -i the-commit-id-you-looked-up-goes-here
通過在除第一個提交之外的所有提交前面放置「s」而不是「pick」來標記要壓縮（squash）的提交。而後保存並關閉，等待彈出新的文本編輯器提示來輸入你的 commit 資訊。
使用 git status 來檢查是否有任何問題。
接下來作者將所有提交都合併到 main 分支中，先確保本地的 main 分支是最新的
git checkout main
git pull origin main
接下來進行 rebase 操作，先切換分支再 rebase
git checkout my-branch-name
git rebase main
修複發生的 git 衝突後，暫存如下的文件：
git add some-file.js
而後再繼續完成 rebase：
git rebase --continue
最後提交 commit，請先檢查分支是你的分支！
git push --force-with-lease origin my-branch-name
如果途中出現了問題，你還有一個備份分支可以用來恢復，或者使用 git rebase --abort 來中止正在進行的 rebase。
為什麼要在 rebase 前進行 squash？在使用 squash 壓縮提交後，rebase 需要解決的衝突至多需要一次，而當你的公司/組織/項目要求你不得壓縮時，那麼就不要使用 squash。
Tip
使用宏定義的注意事項，宏定義是直接替換，並不是保存計算的結果。示例程式碼如下：
#include <stdio.h>
#define NUM_0 4
#define NUM_1 5-1
#define NUM_2 (5-1)
int main()
{
printf("%d\n", 5 % NUM_0); // 5 % NUM_1 = 5 % 4 = 1
printf("%d\n", 5 % NUM_1); // 5 % NUM_1 = 5 % 5-1 = 0 - 1 = -1
printf("%d\n", 5 % NUM_2); // 5 % NUM_1 = 5 % (5-1) = 5 % 4 = 1
return 0;
}
程式的運行結果如下：
$ clang test.c
$ ./a.out
1
-1
1
Share
未來幾周內打算抽空認真地、系統性地回顧下基本的數據結構、演算法，為下一步做 LeetCode 題目做準備。
