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

題目敘述 題目難度: Easy 題目描述: 給定字串 pattern 以及 字串 s，檢查 s 是否遵循相同模式 題目有說明這裡 相同模式 的意思: pattern 中的任一字元與 s 中的非空字串完全匹配的 1對1映射關係，具體來說規則如下: 在 pattern 中的每個字母，都有明確的對應到 s 中的 unique 字串 在 s 中的 unique 字串，明確對應到 pattern 中的一個字母 沒有兩個字母映射到同一個單詞，也沒有兩個單詞映射到同一個字母 解法一開始的想法這裡想法很單純就是透過 Hash Table 來去建立並儲存映射關係。而在建立過程中可以去檢查當前的字母和對應字串是否已經存在映射關係於 hash table 中，如果有救回傳 false，如果整個 hash table都建立好後都沒有重複的映射關係那就回傳 true。 我的解法12345678910 ...

題目敘述 題目難度: Medium 題目敘述：給定一個整數陣列 nums， 回傳所有可能的子集，回傳的子集不能重複，但可以任意順序排序 這題是 78.Subsets 的延伸題型，可以看我這一篇解法，但是這題不同的是，對於 nums 陣列中 [2] 是不等於 [2,2] 的，但 [1,2] 是等於 [2,1] 的，也就是説對於個別子集來說，若相同元素但元素數量不同則看成不同子集 解法一開始的想法我的想法就跟上一題差不多，只是想說在添加到回傳陣列時，額外進行檢查，踢除重複的子集。 我的解法123456789101112131415161718192021222324252627282930class Solution {public: vector<vector<int>> result; void subsetHelper(vector& ...

題目敘述 題目難度: Medium 題目敘述: 給定一個具有不重複元素的整數陣列 nums，回傳所有可能的子集合 子集會包含空集合，另外，若子集中的元素相同但順序不同，則視為相同子集。 123Ex. nums = {1,2,3}[1,2] = [2,1][1,3,2] = [3,1,2] 解法一開始的想法子集合問題也是典型的 backtracking 問題，它包含了在每個數字中選與不選，因此終止條件會是目前選擇的深度到達題目所給的長度上限就停止，而在每一層中要做的事就是選跟不選，首先是不選，那就會需要直接往往下一層去，到下一層在進行選以及不選，直到到達長度限制。 假設題目是 nums={1,2} 則他的樹狀結構會如下： 123456 [] / \ [] [1] / \ / ...

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

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

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

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