LeetCode系列文章 [LeetCode] #12 Integer to Roman 解題 題目連結 題型解說 這是一題難度為普通的題目 需要設計一個方法,此方法會傳入一個整數 num 要求是把整數轉換成羅馬字母,轉換清單如下 I => 1 V => 5 X => 10 L => 50 C => 100 D => 500 M => 1000 但羅馬字母有一些特殊規則 4 並非 IIII
LeetCode系列文章 [LeetCode] #11 Container With Most Water 解題 題目連結 題型解說 這是一題難度為中等的題目 需要設計一個方法,此方法會傳入一個數字陣列 height 陣列中的元素代表每一個柱子的高度 現在需要計算出,該陣列中以某兩隻柱子為邊界,最多可以裝多少水 以範例來說 height = [1,8,6,2,5,4,8,3,7] 最多可以裝 7 * 7 = 49 單位的水 解題思路 計算面積就是底乘上高 底的計算方式為 「右邊柱子的 index」 減去 「左邊柱子的
LeetCode系列文章 [LeetCode] #941 Valid Mountain Array 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個數字陣列 arr 判斷陣列中的元素是不是由低到高再從高到低(山形)的排序,且不連續一個以上數字 比如說 [1,2,3,2] 就是一個山形陣列,但 [1,2,2,3,2] 不是,因為有兩個 2 [1,2,3,4,5] 和 [5,4,
LeetCode系列文章 [LeetCode] #944 Delete Columns to Make Sorted 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個字串陣列 strs 這個陣列中每個字串的長度都相同,字串內容都是小寫英文 需要檢查每個元素的第 N 個字元是不是由小至大排列,並回傳有幾個錯誤排列 比如傳入的陣列長這樣 ["cba","daf","ghi"] 取第一個字元 = cdg 取第二個字元 = bah 取第三個字元 = afi 其中第二組的結果(bah)並不是由小至大排列,故回傳 1
LeetCode系列文章 [LeetCode] #122 Best Time to Buy and Sell Stock II 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數陣列 prices 這個陣列表示每一天的股票價格,若可以購買無數次(買入 + 賣出) 回傳最大利潤是多少 解題思路 這一題是 [LeetCode] #121 Best Time to Buy and Sell Stock 解題 的延伸 上一題是要求只能買一次,這一題是可以買無數次 但規則一樣是手頭有買入的股票前不能再買入 一開始解法是把所有的狀況走一遍,找出利潤最好的那個 後來看了官方提供的思路,其實只要用迴圈歷遍一次,只要比明天的價格低就把差價算到利潤去 因為最大的利潤可以拆成多個小利潤的和
LeetCode系列文章 [LeetCode] #121 Best Time to Buy and Sell Stock 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數陣列 prices 這個陣列表示每一天的股票價格,若只能購買一次(買入 + 賣出) 回傳最大利潤是多少 解題思路 原本我是利用兩個索引左右移動想辦法找出最大利潤是哪一個 但總會有一些例外狀況導致算法不通過 這題想了很久也沒想出怎麼寫才是有效率的 後來就放棄去找答案,原來只要紀錄下當下最小值與最大利潤 下次遇到更小的值就更新一下,繼續計算最大利潤就好 程式碼 Java class Solution { public int maxProfit(int[] prices) { int result = 0; int min
LeetCode系列文章 [LeetCode] #119 Pascal's Triangle II 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數 rowIndex 回傳一個巴斯卡三角形中的 rowIndex 層 解題思路 這題是 [LeetCode] #118 Pascal's Triangle 解題 的延伸 原本是要回傳整個巴斯卡三角形,現在只要回傳某一層 且空間複雜度只能是 O(k),也就是只能用一個 List 那麼就把每一層的值算出來,然後把下一層的值覆蓋上去 程式碼 Java class Solution { public List<
LeetCode系列文章 [LeetCode] #118 Pascal's Triangle 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數 numRows 回傳一個與 numRows 相同層數的巴斯卡三角形 解題思路 這一題看一下官方給的示意圖就大概知道怎麼寫了 除了第一個及最後一個元素都是 1 之外 每一個元素(j)的值都是上一層(i - 1)(j) + (i - 1)(j - 1) 程式碼 Java class Solution { public List&
LeetCode系列文章 [LeetCode] #112 Path Sum 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 和一個整數 sum 回傳這棵樹有沒有一條路徑的所有節點總和為 sum 必須得要走到最後一個節點 解題思路 這題看是要寫個遞迴還是使用 Queue 搭配迴圈都可以 如果選擇遞迴版本的,可以用同一個方法來遞迴 每一層把 sum 減去節點的值後傳到下一層去 若遇到最後一個節點並且 sum 剛好為 0 就回傳 true 如果選擇迴圈版本,可以把上一層節點的值加到下一個節點中 若遇到最後一個節點並且值與 sum 一樣就回傳 true 程式碼
LeetCode系列文章 [LeetCode] #111 Minimum Depth of Binary Tree 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 回傳這棵樹最淺節點深度 解題思路 這題看是要寫個遞迴還是使用 Queue 搭配迴圈都可以 記得不要用到 Stack 了,Queue 是先進先出 修改一下 [LeetCode] #110 Balanced Binary Tree 解題 的解法就可以了 程式碼 Java class Solution { public int minDepth(TreeNode root)
LeetCode系列文章 [LeetCode] #110 Balanced Binary Tree 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 回傳這棵樹是不是高度平衡,也就是左節點的深度與右節點點的深度相差不超過 1 解題思路 這題看是要寫個遞迴還是使用 Stack 搭配迴圈都可以 一開始做這一題時搞錯題意,原本以為只要從根節點算左右深度相減不超過 1 就好 結果是每一個節點左右都要平衡 Orz 程式碼 Java class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true;
LeetCode系列文章 [LeetCode] #108 Convert Sorted Array to Binary Search Tree 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個排序好的陣列 nums 回傳一顆平衡的二元搜尋樹,左右兩邊的層級不能超過 1 解題思路 二元搜尋樹有幾個特性 不會有重複的值 左節點數值一定比根節點數值小 右節點數值一定比根節點數值大 其他層的節點也要符合以上要求 既然所有的右邊節點一定比根節點大,所有左邊節點一定比根節點小,題目也規定兩邊的層數不能相差超過 1 那麼根節點只能選 nums 的中間值,這邊有個小疑問「如果 nums 是偶數呢?」,是要選左邊那個還是右邊那個? 答案其實無所謂,因為題目有提示說答案不止一種 根節點選擇好了後就能把 nums 拆成左右兩部分,左右兩部分也需要符合
LeetCode系列文章 [LeetCode] #139 Word Break 解題 題目連結 題型解說 這是一題難度為中等的題目 需要設計一個方法,此方法會傳入一個字串 s 和 字串 list wordDict 回傳能不能利用 wordDict 內的值組合出 s 範例: s = "applepenapple", wordDict = ["apple", "pen"],則回傳 true s = "catsandog", wordDict
LeetCode系列文章 [LeetCode] #107 Binary Tree Level Order Traversal II 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 將這顆樹每一層的節點收集後回傳 解題思路 這題也是沒什麼難點,看是要用遞迴還是迴圈都可以解題 LeetCode 上有很多的題目都跟樹有關的,基本歷遍樹的方法掌握之後,解題上都不會太困難 程式碼 Java class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<
LeetCode系列文章 [LeetCode] #104 Maximum Depth of Binary Tree 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 回傳這棵樹最深的節點是第幾層 解題思路 這題基本上就是用遞迴去濾到最後深的一個節點,雖然說使用迴圈也可以做到 但就必須多寫一點程式碼,底下也會提供迴圈的版本 講回到遞迴,都必須搭配一個數字來計算第幾層 有從第一層加下去的,也有從最後一層加上來的 兩種版本也會附上 程式碼 Java class Solution { // 從第一層加下去 public int maxDepth(TreeNode root) { return maxDepth(root, 1); } private int
LeetCode系列文章 [LeetCode] #101 Symmetric Tree 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 回傳這棵樹是不是左右對稱的 解題思路 這題跟上一題 [LeetCode] #100 Same Tree 解題 是高度相像的 唯一的差異是因為要確認是否對稱,所以是左邊跟右邊比,右邊跟左邊比,中間一樣跟中間比 其中一個沒比對上就回傳 false 程式碼 Java class Solution { public boolean isSymmetric(TreeNode root) { if (root == null)
LeetCode系列文章 [LeetCode] #100 Same Tree 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入兩個二元樹 p 和 q 回傳這兩棵樹是不是完全一樣 解題思路 這題看是要寫個遞迴還是使用 Stack 搭配迴圈都可以 沒有什麼困難點,就是左邊跟左邊比,右邊跟右邊比,中間跟中間比 其中一個沒比對上就回傳 false 程式碼 Java class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null
LeetCode系列文章 [LeetCode] #88 Merge Sorted Array 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入兩個已排序的整數陣列 nums1 nums2 及它們各自的長度 m 與 n 將 nums2 的元素合併到 nums1 後進行排序即可 另 nums1 有保留給 nums2 的欄位,所以不需要另外產生新的陣列 範例: nums1 = [1,2,3,0,0,0], m = 3, nums2
LeetCode系列文章 [LeetCode] #83 Remove Duplicates from Sorted List 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個已經排序好的 Linked List head,當中每一個元素都有一個數字 將這個所有的重複數字移除後回傳 範例: head = 1->1->2,則回傳 1->2 head = 1->1->2->3->3,則回傳 1-&
LeetCode系列文章 [LeetCode] #70 Climbing Stairs 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數 n,這個 n 代表的階梯的數量 如果一次只能走 1 個階梯或 2 個階梯,回傳要到達第 n 個階梯有幾種走法 範例: n = 1,則回傳 1,因為只有一個階梯,也只能選擇走 1 個階梯 n = 2,則回傳 2,因為可以選擇走兩次 1 個階梯或是一次走
LeetCode系列文章 [LeetCode]#35 Search Insert Position 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個排序好的整數陣列 nums 和一個目標數字 target 找出 target 在 nums 的索引返回,如果沒有找到,則返回插入的索引 範例: nums = [1,3,5,6], target = 5,則回傳 2 nums = [1,3,5,6], target = 2,則回傳
LeetCode系列文章 [LeetCode] #69 Sqrt(x) 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數 x 計算出最接近 x 平方根的整數答案後回傳 簡單說就是去掉小數點只回傳整數部分 範例: x = 8,則回傳 2,雖然 8 的平方根介於 2 和 3 之間,但題目只要我們取整數就好 解題思路 如果你有搜尋過這個題目的話,大概知道主要的解題方向就是二分搜尋法的變種 更厲害的就會用 牛頓迭代法 來求根,但那已經是數學領域的東西,我自己是怎麼都看不懂 後來就自己簡單的寫了一個類似 十分逼近法
LeetCode系列文章 [LeetCode] #67 Add Binary 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入兩個字串 a 和 b,字串內容是二進制(只有 0 和 1) 將兩個字串的二進制內容相加後回傳 範例: a = "11", b = "1",則回傳 "100",因為 11 + 1 = 100 a = "
LeetCode系列文章 [LeetCode] #66 Plus One 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數陣列 digits 將這個陣列看作一串數字的組合,把數字 + 1 後回傳 範例: digits = [1,2,3],則回傳 [1,2,4],因為 123 + 1 = 124 解題思路 一開始走了彎路,寫了很多判斷和使用 List 來應付位數增加的情況 後來研究其他人的寫法後才恍然大悟,因為忽略了一個很簡單的事實 位數增加的情況就只會是 9、99、
LeetCode系列文章 [LeetCode] #58 Length of Last Word 解題 題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個字串 s 字串中由一些空白字元當作間隔,請找出最後一個單詞後將長度回傳 s 中只會由空白及英文字母組成,如果不存在最後一個單詞就回傳 0 範例: s = "Hello World",則回傳 5 解題思路 這題需要從字串的尾部開始,宣告一個計數器後逐字元確認 如果遇到空白字元請計數器不為 0 ,則直接回傳 程式碼 Java class Solution { public int lengthOfLastWord(