Dimple在左耳聽風ARTS打卡（十七）
- 2019 年 12 月 26 日
- 筆記
所謂ARTS：每周至少做一個LeetCode的算法題；閱讀並點評至少一篇英文技術文章；學習至少一個技術技巧；分享一篇有觀點和思考的技術文章。（也就是Algorithm、Review、Tip、Share 簡稱ARTS）這是第十七期打卡。
小編文章的閱讀量不高，粉絲也不多，所以還是蠻在意讀者的感受的。昨天有讀者聯繫我，說我最近文章有點空，尷尬。上次前輩就告誡過我，說我有點走偏了，沒想到這麼快讀者就反饋了，狠狠的給我當頭一棒。
所以，接下來的日子，我肯定會時刻保持清醒，更多的專註於Java和Android相關的分享，適當的分享下前輩們覺得不錯的工具、文章、獨到的見解等等。讀者朋友們有什麼需求，有什麼想法，有什麼不爽的，歡迎過來找我吐槽，給我清醒的機會。
Algorithm LeetCode算法
合併二叉樹 (https://leetcode-cn.com/problems/merge-two-binary-trees/)
題目描述：給定兩個二叉樹，想像當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。
你需要將他們合併為一個新的二叉樹。合併的規則是如果兩個節點重疊，那麼將他們的值相加作為節點合併後的新值，否則不為NULL的節點將直接作為新二叉樹的節點。
示例 1：
輸入: Tree 1 Tree 2 1 5 / / 2 3 3 6 / / / 4 5 2 1 4 輸出: 合併後的樹: 6 / 5 9 / / 6 5 1 4
注意: 合併必須從兩個樹的根節點開始。
小編這次對選題改了下策略，從今天開始，會有目的性的進行選題。前幾次的選題，都是按順序而來，然後是挑選簡單的練習下意識。
直到我看了極客時間的《Android開發高手課》上關於Android面試的那節課，老師也提到練習算法是一個很重要的事情，可以對題目進行篩選，把自己認為重要的題先做。
我自己的性格本身就是想按部就班的，也是一根筋的表現，以後還得尋求變通。今天的選題，篩選了網站上的「熱題 HOT 100」，而且二叉樹也是熱點，就順勢寫一個唄。
當前題目上，是合併二叉樹，那很顯然，我們的思路就和描述一樣，同一個節點有兩個值則進行相加，否則取其一即可。具體的，就看我的解題吧，這個方式是比較好的。
public class MergeTrees { public static void main(String[] args) { TreeNode t1 = new TreeNode(1); t1.left = new TreeNode(2); t1.right = new TreeNode(3); t1.left.left = new TreeNode(4); t1.left.right = new TreeNode(5); TreeNode t2 = new TreeNode(5); t2.left = new TreeNode(3); t2.left.left = new TreeNode(2); t2.right = new TreeNode(6); t2.right.left = new TreeNode(1); t2.right.right = new TreeNode(4); TreeNode result = mergeTrees(t1, t2); } public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) return t2; if (t2 == null) return t1; t1.val += t2.val; t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); return t1; } }
當然啦，這個題目還有第二種解法，使用棧的方式來的。在Leetcode的英文官網，solution下可以看到動態的運行原理圖，以及相應的代碼和激烈的討論，大家可以去圍觀下哦。地址是：(https://leetcode.com/problems/merge-two-binary-trees/solution/)
public static TreeNode mergeTrees1(TreeNode t1, TreeNode t2) { if (t1 == null) return t2; Stack < TreeNode[] > stack = new Stack < > (); stack.push(new TreeNode[] {t1, t2}); while (!stack.isEmpty()) { TreeNode[] t = stack.pop(); if (t[0] == null || t[1] == null) { continue; } t[0].val += t[1].val; if (t[0].left == null) { t[0].left = t[1].left; } else { stack.push(new TreeNode[] {t[0].left, t[1].left}); } if (t[0].right == null) { t[0].right = t[1].right; } else { stack.push(new TreeNode[] {t[0].right, t[1].right}); } } return t1; }
Review 閱讀並點評至少一篇英文文章
How to improve the build speed of your Android projects (https://www.freecodecamp.org/news/how-to-improve-the-build-speed-of-your-android-projects-bd49029d8602/)
前段時間在掘金上關注了一個號主，叫「駐坑大使」，看到有好幾篇關於Android的翻譯，提起了我的興趣，上周的那篇翻譯，也是從他的資源里找到的。
這禮拜，又看到一篇是關於如何提升Android項目的構建速度的，我覺得也是有必要和大家分享下。
因為做Android開發的都知道，從早期的Eclipse開發，到現在的Android Studio，編譯速度一直是個問題。很多時候一個稍微比較大的項目，光編譯花費的時間就夠你泡一杯咖啡甚至還能喝上幾口。
在優化之前，我們可以先記錄下優化之前需要的時間，以此來證明這個優化是否真的對我們是有效的。關於如何記錄，文中的But first頁簽下已經告訴我們了哦。
緊接着就是三大步驟，如下：
Step #1: Update your tooling
Step #2: Update your configurations
Step #3: Gradle Properties
解釋起來分別是，更新你的開發工具，更新你的配置，更新Gradle，然後就可以去看看是不是溜的飛起啦。
還有這個網站也是我新發現的一個網站，感覺還蠻不錯的，感興趣的朋友可以再去看看其他的文章。
Tip 一個技術技巧
昨天在一個技術群里，聊了下微服務相關的話題，忽然想起前段時間學習微服務的時候，CAP定理讓我印象深刻，這裡同大家分享出來。
CAP定理
CAP定理是分佈式系統設計中最基礎，也是最為關鍵的理論。它指出，分佈式數據存儲不可能同事滿足以下三個條件。
- 一致性（Consistency）：每次讀取要麼獲得最近寫入的數據，要麼獲得一個錯誤
- 可用性（Availability）：每次請求都能獲得一個（非錯誤）響應，但不保證返回的是最新寫入的數據
- 分區容忍（Partition tolerance）：儘管任意數量的消息被節點間的網格丟失（或延遲），系統仍繼續運行
- CA（consistency + availability），這樣的系統關注一致性和可用性，它需要非常嚴格的全體一致性。比如「兩階段提交」。
- CP（consistency + partition tolerance），這樣的系統關注一致性和分區容忍性。塔關注的是系統里大多數人的一致性協議，比如：Paxos算法（Quorum類的算法）
- AP（availability + partition tolreance），這樣的系統關心可用性和分區容忍性。因此，這樣的系統不能達成一致性，需要給出數據衝突，給出數據衝突就需要維護數據版本。Dynamo就是這樣的系統。
