LeetCode系列文章

LeetCode系列文章

[LeetCode] #100 Same Tree 解題

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

LeetCode系列文章

[LeetCode] #88 Merge Sorted Array 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入兩個已排序的整數陣列 nums1 nums2 及它們各自的長度 m 與 n 將 nums2 的元素合併到 nums1 後進行排序即可 另 nums1 有保留給 nums2 的欄位，所以不需要另外產生新的陣列 範例: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3，則回傳 [1,2,2,3,5,6] m 為 nums1 的元素數量，n

LeetCode系列文章

[LeetCode] #83 Remove Duplicates from Sorted List 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個已經排序好的 Linked List head，當中每一個元素都有一個數字 將這個所有的重複數字移除後回傳 範例: head = 1->1->2，則回傳 1->2 head = 1->1->2->3->3，則回傳 1->2->3 解題思路 這一題沒有太多好講的部分，就是利用迴圈或是遞迴的方式來把重複的數字過濾掉 如果是利用迴圈的方式，得要建立兩個參考物件 一個用來參考到最後一個元素，另一個用來歷遍所有元素 另一個遞迴解法是其他人提交的內容，寫遞迴挺燒腦的，所以就直接拿其他人的來用 很巧妙，只有三行 程式碼 Java class Solution { public ListNode deleteDuplicates(ListNode head) { if

LeetCode系列文章

[LeetCode] #70 Climbing Stairs 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個整數 n，這個 n 代表的階梯的數量 如果一次只能走 1 個階梯或 2 個階梯，回傳要到達第 n 個階梯有幾種走法 範例: n = 1，則回傳 1，因為只有一個階梯，也只能選擇走 1 個階梯 n = 2，則回傳 2，因為可以選擇走兩次 1 個階梯或是一次走 2 個階梯 n = 3，則回傳 3，因為可以選擇 1. 走三次 1 個階梯 2. 第一次走 1 個階梯，第二次走 2

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，則回傳 1，因為 2 不存在 nums 中，又因 2 小於 3，所以插入時會在 3 的位置，所以回傳 3 的索引 1

LeetCode系列文章

[LeetCode] #69 Sqrt(x) 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個整數 x 計算出最接近 x 平方根的整數答案後回傳 簡單說就是去掉小數點只回傳整數部分 範例: x = 8，則回傳 2，雖然 8 的平方根介於 2 和 3 之間，但題目只要我們取整數就好 解題思路 如果你有搜尋過這個題目的話，大概知道主要的解題方向就是二分搜尋法的變種 更厲害的就會用 牛頓迭代法 來求根，但那已經是數學領域的東西，我自己是怎麼都看不懂 後來就自己簡單的寫了一個類似 十分逼近法 的解法，一樣可以過關 一開始用一個比較大的區間計算，我是設定 100 利用迴圈每次加 100 後計算平方直到大於 x 再慢慢扣 1 直到小於等於 x 程式碼 Java class Solution

LeetCode系列文章

[LeetCode] #67 Add Binary 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入兩個字串 a 和 b，字串內容是二進制(只有 0 和 1) 將兩個字串的二進制內容相加後回傳 範例: a = "11", b = "1"，則回傳 "100"，因為 11 + 1 = 100 a = "1010", b = "1011"，則回傳 "10101" 解題思路 跟之前的一些題目一樣，有字串解跟數字解兩種方式 字串解比較直覺，但效能較差一些，程式碼也會多一些 兩種解同樣都是從字串最後面往回歷遍，等同於加法方式，由右到左 程式碼 Java class Solution { public String addBinary(String a, String

LeetCode系列文章

[LeetCode] #66 Plus One 解題

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

LeetCode系列文章

[LeetCode] #58 Length of Last Word 解題

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

LeetCode系列文章

