LeetCode #21 Merge Two Sorted Lists - 刷題之旅
1 題目描述
合併兩個有序的鍊錶，並且返回一個新的鍊錶。新的鍊錶是由兩個鍊錶的節點組成的。
2 解法
跟 leetcode-2-add-two-numbers 很類似，因為它涉及到多個 listNode 的操作，並且將操作結果合併為一個，因此我們可以使用 dummy_head 來幫助我們串接結果。因為他是排序，所以要比較兩個數字的大小，但是我們最怕的是在取listNode的值時發現他是None而導致錯誤，因為題目說數字範圍是[0, 50] 因此我們取 100 當作最大值，因此我們可以使用 digit1 = list1.val if list1 else 100 的方式，儘管遇到 none 仍然可以繼續執行迴圈，直到兩個 list1 跟 list2 都觸底，以避免 None 的問題。
1234567891011121314151617181920212223242526272829class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextcl ...
LeetCode #2 Add Two Numbers - 刷題之旅
1 題目描述
這題就是兩個鍊錶表示的數相加，這樣就可以實現兩個很大的數相加了，關鍵要能無需考慮數值 int ，float 的限制了。但是如果你把 ListNode 直接串啟程字串並且轉換成數字，這你就大錯特錯了！因為這樣就失去了這題的意義了。
2 解法
2.1 我的解法
我一開始沒意識到，這題的 ListNode 是倒序的，所以我一開始的想法是把兩個 ListNode 轉換成數字，然後相加，再轉換成 ListNode。但是這樣就失去了這題的意義了。因為有一個test case是超級長的[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]直接突破了int的限制。
所以我的解法無法通過這個 test case。建議參考下一個方法
12345678910111213141516171819202122232425262728293031class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) ...
LeetCode #141 Linked List Cycle - 刷題之旅
1 題目描述
判斷一個 linked list 是否有 cycle，如果有就返回 True，沒有就返回 False。
特殊要求空間複雜度為 O(1)。
2 解法
2.1 我的解法
一開始我的想法很簡單，但是空間複雜度為 O(n)。就是把每個節點都放進一個 set 裡面，如果有重複的節點就返回 True，否則返回 False。但是這個不滿足要求空間複雜度為 O(1)。
123456789class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: check_dict = {} while head: check_dict.__setitem__(head, head.val) head = head.next if check_dict.get(head): return True return False
2.2 龜兔演算法
這個方 ...
LeetCode 課前預習 - 掌握 Linked List 的核心
介紹
Linked List 鏈結串列是一種常見且基礎的資料結構，我們可以基於 Linked List 去建立 Queue、Stack 等資料結構。關於Stack與Queue可以參考這篇文章LeetCode 課前預習 - 掌握 Stack 和 Queue 大全。
Linked List 的種類
single linked list: 只能訪問下一個節點
double linked list: 可以訪問上一個和下一個節點
circular linked list: 最後一個節點指向第一個節點
linked list 一個很重要的概念是這個 list 的* Node.next 是儲存下一個 Node 在實際記憶體中的位置*，而不是儲存下一個 Node 的值。
結構
節點
一個linked list主要由節點Node組成，每個節點包含兩個部分：
data: 用來存放節點的數據
next: 用來指向下一個節點，是一個指標 pointer，pointer 會指向下一個節點，而最後一個節點的 pointer 則是指向 Null。
1234class Node: def __init ...
LeetCode #224 Basic Calculator - 刷題之旅
1 題目描述
這題是 Hard 的題目，難度在於，要如何處理以下問題：
碰到括號怎麼進行優先處理
括號前面的“-”號會改變括號內的數字正負，並且要與括號外的數字相加
2 解法
首先一個很重要的概念是，我們要如何處理括號的問題，這邊我們會使用到三個變數：
sign：用來記錄當前的正負號，初始值為 1，通常用來記錄數字前一個符號是正還是負。
res：用來記錄當前的結果，初始值為 0，通常是用來記錄左括號之前的加總數字。
num：用來記錄當前的數字，初始值為 0，通常是當前括號內的數字總和。
因此我們所使用的公式如下：
在了解公式之後，我們要有一個邏輯處理當碰到左括號 和 右括號的流程。
當碰到左括號
我們要記錄當前的 res 和 sign先放到 stack 裡面，並且重新設定 res 和 sign 為 0 和 1。
然後優先處理括號內的數字，直到遇到右括號。
當碰到右括號
當前的 res 是括號內的加總數字
括號的前一個符號，也就是在 stack 裡面的 sign 會決定括號內的數字是正還是負。
因此我們會將括號也就是當前的 res 和 stack 的sign 取出來並 ...
LeetCode #150 Evaluate Reverse Polish Notation - 刷題之旅
1 題目描述
題目中是逆波蘭式，計算法則就是，每次找到運算子位置的前兩個數字，然後再進行計算。
2 解法
這題不會太難，我覺得關鍵在你要意識到，當計算完後，要把結果再 push 回去 stack 裡面，這樣下次遇到運算符號時，才可以再次的把上一次的計算結果一起pop出來。
以範例的 ["4","13","5","/","+"] 為例好了，大概是這樣：
1234567891011121314151617181920class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] operators = ["+", "-", "*", "/"] for i in tokens: cur = i if cur not in operat ...
LeetCode #155 Min Stack - 刷題之旅
1 題目描述
這題的重點在於要實現一個可以取得最小值的 stack，並且要求時間複雜度為 O(1)。解題思路的重點是，你要怎麼確保在 push() 的時候，更新最小值，並且在 pop() 的時候，如果 pop() 出當前最小值時，也要更新最小值。
2 解法
2.1 我的解法
有沒有發現重點，當 pop() 和 push() 的時候，最小值也會有所更新，在 pop() 的時候，最小的值被剔除時，我們希望取得第二小，因此我們會需要一個 min_stack 來記錄當前最小值，如果遇到當前更小的，就 push() 進去 min_stack 裡面。這樣儘管最小的被 pop() 出去，我們仍然可以取得第二小的值。
大概是這種感覺：
每當 push 新的值進去時，都要與 min_stack[-1] 最小值比較是否更小，若更小，也要 push 進去 min_stack 裡面。
每當 pop 出去時，也要檢查 pop 出去的值是否是當前的最小值，若是，也要把當前的 min_stack[-1] pop 出去
其他的功能就跟 stack 一樣，在 python 可以使用 list 來實現 s ...
LeetCode #20 Valid Parentheses - 刷題之旅
1 題目描述
這是一個括號匹配的問題，給一個只包含(, ), {, }, [, ]的字符串，目的是要檢查一個字串是否是有效的括號組合。
2 解法
我的想法很簡單：
先建立一個 dictionary，把所有的括號對應關係記錄下來。 key 是 (, {, [，value 是說明 key 的方向(open or close)與屬性(大, 中, 小括號)。
開始遍歷字串，如果是open，就把它放進 stack 裡面，如果是close，就檢查 stack 最上面的元素是否是對應的開括號，如果是就 pop 掉，不是就返回 False。
大概是這種感覺：
123456789101112131415161718192021222324252627class Solution: def isValid(self, s: str) -> bool: str_dic = { "{": ["open", "Big"], & ...
LeetCode #71 Simplify Path - 刷題之旅
1 題目描述
這個題目的目標是在把一個很複雜的路徑簡化成為一個簡單的路徑，例如：
input: /a/./b/../../c/
output: /c
從上面的例子來說，/a/b 進去後，往上一層，再往上一層，回到/，最後進到 /c，但直接寫成 /c 不就好了嗎？太蠢了，請簡化他！這就是題目的用意。
2 解法
從題目的思路來看，你會發現當遇到 /.. 的時候，就需要往上一層，其實就是把目前 stack 的最上面的目錄 pop 出來，當遇到正常的目錄而不是/. 或是 /.. 就可以放入 stack 裡面。從下面的圖片來看，以 /.../a/../b/c/../d/./ 為例子，我們可以看到 stack 的變化。（注意 /... 是一個目錄，因為他不是 /. 或是 /..）
從下圖來看，只要是正常檔案名稱，就放入 stack 裡面
當遇到 .. 的時候，就 pop 出來，當遇到 . 的時候，就不做任何事情，繼續往下走。
最後，把 stack 裡面的元素，用 / 串接起來，就是答案。
12345678910111213141516171819202122232425 ...
LeetCode 課前預習 - 掌握 Stack 和 Queue 大全
Stack
Stack是一種線性資料結構，遵循後進先出（LIFO）的原則。
LIFO 現實中的例子可以想像一落堆疊起來的盤子，我們需要從最上面開始拿；又或者像一台塞滿人的電梯，最後進的最靠門的人必須要先出去，後面的人才能出去。
基本操作
Push: 將元素添加到Stack的頂部。
Pop: 從Stack的頂部移除元素。
Peek/Top: 獲取Stack頂部的元素但不移除它。
1234567891011121314151617181920212223242526272829303132public static class Stack { private static class Node { private int data; private Node next; private Node(int data) { this.data = data; } } private Node top; // remove from the t ...