排列問題 | Medium | LeetCode#46. Permutations
題目敘述
題目難度: Medium
題目敘述: 給定一個整數陣列 nums 其中不包含重複數字,找到所有數字排列後的可能情況。
輸入: nums = [1,2,3]輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]輸出結果為輸入陣列中元素的各種排列結果。
解法一開始的想法Permutations 其實就是經典的 backtracking 題目,也是典型的樹狀結構,在每一層都先選擇一個數字,並且透過遞迴進入下一層,而一但到達指定層數,就可想辦法 return,退回後原先占用在陣列的數字就可以 pop 出來的。但我按照這個想法時做的時候,起初的結果是有重複數字的,也就是 [1,1,1],[1,1,2] … [3,3,3] 像是這種的,後來才進行了修正。
我的解法12345678910111213141516171819202122 ...
刷題知識整理 | Backtracking & Recursive
遞迴在解 backtracking 題目的時候,通常可以使用遞迴回來實現,那最好還是要先了解遞迴的想法。遞迴的核心想法就是 「大問題拆成多個小問題,小問題也能按照相同方式切成更小的問題」、「除了最小的問題之外,每層的解決方式都一樣」
河內塔問題(Tower of Hanoi)
河內塔問題就是經典的遞迴問題,它的問題是,有三根柱子,並有 N 個圓盤套在最左邊柱子上面(上圖 N = 4),現在我們要把它們全部移動到最右邊的柱子上,請問我們最少需要移動幾次?
每次可選一個柱子,移動最上方的圓盤,一次只能一動一個
大的圓盤不可以疊在小的上面
這裡就需要 Follow 一下遞迴的思維,靠解決多個小問題來解決大問題。 這裡的大問題就是 要怎麼移動四個圓盤到最右邊要幾個步驟? 而小問題則是 移動三個圓盤要幾步?
這邊問題本質一樣,只是問題範圍縮小而已,這裡假設我們已經知道移動兩個圓 ...
基於 CPU 功耗來進行 PVE 虛擬機的 Live Migrations | PVE 系列-2
前言上一篇文章中我們介紹了如何在 Proxmox VE 中對虛擬機進行 Live Migrations,現在我們要加入條件來去對虛擬機進行 Migrations,由於我目前需求會是功耗,因此會需要知道在如何獲取 CPU 功耗的資訊。
獲取 CPU 功耗資訊通常可以透過幾種方式來獲取 CPU 或者是其他硬體的功耗,最簡單的方式就是透過 powerstat 來在 Linux/Unix 環境中查看 CPU 的功耗。 另外如果主機有 BMC和支援IPMI 的話,那就可以透過 ipmitool 去獲取主機的電力消耗資訊。
題外話: 其實 Proxmox VE 本身是有支援 IPMI watchdog 的,可以在 /etc/default/pve-ha-manager 裡面去取消註解,改成使用 IPMI watchdog,因為默認是使用作業系統層級的 softdog,但如果主機板沒有支援 ...
填充每個節點的右側指標 II| Medium | LeetCode#117. Populating Next Right Pointers in Each Node II
題目敘述
題目難度:Medium
題目敘述: 題目會給 Binary Tree 的節點,節點結構如下,除了 *left, *right pointer 之外,還多了一個 *next 指標,用於指向該層中右方的節點,而如果右方節點不存在,則 *next 指向 NULL
123456struct Node { int val; Node *left; Node *right; Node *next;}
上圖中的例子中,題目會依序給 Binary Tree 的節點 [1,2,3,4,5,null,7] 而輸出結果也如圖,節點 1 沒有右邊節點,所以它的 *next 指向 NULL。再來就是下一層,節點 2 的下一個是節點 3,而節點 3 沒有右邊節點,所以會是指向 NULL
123(1) -> NULL(2) -> (3) -> NULL(4) ...
實作 Proxmox VE VM 的 Live Migrations | PVE 系列-1
Proxmox VE 介紹Proxmox VE(PVE) 是一個開源的虛擬化環境,能夠同時支援基於 LXC (Linux Container) 的容器,抑或是基於Kernel 的VM,即為 KVM,也就是將 Linux Kernel 作為 Hypervisor 的虛擬化技術。
而 Proxmox 也透過介於 Host 與 Guest 的 QEMU 去處理 Guest 的硬體請求,將其轉譯給真正的硬體,搭配KVM 一起運作可帶來指令處理效能上的提升。因此可以以近乎本地環境的速度來去進行虛擬化。
實體節點設定Proxmox VE images 燒錄
這裡準備好 USB 將 Proxmox VE 的 iso image 放置其中,我選擇 Proxmox VE 7.4 ISO Installer
PVE Image 官網下載處
接著就是要準備節點,並且在個別主機上調整開機順序,進到 ...
二元樹的最近共同祖先 | Medium | LeetCode#236. Lowest Common Ancestor of a Binary Tree
題目敘述
題目難度: Medium
題目敘述: 給定一個 binary tree,請找到任兩節點 p 和 q 的 lowest common ancestor (LCA)
最近公同祖先(lowest common ancestor): 是指在節點 p 和 q 之間,二元樹 T 中最低的、同時擁有 p 和 q 作為後代的節點 (本題允許當前節點是自己的後代)
解法一開始的想法想法一樣會是 DFS,因為在正常實踐 DFS 的過程中,我們是透過遞迴函式呼叫來實現,Ancestor 一定會是 descendant 的 caller之一。因此朝著 DFS方向去想。另外沒必要把 Traversal全部跑完,只要能夠找到 p 與 q 即可。
我的解法123456789101112131415161718192021222324/** * Definition for a binary tree ...
從 Inorder 和 Postorder Traversal 建構二元樹 | Medium | LeetCode#106. Construct Binary Tree from Inorder and Postorder Traversal
題目敘述
題目難度: Medium
題目敘述: 給定兩個整數 inorder 和 postorder 分別代表對一個 binary tree 進行 inorder traversal 和 postorder traversal 的結果,請建構一棵二元樹,並回傳二元樹的 root。
解法一開始的想法這題算是 LeetCode 105 的延伸題目。
其實有想法很像:
Inorder 的第一個元素是 leftmost 元素
Preorder 的最後一個元素會是 root
因此每次迭代過程中,透過 postorder 中找到的 root 節點值,來去找到 inorder 中的 subTree 該怎麼切分左右子樹
我的解法1234567891011121314151617181920212223242526272829303132333435363738/** * Defin ...
BST 中第K小的元素 | Medium | LeetCode#230. Kth Smallest Element in a BST
題目敘述
題目難度:Medium
題目敘述:給定一個 Binary Search Tree 的 root,以及一個整數 k ,回傳第 $k^{th}$ 小的節點值
解法
這題是刷題到目前下來解最快的一題,從打開題目到最後 Accept 大概花 15 分鐘,其中包含 5 分鐘在local端手動寫測試
一開始的想法題目要求回傳 第 K 個最小的節點值,所以想法很簡單,首先 BST 的由左至右的大小排序跟你對樹進行 In-Order Traversal 的順序會一致,因此當你進行 In-Order Traversal 第一個拜訪的節點就會是最小值,接著拜訪到的就是 BST 中第二小的節點,依序下去…。 因此只要透過一個 counter 來計算現在是否第K個節點就好,如果找到就回傳節點值。
我的解法12345678910111213141516171819202122232425262728 ...
二元樹Z字形走訪 | Medium | LeetCode#103. Binary Tree Zigzag Level Order Traversal
題目敘述
題目難度:Medium
題目敘述:給定一個二元樹的 root ,回傳對這棵樹進行 Z 字走訪 (Zigzag Level Order Traversal)的結果
Zigzag Level Order Traversal 代表先從左走到右,下一層再從右走到左,每一層走訪方向交互替換
解法一開始的想法這題想法也很直觀,就BFS,然後宣告一個用來存放結果的 2D Vector,透過變數控制在每一層走訪的時候,按照順序或反向順序放入 vector 當中。
我的解法123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeN ...
Valid 的二元搜尋樹 | Medium| LeetCode#98. Validate Binary Search Tree
題目敘述
題目難度: Medium
題目敘述: 題目給定一個 Binary Tree 的 root ,我們需要確認這棵 Binary Tree 是否是 Binary Search Tree
一個 valid 的 Binary Search Tree(BST) 包含了:
對於任意節點,其 Left SubTree 的任意節點值一定小於當前節點值
對於任意節點,其節點值一定小於其 Right SubTree 的任意節點值
Left SubTree 和 Right SubTree 都要是 binary search tree
解法一開始的想法這題想法很簡單,這題的花費時間很少,首先可以知道的是: BST 從小到大走訪,其走訪順序會是對同一棵樹進行 inorder traversal。 所以只要能夠 在 Inorder 走訪過程中比較前一個節點值與當前節點值,看前一個節點是否比當前節 ...