Kevin Liu's 部落格 || Technical || Travel

題目敘述 題目難度: Easy 題目敘述: 題目要求給定一個 Complete Binary Tree 的 root，需要計算 Tree 中的所有節點 根據維基百科定義，在一顆二元樹中，若除最後一層外的其餘層都是滿的，並且最後一層要麼是滿的，要麼在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。深度為k的完全二元樹，至少有 $\displaystyle 2^{\begin{aligned}k-1\end{aligned}}$ 個節點，至多有 $\displaystyle 2^{\begin{aligned}k\end{aligned}}-1$　個節點。 最後題目有個要求是，請設計一套演算法其時間複雜度小於 $O(n)$ 解法一開始的想法這題我一開始的想法其實都是 $O(N)$ 的做法 (各種 Traversal 算節點)，到後面是想說， ...

題目敘述 題目難度: Easy 題目敘述: 給定一個二元樹的 root 以及一個整數 targetSum，若從 root 到 任意leaf 之間節點值的加總等於 targetSum 則回傳 true 解法一開始的想法 這題一開始的想法就是用 DFS，去找到 root，途中運用變數來儲存節點值，邊traverse 邊累加節點值，走到leaf就能夠知道是否等於 targetSum 錯誤寫法1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right ...

題目敘述 題目難度: Medium 題目敘述: 給兩個整數陣列 preorder 以及 inorder， preorder 存放一棵二元樹進行 Pre-Order Traversal 的結果，inorder 存放相同二元樹進行 In-Order Traversal 的結果，題目要求透過這兩個陣列來建構出原本的Binary Tree，並回傳 root 節點。 解法一開始的想法這次的題目卡了很久，主要流程有嘗試寫下想法，但不知道該如何用遞迴去實作。 字有點醜，請見諒XD 首先第一個想法就是，Preorder Traversal 後的第一個元素必定會是Root，而再來就是 Inorder Traversal 後的第一個元素會是整棵樹的 leftmost node，也就是最左邊的節點，所以如果能夠迭題目給的 preorder list，從 Root 到 leftmost node 之 ...

題目敘述 題目難度: Easy 題目敘述: 題目給定一個 Binary Tree 的 root，求各層level 節點值的平均值，結果以陣列回傳 解法一開始的想法這題與之前碰過的題目很像，**首先想法一樣會是先BFS (Level-Order Traversal)**。 如果能夠在各層加入某個變數，在各層結束時加入回傳陣列即可。 我的解法這是我一開始的解法，但這是錯的 123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * ...

題目敘述 題目難度: 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); ...

題目敘述 題目難度: Medium 題目敘述: 給定一個 Binary Tree 的 root，求 Level Order Traversal 的結果 (須將節點值存在一個二維list中) 解法一開始的想法就是先實踐經典的 Level Order Traversal，然後再嘗試存進 vector<vector<int>> result 返回。但我的想法在我剛實現完標準的 level_order_traversal 後就卡住了，由於我是用 queue 來去做實現，而每一次 push 進 queue後的節點會為同一層 (因為上一層已經被pop出來了) ，因此就可以處理在每一層的時候將節點值添加進 result 中，但我高估了我對 vector 的熟悉程度… 我的解法123456789101112131415161718192021222324252627282930 ...

題目敘述 題目難度: 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( ...

題目敘述 題目難度: Easy 題目敘述: 給定一個 Binary Tree 的root，反轉他以後，回傳它的 root 解法一開始的想法 題目敘述很簡短，但基本上就是除了root以外，左葉子樹的成員都對調 但學會了上一題遞迴的概念後，這題幾乎是秒解，但還是有考慮不周到的地方 我一開始的想法，就是一樣透過遞迴的方式，一開始就 traverse 到樹葉，碰到樹葉後，再將他們的左右child進行對調，之後一路fuction return 回去，然後回傳一開始原先的root即可 我一開始的思路會是下面這樣 123456789101112131415161718TreeNode *BT::invertTree(TreeNode* root){ TreeNode *tmp = 0; TreeNode *current = root; if (root == nu ...

題目敘述 題目難度: 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 ...

甚麼是並行計算?現在的深度神經網路模型具有大量的參數，模型大也意味著計算量變大 Big Model + Big Data -> Huge computation cost ! 單一GPU進行一年的計算量，可以透過20 個 GPU 一次進行計算來實現，來減少花費的時間成本 Linear Predictor未完待續 聯邦式學習最好先具備並行計算和分散式機器學習的基礎。可以參考下面這系列影片:https://www.youtube.com/watch?v=gVcnOe6_c6Q&t=124s 背景 問題背景: Google 想要透過使用者行動裝置上的資料來訓練模型。 可能的解決辦法: 蒐集使用者資料，上傳到某個集中式學習平台去訓練模型 面臨的挑戰: 使用者拒絕上傳資料，尤其是機敏資料到 Google 的伺服器 這樣的問題情境也發生在個人隱私保護很嚴格的歐美企 ...