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

題目敘述 題目難度： Medium 題目描述： 有個大小 m x n 的長方形島嶼，它的邊界被太平洋與大西洋包圍。與太平洋交界的會是島嶼的上方以及左側邊緣，與大西洋交界的會是島嶼的下方和右側邊緣。島嶼被切分成許多網格單元，可以視為一個 m x n 大小的矩陣 heights，其中 heights[r][c] 代表座標 (r,c) 位置的海拔高度。 島上很常下雨， 只要當前單元格的海拔高度大於或等於其上下左右單元格的海拔高度，則雨水可以自由流向他的上下左右單元格。 雨水可以透過相鄰單元格一路流到海洋中。 題目要求回傳一個 2D 矩陣 result， 其中 result[i] = [r_i, c_i] 代表雨水可以從座標 (r_i, c_i) 同時流到太平洋與大西洋。 解法一開始的想法一開始覺得這題一樣會是 connected components 只是 connected 的條件變成只 ...

題目敘述 題目難度： Medium 題目描述： 題目要求設計一套結構能夠滿足 [LRU(Least Recently Used) Cache])(https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU) 題目要求實踐 LRUCache class： LRUCache(capacity): 使用 capacity 初始化 LRUCache 大小 int get(int key): 如果 key 存在，則返回對應的值，若不存在則返回 -1 void put(int key, int value): 如果 key 存在，則更新它的值，否則添加 key-value pair 到 cache。若 key 的數量車超出 capacity 大小，則逐出最近最少使用的Key 解法一開始的想法這題因為很偏系統設計，所以剛接觸的時 ...

題目敘述 題目難度： Medium 題目描述： 給定一個 m x n 大小的 board，包含兩種字母 X 或者 O，目的是捕捉被包圍的區域： Connected： 一個格子可以與相鄰的格子（水平或垂直）相連Region： 通過連接每個 O 格子來形成一個區域(Region)Surround： 如果一個區域的所有 O 格子都能被 X 格子連接，並且該區域中的 O 格子不在矩陣的邊緣上，則該區域被視為被包圍 題目要捕捉被包圍的區域， 將原始矩陣中所有被包圍的 O 替換為 X。 此操作應直接在原始矩陣上進行，無需返回任何值。 解法一開始的想法這題我一開始的想法有點偏掉，但這題的意思就是： 找出被包圍 Region 並將 Region 中的 O 換成 X 如果 Region 有接到矩陣邊緣，則不替換成 X 這樣依舊會需要先透過 DFS 或者是 BFS 來先去走訪 connect ...

題目敘述 題目難度： Medium 題目描述： 給定一個 9 x 9 大小的數獨 board 請確認該數獨是否是有效的。 只有當被填入數字滿足下面條件，數獨才會是有效的:(1) 每一列只包含非重複的數字 1-9(2) 每一行只包含非重複的數字 1-9(3) 共9個 3 x 3 的子方格, 每個子方格中的數字 1-9 都不重複 解法一開始的想法想法就偏向暴力解，首先就是要迭代 board 中每一列，看數字是否重複，這時可以用一個 unordered_set 去儲存數字，並在每一格檢查數字是否重複，如果重複就回傳 false，接著迭代每一行檢查是否重複。每次換行換列 unordered_set 都要清空為的是保存新的一行/列的數字。 最後就是需要迭代 9 個 3*3 大小的子方格，如果重複就回傳 false 函數最後代表檢查完畢，回傳 true。 我的解法12345678 ...

題目敘述 題目難度： Medium 題目描述： 給定一個 m x n 大小的矩陣叫做 grid ，其中每一格可能會這三種值其中一種： (1) 0 代表那格是空的 (2) 1 代表新鮮橘子 (2) 2 代表腐爛橘子。每分鐘在腐爛橘子四周的(上下左右)其他新鮮橘子都會腐爛，請回傳整個 grid 中所有新鮮橘子都腐爛最少需要幾分鐘，如果不可能全都腐爛，則回傳 -1 解法一開始的想法我原先認為這題就是要將腐爛橘子作為搜尋起點，然後BFS走訪附近的新鮮橘子，並且計算距離，每多走一格就會變成腐爛橘子，最後回傳最小距離就好。但後來發現這樣不符合題意，因為題目的要求是每一分鐘腐爛過子四周的新鮮橘子也會變腐爛，原先的做法會忽略了 「一輪 BFS 表示一分鐘」的關鍵邏輯。 腐蝕的時間應該是按 層數來計算，而非單純依照單一節點的距離。並且在BFS結束後，可能還是會有新鮮橘子存在(可能是分隔在其他cell中) ...

