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

題目敘述 題目難度: Easy 題目敘述: 這題給定一個linked list 的 head 要求，判斷這個linked list 當中是否存在 Cycle。 這裡的 Cycle 代表，你能夠透過持續跟隨next指標走訪list，而重複的訪問到曾經訪問過的節點，則代表有Cycle 另外，題目還說明了他們是用一個 pos 變數來去將一個linked list 讓Tail node接到特定index的節點上，這代表這題的cycle 只會從 tail node 往回接，而 pos 變數對我們而言不重要，因為它並不是這題能夠存取到的變數 解法一開始的想法我的想法是這題可以透過記錄節點是否有走訪過來判斷是否有 Cycle，因為這題會將Tail node 接回其他node，因此如果有Cycle 必定會有節點重複走訪，且無法抵達 NULL。而儲存方式比較快的應該是用 Hash Table ...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個 m x n 大小的字母網格 board 以及一個字串 word，如果在網格中存在 word 則回傳 true。 Word 可以由字母的相鄰Cell中組合而成，相鄰可以是水平相鄰或者是垂直相鄰。相同的Cell不可重複使用。 解法一開始的想法首先由於也是要嘗試多種不同組合，因此想法上還是會偏向 backtracking，**我的想法上覺得應該要先找出 word 中的第一個字是否存在於 board 之中，如果存在則可以先取得第一個字的座標 (在board上的位置)**，一旦有初始位置後，就可以去進行 backtracking嘗試看看各種鄰接組合。 組合方式可能會是上下左右，因此每次遞迴輸入時會有四種不同可能，分別是向左、向右、向上以及向下，而這個過程中應該也要確保沒有超出邊界。 而遞迴的中止條件，應該會是backtrac ...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個包含由數字 2-9 組成的連續字串 digits， 回傳所有可能的字母組合，回傳的組合不限順序。 這裡的字母可能對應到的就是題目給的電話號碼圖片，數字 1 跟 0 沒有對應的字母 解法一開始的想法提到 所有可能的組合數 這種問題就會想到 backtracking，由於題目中的電話號碼數字跟字母有對應關係，因此我的想法是，可以透過雜湊表來去保存這個mapping關係，接著再去進行組合。首先思考遞迴終止條件，遞迴終止條件就是已經窮盡給定的 digits 中的數字。 接著在每一層中，應該要去嘗試數字對應的每一種字母，要取出來放入字串變數中，而這裡還需要注意針對雜湊表的存取。取出後接著就是遞迴呼叫下一層，實現backtracking來窮盡各種組合。 我的解法123456789101112131415161718192021222 ...

題目敘述 題目難度: Medium 題目敘述: 給定 n 組括號，請產生所有可能的閉合括號的組合 反正就是沒有 (() 或者是 )() 類似這樣的組合 解法一開始的想法這題求組合的所有可能性，所以想法上一定還是 backtracking，但今天的問題會是要怎麼樣 控制括號能夠閉合，以 backtracking 的解題架構來看，首先可以思考退回條件會是一旦每個組合中的長度到達了 2 * n 因為 會是 n 組括號，另外每一層中在選一定要先選左括號再選右括號，因此需要判斷當前右括號數量是否小於左括號，如果小於就代表一定至少有一組括號還沒閉合完畢。 我的解法12345678910111213141516171819202122class Solution {public: vector<string> parentheseList; void gener ...

題目敘述 題目難度: Medium 題目敘述: 題目會給一個整數陣列叫做 candidates 和一個目標整數 target，回傳一系列candidates的unique組合，其中對於每種組合中數字的總和要等於 target，可以以任何順序回傳各種可能。 在這個問題中，每個candidates中的數字可以被選擇無限次。若至少有一個數字被選擇的次數不同，那麼兩個組合即被視為唯一的。Ex. [2,2,3] != [2,2,2,2,3]測試案例會保證在給定的輸入下，組成目標數字的唯一組合總數少於 150 個。 解法一開始的想法既然是組合問題，那就直接聯想到 Backtracking，另外由於這題與 77.Combinations 那篇 不同的是，這個沒有限制層數，因為題目也說了 candidates 中的數字可以被重複選擇無限多次，因此終止條件不會跟往常一樣是透過層數來做限制。 而可能 ...

前言在 PVE 系列文章的第一篇 有示範在PVE的控制台上面進行 migration，而這裡紀錄另一種可以進行 Migration 的方式 手動 Migration可以選擇先進入節點的 shell，接著進入 /etc/pve/nodes 目錄中，可以發現底下有相同cluster的所有節點 1234root@pve:/etc/pve/nodes# ls -ltotal 0drwxr-xr-x 2 root www-data 0 Sep 10 11:06 pvedrwxr-xr-x 2 root www-data 0 Sep 10 14:21 pve2 接著進入目標節點 pve2，會發現裏頭有許多目錄，這裡跟 migration 有關的目錄會是 lxc 以及 qemu-server 這取決與你要 migrate 的是容器還是VM，如果要mirgate 容器就將 lxc 底下的設定檔移到目標節點 ...

題目敘述 題目難度: medium 題目敘述: 給定兩個整數 n 和 k，求 [1,n] 範圍中，任意 k 個數字的所有組合可能，要用二維vector回傳。 其實數學意義就是要求 $C^{n}_{k} 的答案$ 解法一開始的想法一開始的大方向也是 backtracking，並且思考方想跟 46.Permutations 很像，骨幹一樣是一個 for 迴圈，迴圈代表每一層中要組合的數字，會去從 [1,N] 去進行組合，而由於數字不能重複，因此我們迴圈的初始值會給定一個變數 start，並且會在每次進入下一層時，去更新傳入的 start參數。如果抵達給定的層這裡也就是題目的 N，那就會退回，而這裡為了輸出最終結果，會將陣列添加到儲存最終結果的二維陣列中。 之後如同其他 backtracking 題目一樣，會回退，將原先占用陣列的值pop 出來，以便進行其他選擇。 我的解法123456 ...

題目敘述 題目難度: 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 題目的時候，通常可以使用遞迴回來實現，那最好還是要先了解遞迴的想法。遞迴的核心想法就是 「大問題拆成多個小問題，小問題也能按照相同方式切成更小的問題」、「除了最小的問題之外，每層的解決方式都一樣」 河內塔問題(Tower of Hanoi) 河內塔問題就是經典的遞迴問題，它的問題是，有三根柱子，並有 N 個圓盤套在最左邊柱子上面（上圖 N = 4)，現在我們要把它們全部移動到最右邊的柱子上，請問我們最少需要移動幾次？ 每次可選一個柱子，移動最上方的圓盤，一次只能一動一個 大的圓盤不可以疊在小的上面 這裡就需要 Follow 一下遞迴的思維，靠解決多個小問題來解決大問題。 這裡的大問題就是 要怎麼移動四個圓盤到最右邊要幾個步驟? 而小問題則是 移動三個圓盤要幾步? 這邊問題本質一樣，只是問題範圍縮小而已，這裡假設我們已經知道移動兩個圓 ...

前言上一篇文章中我們介紹了如何在 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，但如果主機板沒有支援 ...