LeetCode系列文章

[LeetCode] #12 Integer to Roman 解題

題目連結題型解說這是一題難度為普通的題目需要設計一個方法，此方法會傳入一個整數 num 要求是把整數轉換成羅馬字母，轉換清單如下 I => 1 V => 5 X => 10 L => 50 C => 100 D => 500 M => 1000 但羅馬字母有一些特殊規則 4 並非 IIII 而是 IV，9 並非 VIIII 而是 IX 這規則同樣可以套用到 40 90 400 900 解題思路既然知道特殊規則是一樣的，變得是使用的符號，那麼先從 num 取個位數開始轉換完成後，把 num 除上 10，消除個位數，

LeetCode系列文章

[LeetCode] #11 Container With Most Water 解題

題目連結題型解說這是一題難度為中等的題目需要設計一個方法，此方法會傳入一個數字陣列 height 陣列中的元素代表每一個柱子的高度現在需要計算出，該陣列中以某兩隻柱子為邊界，最多可以裝多少水以範例來說 height = [1,8,6,2,5,4,8,3,7] 最多可以裝 7 * 7 = 49 單位的水解題思路計算面積就是底乘上高底的計算方式為「右邊柱子的 index」減去「左邊柱子的 index」高就取最短的那一根柱子高度拿題目給的例子來當範例建立三個變數 result、left、right left、right 代表左右兩邊的 index result 代表目前最大容量，初始值 0 第一步，找出最短的柱子高度，

LeetCode系列文章

[LeetCode] #941 Valid Mountain Array 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個數字陣列 arr 判斷陣列中的元素是不是由低到高再從高到低(山形)的排序，且不連續一個以上數字比如說 [1,2,3,2] 就是一個山形陣列，但 [1,2,2,3,2] 不是，因為有兩個 2 [1,2,3,4,5] 和 [5,4,3,2,1] 也不算是山形陣列，前者只有往上沒有往下，後者相反解題思路準備一個數字變數(temp)和布林變數(asc)，跑一次迴圈，有可能遇到如下狀況 1. 某個數字與前一個數字相同，這時候直接回傳 false

LeetCode系列文章

[LeetCode] #944 Delete Columns to Make Sorted 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個字串陣列 strs 這個陣列中每個字串的長度都相同，字串內容都是小寫英文需要檢查每個元素的第 N 個字元是不是由小至大排列，並回傳有幾個錯誤排列比如傳入的陣列長這樣 ["cba","daf","ghi"] 取第一個字元 = cdg 取第二個字元 = bah 取第三個字元 = afi 其中第二組的結果(bah)並不是由小至大排列，故回傳 1 解題思路這一題就用兩個迴圈各別把字元取出來，並比較是否比上一個字元大(Java 中的字元可以直接比較)，如果不是就將結果+1 程式碼 Java class Solution { public int minDeletionSize(String[] strs) { int result = 0; for (int i = 0,

LeetCode系列文章

[LeetCode] #122 Best Time to Buy and Sell Stock II 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個整數陣列 prices 這個陣列表示每一天的股票價格，若可以購買無數次(買入 + 賣出) 回傳最大利潤是多少解題思路這一題是 [LeetCode] #121 Best Time to Buy and Sell Stock 解題的延伸上一題是要求只能買一次，這一題是可以買無數次但規則一樣是手頭有買入的股票前不能再買入一開始解法是把所有的狀況走一遍，找出利潤最好的那個後來看了官方提供的思路，其實只要用迴圈歷遍一次，只要比明天的價格低就把差價算到利潤去因為最大的利潤可以拆成多個小利潤的和程式碼 Java class Solution { public int maxProfit(int[] prices) { int resule = 0; for (int i = 0; i

LeetCode系列文章

[LeetCode] #121 Best Time to Buy and Sell Stock 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個整數陣列 prices 這個陣列表示每一天的股票價格，若只能購買一次(買入 + 賣出) 回傳最大利潤是多少解題思路原本我是利用兩個索引左右移動想辦法找出最大利潤是哪一個但總會有一些例外狀況導致算法不通過這題想了很久也沒想出怎麼寫才是有效率的後來就放棄去找答案，原來只要紀錄下當下最小值與最大利潤下次遇到更小的值就更新一下，繼續計算最大利潤就好程式碼 Java class Solution { public int maxProfit(int[] prices) { int result = 0; int min = Integer.MAX_VALUE; for (int i = 0, len = prices.length; i < len; i++) { min = Math.min(min,

LeetCode系列文章

[LeetCode] #119 Pascal's Triangle II 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個整數 rowIndex 回傳一個巴斯卡三角形中的 rowIndex 層解題思路這題是 [LeetCode] #118 Pascal's Triangle 解題的延伸原本是要回傳整個巴斯卡三角形，現在只要回傳某一層且空間複雜度只能是 O(k)，也就是只能用一個 List 那麼就把每一層的值算出來，然後把下一層的值覆蓋上去程式碼 Java class Solution { public List getRow(int rowIndex) { List result = new ArrayList<>(); for (int i = 0; i <= rowIndex; i++) { result.add(

LeetCode系列文章

