LeetCode系列文章

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

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

  • Michael
1 min read
LeetCode系列文章

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

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

  • Michael
1 min read
LeetCode系列文章

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

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

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #118 Pascal's Triangle 解題

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

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #112 Path Sum 解題

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

  • Michael
1 min read
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)

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #110 Balanced Binary Tree 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個二元樹 root 回傳這棵樹是不是高度平衡,也就是左節點的深度與右節點點的深度相差不超過 1 解題思路 這題看是要寫個遞迴還是使用 Stack 搭配迴圈都可以 一開始做這一題時搞錯題意,原本以為只要從根節點算左右深度相減不超過 1 就好 結果是每一個節點左右都要平衡 Orz 程式碼 Java class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true;

  • Michael
1 min read
LeetCode系列文章

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

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

  • Michael
2 min read
LeetCode系列文章

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

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

  • Michael
1 min read
LeetCode系列文章

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

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

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #101 Symmetric Tree 解題

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

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #100 Same Tree 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入兩個二元樹 p 和 q 回傳這兩棵樹是不是完全一樣 解題思路 這題看是要寫個遞迴還是使用 Stack 搭配迴圈都可以 沒有什麼困難點,就是左邊跟左邊比,右邊跟右邊比,中間跟中間比 其中一個沒比對上就回傳 false 程式碼 Java class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #69 Sqrt(x) 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數 x 計算出最接近 x 平方根的整數答案後回傳 簡單說就是去掉小數點只回傳整數部分 範例: x = 8,則回傳 2,雖然 8 的平方根介於 2 和 3 之間,但題目只要我們取整數就好 解題思路 如果你有搜尋過這個題目的話,大概知道主要的解題方向就是二分搜尋法的變種 更厲害的就會用 牛頓迭代法 來求根,但那已經是數學領域的東西,我自己是怎麼都看不懂 後來就自己簡單的寫了一個類似 十分逼近法

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #66 Plus One 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個整數陣列 digits 將這個陣列看作一串數字的組合,把數字 + 1 後回傳 範例: digits = [1,2,3],則回傳 [1,2,4],因為 123 + 1 = 124 解題思路 一開始走了彎路,寫了很多判斷和使用 List 來應付位數增加的情況 後來研究其他人的寫法後才恍然大悟,因為忽略了一個很簡單的事實 位數增加的情況就只會是 9、99、

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #58 Length of Last Word 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個字串 s 字串中由一些空白字元當作間隔,請找出最後一個單詞後將長度回傳 s 中只會由空白及英文字母組成,如果不存在最後一個單詞就回傳 0 範例: s = "Hello World",則回傳 5 解題思路 這題需要從字串的尾部開始,宣告一個計數器後逐字元確認 如果遇到空白字元請計數器不為 0 ,則直接回傳 程式碼 Java class Solution { public int lengthOfLastWord(

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #26 Remove Duplicates from Sorted Array 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個已經排好序的 int 陣列 nums 將這個陣列移除重複元素後把長度回傳 範例: nums = [1,1,2],則回傳 2,因為元素 1 重複了 題中還要求不能另外建立陣列,必須使用原陣列進行操作 解題思路 這一題既然要求只能使用原陣列,那就只能把不重複的數字往前排 而且陣列已經幫我們排好序,那就準備一個 index 變數用來紀錄最後一個不重複元素的索引 之後跑一次迴圈,如果遇到與 index 索引指向的元素不相同的話,把

  • Michael
1 min read
LeetCode系列文章

[LeetCode] #20 Valid Parentheses 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個字串 s 這個字串只會由 6種符號 組成,分別是 ( ) { } [ ] 必須驗證傳入的字串 s 中的符號是不是有被正確匹配 範例: s = "()",則回傳 true s = "()[]{}",則回傳 true s = "(]",則回傳 false 解題思路 一開始我的第一直覺是利用前後索引來驗證,但遇到以下狀況就會驗證失敗 "

  • Michael
1 min read