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

題目敘述 題目難度： Hard 題目描述： N-Queens 其實就是有名的八皇后問題，將 n 個皇后放到一個大小為 n x n 的棋盤，使得任何一個皇后都無法直接吃掉其他的皇后，題目要求輸入 n 求所有可能的棋盤組合，答案的可以是任意順序。每個解答中都需要能夠呈現皇后的擺放位置，題目中以 'Q' 代表皇后，而 '.' 代表空位。 這裡可以看八皇后問題的介紹：八皇后問題 補充：在西洋棋中，皇后可以走直的、橫的和協的，因此如果皇后的的位置如下，則以它為中心的十字及對角都不能走，都可能會被攻擊 1234| . | $ | . | $ || $ | $ | $ | . || $ | Q | $ | $ || $ | $ | $ | . | 解法一開始的想法首先這個問題一樣是要窮盡各種可能的走法組合，因此想法一樣會是朝 backtracking 想。首先對於 backtracking 的遞迴終止條件，首先題目給的棋盤會是二維的向量 vector<vector<string>>因此我們在每一層中會去窮盡所有可能的排法，一定...

題目敘述 題目難度：Hard 題目敘述： 題目給定你一個 Binary Tree 的 root，求這棵二元樹中的所有路徑中，最大路徑和 這裡二元樹的路徑的代表的是 節點序列，序列由每個由邊連接的相鄰節點組成。一個節點最多只能在序列中出現一次。請注意，該路徑不需要經過Root節點 解法 這是第一次解 Hard，真的花比較久的時間，但也學習到很多 一開始的想法我一開始的想法是有問題的，但還是紀錄一下這個錯誤思路，我一開始想得太簡單了，以為就先把所有二元樹的節點DFS 走訪一遍，就能夠得到一個節點順序，接著就是 backtracking 中的子集問題，在序列中找子集元素和最大的組合就是答案。 但這有一個缺陷，那就是DFS(inorder)走訪過程的順序不滿足題目敘述的節點序列 像是下面這個例子，經過 inorder 走訪過後的順序會是 -8, 10, 20, -5, -10 那這樣後面就可能以為 10 跟 20 會是相鄰的，且最大的就輸出 30，但實際情況就是他們之間根本沒有邊相連。 因此這樣的做法會是錯的。 所以做法其實也算是 DFS 但不會是傳統意義上的 ba...

題目敘述 題目難度: Easy 題目敘述: 題目給定兩個字串 ransomNote 以及 magazine ，若 ransomNote 可以由 magazine 中的字母組成，則回傳 ture 否則回傳 false 注意題目給的 Example2，magazine中個別出現字母的數量也是有意義的，如果只有一個 a 也無法組成 ransomNote 中的兩個 a 解法一開始的想法這題的想法就是將 magazine 中的字母丟入 Hash Table 然後，迭代查看 ransomNote 中的字母有無出現在 magazine 有的話就必須將 HashTable　中的對應字母移除或減少數量，而在迴圈中如果發現沒有的話就直接回傳 false，迴圈結束就代表完美匹配，就回傳 true 我的解法12345678910111213141516class Solution {public: bool canConstruct(string ransomNote, string magazine){ unordered_map<char, in...

題目敘述 題目難度: 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 來去實現。 我的解法- Hash Table123456789101112131415161718192021222324/** * Definition for singly-linked l...

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

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

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

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

前言在 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 底下的設定檔移到目標節點的相同路徑底下，例如 /etc/pve/nodes/pve/lxc/。同理要移植 VM 也是，將 qemu-server 底下的設定檔移動到 /etc/pve/nodes/pve/qemu-se...

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