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

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

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

題目敘述 題目難度：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]] 這代表第ㄧ個節點 (index=0) 的鄰接節點有 val==2 以及 val==4 的節點。 而這代表第二個節點 (index=1) 的鄰接節點有 val==1 以及 val==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; int dfs(vector<vector<int>> &grid, int row, int col){ if(row < 0 ||...

題目敘述 題目難度：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 void dfs(int r, int c, vector<vector<char>>& grid){ if(r<0 || r>= ...

前言這裡接續前一篇關於 圖的基本介紹，接著需要來了解在圖中要如何搜尋特定的 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 的無向圖，那可以由任意節點(假設是 vertex(A))出發，另外由於是 connected 的， 因此可以走訪跟 vertex(A)相同connected components的所有節點，並且獲得距離vertex(A)...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個未排序的整數陣列 nums，請回傳它元素的最長度序列， 本題要求實踐出的演算法複雜度為 $O(n)$ 解法一開始的想法雖然這題的 tag 在 LeetCode 裡面是有 hash table，但其實這題應該可以不用到它，我的想法是 既然是未排序，但又要找連續序列，那就將它排序再迭代去檢查就好。 我的解法1234567891011121314151617181920212223class Solution {public: int longestConsecutive(vector<int>& nums){ if(nums.empty()) return 0; if(nums.size()==1) return 1; int counter = 1; int maxValue = 1; sort(nums.begin(), nums.end()); for(int i=1; i<num...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個大小 m x n 的整數矩陣 matrix，並且遵循下面兩個特性： 每一行中元素都以非遞減排序 每一行的第一個元素都大於上一行的最後一個元素 此時題目給定一個整數 target 請回傳 target 是否存在於 matrix 題目額外限制實踐出的解法必須為 $O(log(m \times n))$ 解法一開始的想法最直覺還是使用暴力解，就雙重迴圈迭代下去．但這樣複雜度會是 $O(m \times n)$，排序資料比大小正常來說會想到二元搜索，而現在題目是二維矩陣， 此時可以嘗試將二維陣列同樣用一維的方式進行二元搜索，只要注意最後 index 的計算即可 解法 - Binary Search12345678910111213141516171819202122class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target){ int...

前言以前我們在儲存資料的時候，常見的資料結構有陣列、雜湊表、鏈結串列等。想像你今天你剛上大學然後有個修課表，用表格列出各種課程，但你並不知道哪些課程需要先修，哪些可能需要之後再修，或者某些課程可能會擋修，這時候用圖來表示課程之間的關係就很方便了。所以圖的重點之一 就是保存資料與資料之間的關係 。 這篇部落格主要參考 這篇 的講解 圖(Graph)的定義延續上面的課程圖，每個課程都代表一個 節點，節點是可用於存放資料，資料就是課程名稱。而課程與課程之間有箭頭相連，代表課程與課程之間的關係。 vertex: 每個節點在圖中被稱為vertex，或 node，並定義所有 vertex 的集合叫做 $V$ 或是 $V(G)$edge: 每個線段稱為 edge， 在圖中通常會用一對vertex 來表示他們之間的edge ，$(V_{i}, V_{j})$ 就代表 $V_{i}$ 與 $V_{j}$ 之間的 edge，通常定義所有 edge 的集合為 $E$ 或者 $E(G)$ 有了 $V$ 和 $E$ 就可以定義什麼是圖， 也就是節點與節點之間關係的集合 $G(V, E)$ 圖的...

題目敘述 題目難度: Medium 題目敘述: 題目給了一個整數陣列 height 並且長度為 n， n 代表有 n 條垂直的線，第 i 條線的長度範圍為座標 (i,0) 到 (i, height[i]) (反正 height 的值就會是線的長度)，請找到兩條線與X軸共同形成一個容器，可以裝最多的水，請回傳可能裝的最大面積。 解法一開始的想法總之面積會是由比較矮的直線乘上底邊 $Area = \min(height[i], height[j]) \times (j-i)$ 暴力解12345678910111213141516class Solution {public: int maxArea(vector<int>& height){ int maxArea = 0; int n = height.size(); for(int i = 0; i < n; i++){ for(int j=i+1; j < n; j++){ ...