二元樹各層的平均值 | Easy | LeetCode#637. Average of Levels in Binary Tree
題目敘述 題目難度: Easy 題目敘述: 題目給定一個 Binary Tree 的 root，求各層level 節點值的平均值，結果以陣列回傳 解法一開始的想法這題與之前碰過的題目很像，**首先想法一樣會是先BFS (Level-Order Traversal)**。 如果能夠在各層加入某個變數，在各層結束時加入回傳陣列即可。 我的解法這是我一開始的解法，但這是錯的 123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x),...
對稱的二元樹 | Easy | LeetCode#101. Symmetric Tree
題目敘述 題目難度: Easy 題目敘述: 給定一個二元樹的 root，題目要我們檢查該二元樹是否是對稱的。 解法一開始的想法我一開始的想法就錯了，我一開始認為只要 Inorder Traversal 後的結果，只要反向過來也一樣那就是對稱的了 所以我一開始的解法是錯的: 123456789101112131415161718192021vector<int> result_inorder;void BT::inorder(TreeNode* node){ if(node==NULL) return; cout << node->val << " "; result_inorder.push_back(node->val); inorder(node->left); inorder(node->right);};bool BT::isSymmetric(TreeNode* root){ bool result = fals...
二元樹 Level Order Traversal | Medium | LeetCode#102. Binary Tree Level Order Traversal
題目敘述 題目難度: Medium 題目敘述: 給定一個 Binary Tree 的 root，求 Level Order Traversal 的結果 (須將節點值存在一個二維list中) 解法一開始的想法就是先實踐經典的 Level Order Traversal，然後再嘗試存進 vector<vector<int>> result 返回。但我的想法在我剛實現完標準的 level_order_traversal 後就卡住了，由於我是用 queue 來去做實現，而每一次 push 進 queue後的節點會為同一層 (因為上一層已經被pop出來了) ，因此就可以處理在每一層的時候將節點值添加進 result 中，但我高估了我對 vector 的熟悉程度… 我的解法123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for a binary tree node. * struct TreeNode { *...
相同的二元樹 | Easy | LeetCode#100. Same Tree
題目敘述 題目難度: Easy 題目敘述: 給定兩個 Binary Tree 的 root，分別是 p 與 q，請寫一個函式檢查他們是否相同 相同的定義: 結構一樣，並且節點值一樣 解法一開始的想法我的想法一樣是遞迴，首先Traverse 到 Leaf，之後檢查節點值，如果不一樣就直接回傳 false，我們可以用一個變數值，將遞迴回傳的結果保存起來，再做為函式的返回值 我的解法12345678910111213141516171819202122232425262728/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullpt...
反轉二元樹 | Easy | LeetCode#226. Invert Binary Tree
題目敘述 題目難度: Easy 題目敘述: 給定一個 Binary Tree 的root，反轉他以後，回傳它的 root 解法一開始的想法 題目敘述很簡短，但基本上就是除了root以外，左葉子樹的成員都對調 但學會了上一題遞迴的概念後，這題幾乎是秒解，但還是有考慮不周到的地方 我一開始的想法，就是一樣透過遞迴的方式，一開始就 traverse 到樹葉，碰到樹葉後，再將他們的左右child進行對調，之後一路fuction return 回去，然後回傳一開始原先的root即可 我一開始的思路會是下面這樣 123456789101112131415161718TreeNode *BT::invertTree(TreeNode* root){ TreeNode *tmp = 0; TreeNode *current = root; if (root == nullptr) { return nullptr; } if(current->left != NULL && curr...
二元樹的最大深度 | Easy | LeetCode#104. Maximum Depth of Binary Tree
題目敘述 題目難度: Easy 題目敘述: 題目給定一個Binary Tree 的 Root，要求這棵二元樹的最大深度 最大深度即 root 到樹葉的最遠距離 解法一開始的想法一開始的想法只有停留在 Traversal 本身，所以寫了 Inorder, Preorder, Postorder 甚至是 Level-order，都還是沒有太多想法… 這次是看了提示後才寫出來，並且了解到我自己對Recursive 的不熟練 我的解法123456789101112131415161718192021/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), ri...
從並行計算到聯邦式學習 | 學習筆記
甚麼是並行計算?現在的深度神經網路模型具有大量的參數，模型大也意味著計算量變大 Big Model + Big Data -> Huge computation cost ! 單一GPU進行一年的計算量，可以透過20 個 GPU 一次進行計算來實現，來減少花費的時間成本 Linear Predictor未完待續 聯邦式學習最好先具備並行計算和分散式機器學習的基礎。可以參考下面這系列影片:https://www.youtube.com/watch?v=gVcnOe6_c6Q&t=124s 背景 問題背景: Google 想要透過使用者行動裝置上的資料來訓練模型。 可能的解決辦法: 蒐集使用者資料，上傳到某個集中式學習平台去訓練模型 面臨的挑戰: 使用者拒絕上傳資料，尤其是機敏資料到 Google 的伺服器 這樣的問題情境也發生在個人隱私保護很嚴格的歐美企業或是醫療環境中 分散式學習 以及 聯邦學習 一次迭代的過程: worker node 向 parameter 索取parameter server 回傳 parameter worker n...
刷題必會知識 | 樹 (Tree) | 進階實作篇 | LeetCode 筆記
In-Order Traversal by Parent Field在前一篇介紹 Tree 的文章 中應該有發現，我們在實作 Binary Tree Node 的時候有宣告一個 TreeNode *parent 指標，但卻沒有使用。 我們在實踐 Inorder Traversal 也可以透過 Parent Field來去進行，若要善用 *parent 進行 Traversal 需要提及兩個重要函式: InorderSuccessor() : 以 inorder 順序尋找 (LVR) 進行 Traversal 的 下一個 node InorderPredecessor(): 以 inorder 順序尋找 (LVR) 進行 Traversal 的 前一個 node 這裡提到的概念會與之後的 BST(Binary Search Tree) 有關聯 在實作這兩個函式來實踐 Inorder Traversal 之間還有幾項前置作業必須先完成: 在 main() 中將不同節點的 *parent 之間串接起來 在 class BinartTree 中定義六個成員函式 123456...
刷題必會知識 | 樹 (Tree) | 基礎篇 | LeetCode 筆記
甚麼是 Tree? Tree 是一種常見的資料結構，直觀上來看樹狀結構代表階層式結構，像是族譜或是不同語言，語系的直系表就很常用樹來表示。 基本介紹 節點(Node): 樹的基本單位 根(Root): 樹狀結構的初始節點 分支(Branch): 節點與節點之間的分支 子節點(child): Root以外的節點 葉子節點(leaf): 沒有連接到其他子節點的節點，即樹狀結構的末端節點 樹的定義Tree的定義: 由一個或是數個節點組成的有限集合 並且 存在一個特定節點為Root 其餘節點可以分割成 $n >= 0$ 個沒有交集的(disjoint)集合 $T_{1},T_{2},…,T_{n}$ 為此Root的子樹(subtree) 這是一個遞迴的定義，對於上面圖中的節點A(Root)，有兩個子樹，其樹根分別是節點B和節點C，樹中的每一個節點都是某個子樹的root，例如節點C 就包含了兩個子樹，它們的root分別是節點E 與節點F，而節點E與F為兩個沒有子樹的樹的樹根 A的子樹: $T_{1}(B,D)$, $T_{2}(C,E,F)$ B的子樹: ...
使用Stack來實現Queue | Easy | LeetCode#232. Implement Queue using Stacks
題目敘述 題目難度: Easy 題目敘述: 這題要求透過兩個 Stack 來實現一個Queue具有的基本操作，像是 push, peek, pop 以及 empty 題目也有提醒只可以使用標準 Stack 操作來實現 You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid. 解法一開始的想法這題跟 225. Implement Stack using Queues 其實是很類似的: Push 操作可以直接使用 <stack> 中的 push() STL 進行操作，重點會是實現 pop() 跟 peak()，由於Queue會是 FIFO，因此先進去Queue的會先出來，因此我們用Stack實作的時候等同於要優先將Stack的底部元素pop出來，這時候就需要第二個Stack進行暫存。 因此每當我們需要Pop時，都必須將最底部元素以外的資料...