題目敘述 題目難度：Medium 題目描述： 給定一個 m x n 大小的網格 rooms 並且可能初始化三種值：(1) -1 代表牆壁或者障礙物 (2) 0 代表閘門 (3) INF 則代表空房間，這裏的 INF 代表 2^31 - 1 = 2147483647 (整數的上界)，其實就想成是房間到閘門的距離初始化無限大。 本提要求將空房間填入距離他最近閘門的距離值。 解法一開始的想法這裡其實也是要求從圖中的閘門當成搜尋起點，來去進行路徑走訪，將所有路過的空房間都標注與閘門的距離，所以要做的事會是 BFS 走訪。只不過在 BFS 發現新的 Connected Vertex 的時候會需要將其標注上與搜尋起點(閘門)的距離 我的解法123456789101112131415161718192021222324252627282930313233343536class Solution &# ...

題目敘述 題目難度：Medium 題目描述： 題目給定了一個 connected undirect graph 中節點的參考設計，希望你回傳這個 graph 的 Deep Copy 1234class Node { public int val; public List<Node> neighbors;} 其實看到 Deep Copy 就可以想的是要用 Hash Table 了 這題還有說明，這題節點的 index 與節點的 value 相同，也就是第一個節點的 val 就會是 1 ，而第二個節點的 val 就會是 2 以此類推。 然後題目會給定一個 adjacency list 這個 list 中的每個 sublist 都描述了個別節點與其他節點的相鄰狀況，例如： 1adjList = [[2,4],[1,3],[2,4],[1,3] ...

題目敘述 題目難度：Medium 題目描述： 題目給定一個 m x n 大小的二元陣列 grid，陣列中 1 代表陸地，0 代表水域，島嶼四面環水，相鄰的陸地會水平或垂直地連接而成，請回傳陣列中島嶼的最大面積，如果沒有島嶼則回傳 0 解法一開始的想法這題算是接續 LeetCode#200. Number of Islands 所以我的解題策略會基於這題，就是一樣先透過 DFS 找到 Connected Components 然後這裡累加Connected Components 的面積，再比較最大面積。 我的解法1234567891011121314151617181920212223242526272829303132333435class Solution {public: vector<vector<int>> visited; i ...

題目敘述 題目難度：Medium 題目描述： 題目給定一個 m x n 大小的二元陣列 grid，陣列中 1 代表陸地，0 代表水域，請回傳島嶼的數量。島嶼四面環水，相鄰的陸地會水平或垂直地連接而成。 解法一開始的想法這裡的想法就是這應該其實要找的是 這個 Grid 中的所有 connected components 的數量 ， 這可以透過對所有尚未訪問節點進行 BFS 或 DFS 並透過一個 counter 來紀錄就可實現。 我的解法123456789101112131415161718192021222324252627282930313233class Solution {public: int row, col; vector<vector<int>> visited; //0:unvisited, 1:visited voi ...

前言這裡接續前一篇關於 圖的基本介紹，接著需要來了解在圖中要如何搜尋特定的 vertex，也就是需要知道怎麼走訪圖，主要有三種基本的演算法: Breadth-First Search (BFS)： 用於有向和無向圖的走訪 Depth-First Search (DFS)：用於有向和無向圖的走訪 Topological Search： 用於偵測有向無環圖(Directed Acyclic Graph, DAG)的偵測。 BFS以前有介紹過 Tree的 BFS(Level-Order Traversal)，Level-Order 會依序造訪不同level的節點，而level 其實就對應到 Graph概念中節點與節點之間的距離(Distance)，它其實就代表 root 和 node 之間的距離。 那圖的 BFS又會有哪些差異呢？如果要走訪一個 connected 的無向圖，那可以由任意節點 ...