Shannon's Blog 🐟 技術 | 生活 | 旅行

1 題目描述 簡單來說，在有序的listNode中，移除鍊錶中重複的元素，只留下沒有重複的元素。 2 解法 首先要注意的是，題目提到的是有序的鍊錶，這樣就可以很簡單的使用pointer解決這個問題。 一開始我的解法很蠢，我自己都不太想放上來了…我用三個指標，這導致我花了30分鐘才寫完，不僅僅很攏長可讀性還不高。後來我看到有人的解答是用雙指針，這樣就簡單多了。大概重新用雙指針思考一次題目，7分鐘就寫完了。 首先我們會需要兩個指針： pre 用來記錄重複的前一個元素，這樣才可以把 pre.next 接到沒有重複的元素上 cur 跟 cur.next 這兩個會不斷的比較，如果相鄰的兩個元素val相同 pre 保持原地不動 (while loop) cur 要一直往下走直到 cur.val 跟 cur.next.val 不相同 如果發現 pre.next 與 cur 不同時，就要重新接到最新的 cur 上 大概是這種感覺 12345678910111213141516171819def deleteDuplicates(self, head: Optional[ListNode] ...

1 題目描述 簡單來說，就是給定一個 linked list 和一個數字 n，要求刪除倒數第 n 個節點，並返回新的 linked list。 2 解法 2.1 我的解法 一開始想到的做法: 把所有位置的訊息存在一個 dict 裡面 然後因為已經遍歷過一次知道整個長度，直接尋找到要刪除的節點的前一個進行刪除。 1234567891011121314151617181920212223242526def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: if head.next is None: return None node_dict = {} cur = head index = 0 while cur: index += 1 node_dict.__setitem__(index, cur) cur = cur.next pre_idx = inde ...

1 題目描述 簡單來說，就是在指定的位置 m 到 n 之間，將鍊錶進行反轉。 注意的是，題目要 one pass 是指只能遍歷一次鍊錶，不能多次遍歷。 2 解法 2.1 我的解法 我的想法很簡單 先建立一個字典，紀錄 key = index, value = node 你會發現 left 到 right 之間的反轉，從 left 開始，left 應該改成 right 的值，right 應該改成 left 的值，直到 left 跟 right 相遇。 何時該停呢？當 left >= 原本的 right 時，就停止。 大概是這種感覺 1234567891011121314151617181920212223242526272829303132333435363738class Solution: def reverseBetween( self, head: Optional[ListNode], left: int, right: int) -> Optional[List ...

1 題目描述 簡單來說，就是要你複製出一個一樣的ListNode結構，而這個ListNode有一個random的參數，這個random參數是指向ListNode中的任意一個節點，這個節點可以是自己，也可以是其他節點。 2 解法 2.0 創建鍊錶 在開始前，我們總是得想辦法先做個測試資料吧…輸入是一個二維陣列，每個元素是一個list，第一個元素是值，第二個元素是random的index，如果是None就是None。 input: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]] output: ListNode 鍊錶 1234567891011121314151617181920212223242526272829303132333435363738def createLinkedList(nums: List[List[int]]) -> ListNode: if not nums: return None random_dict = {} # 存 node, random_in ...

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 ...

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]) ...

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 龜兔演算法 這個方 ...

介紹 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 ...

1 題目描述 這題是 Hard 的題目，難度在於，要如何處理以下問題： 碰到括號怎麼進行優先處理 括號前面的“-”號會改變括號內的數字正負，並且要與括號外的數字相加 2 解法 首先一個很重要的概念是，我們要如何處理括號的問題，這邊我們會使用到三個變數： sign：用來記錄當前的正負號，初始值為 1，通常用來記錄數字前一個符號是正還是負。 res：用來記錄當前的結果，初始值為 0，通常是用來記錄左括號之前的加總數字。 num：用來記錄當前的數字，初始值為 0，通常是當前括號內的數字總和。 因此我們所使用的公式如下： 在了解公式之後，我們要有一個邏輯處理當碰到左括號 和 右括號的流程。 當碰到左括號 我們要記錄當前的 res 和 sign先放到 stack 裡面，並且重新設定 res 和 sign 為 0 和 1。 然後優先處理括號內的數字，直到遇到右括號。 當碰到右括號 當前的 res 是括號內的加總數字 括號的前一個符號，也就是在 stack 裡面的 sign 會決定括號內的數字是正還是負。 因此我們會將括號也就是當前的 res 和 stack 的sign 取出來並 ...

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 ...