[LeetCode] #118 Pascal's Triangle 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個整數 numRows 回傳一個與 numRows 相同層數的巴斯卡三角形解題思路這一題看一下官方給的示意圖就大概知道怎麼寫了除了第一個及最後一個元素都是 1 之外每一個元素(j)的值都是上一層(i - 1)(j) + (i - 1)(j - 1) 程式碼 Java class Solution { public List> generate(int numRows) { List> result = new ArrayList<>(); if (numRows == 0) { return result; } result.

LeetCode系列文章

[LeetCode] #112 Path Sum 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個二元樹 root 和一個整數 sum 回傳這棵樹有沒有一條路徑的所有節點總和為 sum 必須得要走到最後一個節點解題思路這題看是要寫個遞迴還是使用 Queue 搭配迴圈都可以如果選擇遞迴版本的，可以用同一個方法來遞迴每一層把 sum 減去節點的值後傳到下一層去若遇到最後一個節點並且 sum 剛好為 0 就回傳 true 如果選擇迴圈版本，可以把上一層節點的值加到下一個節點中若遇到最後一個節點並且值與 sum 一樣就回傳 true 程式碼 Java class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } int n

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) { if (root == null) { return 0; } if (root.left == null) { return minDepth(root.right) +1; } else if (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; } if (Math.abs(isBalanced(root.left, 1) - isBalanced(root.right, 1)) > 1) { return false; } return isBalance

LeetCode系列文章

[LeetCode] #108 Convert Sorted Array to Binary Search Tree 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個排序好的陣列 nums 回傳一顆平衡的二元搜尋樹，左右兩邊的層級不能超過 1 解題思路二元搜尋樹有幾個特性 1. 不會有重複的值 2. 左節點數值一定比根節點數值小 3. 右節點數值一定比根節點數值大 4. 其他層的節點也要符合以上要求既然所有的右邊節點一定比根節點大，所有左邊節點一定比根節點小，題目也規定兩邊的層數不能相差超過 1 那麼根節點只能選 nums 的中間值，這邊有個小疑問「如果 nums 是偶數呢?」，是要選左邊那個還是右邊那個？答案其實無所謂，因為題目有提示說答案不止一種根節點選擇好了後就能把 nums 拆成左右兩部分，左右兩部分也需要符合二元搜尋樹的特性那一樣選擇中間值拆左右兩部分，所以分析後最適合的解法就是二分搜尋法了程式碼 Java class Solution { public TreeNode sortedArrayToBST(int[] nums)

LeetCode系列文章

[LeetCode] #139 Word Break 解題

題目連結題型解說這是一題難度為中等的題目需要設計一個方法，此方法會傳入一個字串 s 和字串 list wordDict 回傳能不能利用 wordDict 內的值組合出 s 範例: s = "applepenapple", wordDict = ["apple", "pen"]，則回傳 true s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]，則回傳 false 解題思路 - 遞迴暴力法這種方法簡單來說就是從頭開始切字串，如果切到存在於 wordDict 的字串時就把剩餘字串進行下一次遞迴，直到所有狀態都走過一次或找到解答為止執行結果: Time Limit Exceeded 程式碼 Java class Solution { public

LeetCode系列文章

[LeetCode] #107 Binary Tree Level Order Traversal II 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個二元樹 root 將這顆樹每一層的節點收集後回傳解題思路這題也是沒什麼難點，看是要用遞迴還是迴圈都可以解題 LeetCode 上有很多的題目都跟樹有關的，基本歷遍樹的方法掌握之後，解題上都不會太困難程式碼 Java class Solution { public List> levelOrderBottom(TreeNode root) { List> result = new ArrayList<>(); levelOrderBottom(root, 1, result); Collections.reverse(result); return result; } public void levelOrderBottom(TreeNode root, int nowLevel, List

LeetCode系列文章

[LeetCode] #104 Maximum Depth of Binary Tree 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個二元樹 root 回傳這棵樹最深的節點是第幾層解題思路這題基本上就是用遞迴去濾到最後深的一個節點，雖然說使用迴圈也可以做到但就必須多寫一點程式碼，底下也會提供迴圈的版本講回到遞迴，都必須搭配一個數字來計算第幾層有從第一層加下去的，也有從最後一層加上來的兩種版本也會附上程式碼 Java class Solution { // 從第一層加下去 public int maxDepth(TreeNode root) { return maxDepth(root, 1); } private int maxDepth(TreeNode root, int nowLevel) { if (root == null) { return nowLevel -1; } return Math.max(maxDept

LeetCode系列文章

[LeetCode] #101 Symmetric Tree 解題

題目連結題型解說這是一題難度為簡單的題目需要設計一個方法，此方法會傳入一個二元樹 root 回傳這棵樹是不是左右對稱的解題思路這題跟上一題 [LeetCode] #100 Same Tree 解題是高度相像的唯一的差異是因為要確認是否對稱，所以是左邊跟右邊比，右邊跟左邊比，中間一樣跟中間比其中一個沒比對上就回傳 false 程式碼 Java class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return isSymmetric(root.left, root.right); } public boolean isSymmetric(TreeNode p, TreeNode q) { if (p