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

題目敘述 題目難度：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 的無向圖，那可以由任意節點 ...

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

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

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

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

題目敘述 題目難度：Medium 題目描述：給定一個鏈結串列的 head 以及整數 left 和 right，其中 left<= right，請將 left 到 right 範圍內的鏈結進行反轉，最後回傳整個串列的頭。 解法一開始的想法一開始的想法蠻單純的，就是要找到 left 的前一個節點，以及 right 的後一個節點 (用來記錄反轉後要連接的節點)，將中間鏈結反轉後再接回這兩個節點。 我的解法1234567891011121314151617181920212223242526272829303132333435363738394041/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : ...

題目敘述 題目難度：Medium 題目描述： 給定一個Linked List 的 head 以及一個整數 x, 將整個 Linked List 以 x 來分隔，使節點值比 x 小的節點排在 x 前面，而節點值大於等於 x 的節點則排在 x 節點後面。 解法一開始的想法使用兩個陣列來分別儲存 1. 位置在 x 節點前面，但節點值比 x 還大的節點 和 2. 位置在 x 節點後面，但節點值比 x 還小的節點 這兩個種類的節點需要他過額外的陣列儲存，以利後續串列的重新建構。 但如過再讀取陣列值進行建構，還需要找到需要插入的位置，這樣複雜度會提高，因此不如分別建立兩個 list 的 head，然後迭代尋找並分別串列所有小於 x 的節點以及所有大於等於 x 的節點。 我的解法1234567891011121314151617181920212223242526class Solution
...

前言這題是股票買賣系列的題目: 121. Best Time to Buy and Sell Stock122. Best Time to Buy and Sell Stock II123. Best Time to Buy and Sell Stock III309. Best Time to Buy and Sell Stock with Cooldown 題目敘述 題目難度：Hard 題目描述： 給定一個整數陣列 prices，prices[i] 代表第 i 天的股票價格，每一天可以選擇買或賣股票，給定整數 k 代表可以進行的交易次數上限，請找出最大收益。 解法一開始的想法 這題基本上是完全延續 LeetCode#123. Best Time to Buy and Sell Stock III 的題目描述，因此我直接按照這題的經驗來去實踐 我的解法123456789101112 ...

前言這題是股票買賣系列的題目: 121. Best Time to Buy and Sell Stock122. Best Time to Buy and Sell Stock II188. Best Time to Buy and Sell Stock IV309. Best Time to Buy and Sell Stock with Cooldown 題目敘述 題目難度：Hard 題目描述： 給定一個整數陣列 prices，prices[i] 代表第 i 天的股票價格，每一天可以選擇買或賣股票，最多只能交易兩次 (買賣兩次)，請找出最大收益。 與先前幾題的原則一樣，只能先買後賣，並且不允許同時有多筆交易，手上股票要賣出才能夠繼續買 解法一開始的想法一開始的想法蠻簡單的，就是與前面幾題一樣，假設 prices=[3,4,5,0,0,3,1,4] 那漲跌幅值如下 1+1 +1 ...