Two Pointers

19. Remove Nth Node From End of List

19. Remove Nth Node From End of List 這一題我的第一個想法是我先走一趟算出整個 Linked List 有多長,接著我把所有的長度減去 n ,這就代表我需要從起點往下走幾步。 不過此時我們需要借助一個虛擬節點,虛擬節點的下一個點才是起點,並且從虛擬起點開始往下走,直到走到了要被刪除的點的前一個點,這時候我們就把需要刪除的節點刪掉。 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
Gary Lai

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters 這一題其實是可以透過暴力解法想辦法算出來的,那就是窮舉出所有的子字串,並且檢查每一個子字串有沒有重複的字元。時間複雜度約為 $$O(n^3) $$ 。 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: def check(start, end): chars = defaultdict(int) for i in range(start, end + 1): c = s[i] chars[c] += 1 if chars[c] > 1: return False return True
Gary Lai

438. Find All Anagrams in a String

483. Find All Anagrams in a String 1. 我們需要想的是窗口增大的時候,需要更新哪些資訊? 2. 如果 char 在目標內,增加計數 3. 如果 char 的計數已經達到目標的計數,valid 加一 4. 何時要收縮窗口? 5. 如果窗口的字串的長度已經大於目標的字串(因為我們要找的是 permutation) 6. 收縮窗口時,需要更新哪些資訊? 7. 檢查左邊的指針的字元在目標內 8. 如果 char 的計數已經達到目標的計數,valid 減一 9. 如果 char 在目標內,減少計數 10. 最終結果要在「擴大窗口」時更新還是「收縮窗口」時更新? 11.
Gary Lai