[LeetCode] #38 Count and Say 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個整數 n，將 n 計數轉換後回傳 一開始看到這一題無法第一時間理解意思 後來找了下中文翻譯後總算了解題目是想要說什麼 範例: n = 1，直接回傳 1 n = 2，需要回傳 11，因為 n = 1 時是回傳 1，所以用語言說的話就是 1 個 1 => 11 n = 3，需要回傳 21，因為 n = 2 的時候是 2 個 1 n = 4，需要回傳 1211，因為 n = 3 的時候是 1

LeetCode系列文章

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

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

LeetCode系列文章

[LeetCode] #21 Merge Two Sorted Lists 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入二個已經排好序的 Linked list 將兩個 Linked list 合併成一個 Linked list 並且排好序(小到大)後回傳 範例: list1 = [1, 2, 3, 4]、list2 = [1, 2, 3, 4]，則回傳 [1, 1, 2, 2, 3, 3, 4, 4] 解題思路 我們利用一個 while 迴圈來運作，從兩個 list 中各取一個來比較 將比較小的 Node 串到要回傳的 Node 中後將該 list 的變數設為下一個

LeetCode系列文章

[LeetCode] #20 Valid Parentheses 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個字串 s 這個字串只會由 6種符號 組成，分別是 ( ) { } [ ] 必須驗證傳入的字串 s 中的符號是不是有被正確匹配 範例: s = "()"，則回傳 true s = "()[]{}"，則回傳 true s = "(]"，則回傳 false 解題思路 一開始我的第一直覺是利用前後索引來驗證，但遇到以下狀況就會驗證失敗 "[(){}]"，這個情況是要回傳 true 的，因為所有的符號都有正確匹配 所以正確的思路是利用一個 堆(Stack) 來解題 堆的特色就是「後進先出」，這剛好完美地應對這一題 所謂的「後進先出」就是最後放入的東西會先被丟出來 利用一個迴圈掃過一次字串 s ，如果遇到開頭符號 ( { [ 我們就把結束符號放入 Stack 中，如果遇到結束符號 ) } ] 就把 Stack 中的最後一個元素丟出，

LeetCode系列文章

[LeetCode] #14 Longest Common Prefix 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個字串陣列 strs 回傳陣列中所有字串的共同前綴 範例: strs = ["flower","flow","flight"]，則回傳 "fl" strs = ["dog","racecar","car"]，則回傳 ""，找不到共同前綴 解題思路 這題就簡單的使用暴力法，以第一個字串當基準比對每一個 char 如果遇到不對的就直接回傳結果，可以用雙 for迴圈 也可以使用 while迴圈，隨個人喜好 程式碼 Java class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length == 0 || strs[0].length() == 0) { return ""; } if (strs.

LeetCode系列文章

[LeetCode] #13 Roman to Integer 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個羅馬數字字串 s 將羅馬數字轉成阿拉伯數字後回傳 解題思路 這一題只要按照題目中給的規則跑一次迴圈就好，很直覺 PS: 熟悉羅馬數字的規則的話可以將程式碼更省略一點 程式碼 Java class Solution { public int romanToInt(String s) { int result = 0; s += " "; // 多在字串尾加入一個空字串可以省略迴圈的邊界檢查 for (int i = 0, len = s.length() -1; i < len; i++) { switch (s.charAt(i)) { case 'I': // 需要確認下一個符號是不是 V 或 X if (s.charAt(

LeetCode系列文章

[LeetCode] #9 Palindrome Number 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法，此方法會傳入一個整數 x 確認將 x 反轉後是否依然為原樣，簡單來說就是正著讀反著讀是不是都一樣 範例: x = 121，則回傳 true x = -121，則回傳 false，因為 -121 不等於 121- x = 10，則回傳 false 另外題目有說試著不要將數字轉成字串來解解看 解題思路 第一步判斷 x 如果小於 0 就回傳 false，如果小於 10 就回傳 true 之後看是要用數字的四則運算來求解還是轉成字串求解都可以 如果選擇用數字來求解，步驟與 [LeetCode] #7 Reverse Integer 解題 一樣 如果選擇用字串來求解，可以用一個