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

前言 這裡是我寫Leetcode總結核心概念的地方，不同的情境會使用到的武器不同，這裡我會描述在什麼樣的情境滿足下，適合的資料結構或是演算法。而這個演算法的核心概念是什麼，同時我也會紀錄一些我在刷題時的心得，以及刷題的時間，來慢慢看到成長與進步。 Leetcode時間紀錄 Hash Table 情境1: 快速找元素 通常使用 Hash 的關鍵在於要用 O(1) 的時間複雜度來查找元素，這樣就可以不用遍歷整個 list 從 O(n) 變成 O(1) 的時間內完成整個問題。 相關題目： leetcode-1-two-sum: 給定一個 target 數值，從 list 中找到兩個數字相加等於 target leetcode-12-integer-to-roman: 整數轉羅馬數字 leetcode-13-roman-to-integer: 羅馬數字轉整數 情境2: 比對無序的東西 如果要比對兩個無序的東西，像是兩個字串是否是 Anagram，這時候可以使用 Hash 來記錄每個字元出現的次數，然後比對兩個 Hash 是否相同。 相關題目： leetcode-49-group ...

1 題目描述 檢查一個數獨是否合法，合法的數獨滿足以下條件： 每一行的數字都是1-9，且不重複 每一列的數字都是1-9，且不重複 每一個3x3的小格子裡的數字都是1-9，且不重複 注意：不用檢查數獨是否有解，只需要檢查數獨是否合法。 2 解法 其實思路很簡單，我們看到需要滿足的三個條件，就可以分別實現這三個條件的檢查函數，然後分別檢查即可。 但是在這之前你會發現這三個條件都有個共通點就是數字不重複，所以我們可以針對此設計一個不重複的檢查函數。 不重複 透過set的特定把重複的移除，然後比較移除"."後的長度是否相等即可。 1234def check_unique(nums): # 移除'.'的數組 nums = [num for num in nums if num != '.'] return len(set(nums)) == len(nums) 檢查row 12345def check_row(board): for row in board: if not check ...

1 題目描述 會提供words跟s，要求找出s中所有words的連續子串的起始索引。 2 解法 2.1 一個個慢慢找 我們從i=0開始檢查，取s[i:i+word_len]叫做word（圖片橘色部分） 有一個word_dic負責紀錄要求，也就是words中的word的數量 有一個seen負責紀錄已經看過且是word_dic的word，可以用來與word_dic比較判斷當前的window是否滿足狀況 擴展window的條件： 基本上擴展window的時機點是透過count的移動來移動window，但是何時要移動count呢？ 當前的word是合法的條件？ 當前的word是word_dic中的word 當前的seen[word]小於word_dic[word] word 合法之後要做哪些工作？ count要+1，count用來計算start的位置以及判斷是否滿足word_dic的數量要求 紀錄i的時機 當我們發現滿足count等於len(words)時，代表我們找到了一個合法的window，這時候要紀錄i的位置 因為count只會在word合法的時候+1， ...

1 題目描述 找到一個subarray的和大於等於target，並且這個subarray的長度是最小的。 subarray是指連續非空的元素。 題目要求時間複雜度為O(N)。 2 解法 因為要找出最小長度，基本上就是找到一組window大小為最小，但是同時滿足>=target的條件。因為nums是無序的，所以一定是要遍歷一次，因此時間複雜度是O(N)。 老樣子，Sliding Window 就是需要定義出以下狀況： 何時停止擴展？ 我們希望當前的window >= target時，停止擴展 在還沒超過target之前，我們會一直擴展window right 指針會一直往右移動 處理當前window的時機？ 因為接下來我們要開始收縮window找找看有沒有更小的window 計算當前window的總和數，以及當前window的長度是否有小於最小長度 何時收縮window？ 如果發現當前window的總和數 >= target，就開始收縮window 移動left指針，並且更新當前window的總和數 當當前window的總和數 < target ...

前言 之前一直想用，但中途都會失敗，今天終於成功了！這篇文章主要是記錄如何在Hexo的文章中嵌入日曆。 步驟 1. 安裝插件 1npm install --save git://github.com/howiefh/hexo-generator-calendar.git 2. 下載並修改js檔案 下載以下兩個檔案 calendar.j languages.js 我自己是保存到source\self\目錄底下： 接下來修改js檔案添加以下內容在最後底部的部分 123$(document).ready(function () {$("#calendar").aCalendar("zh-TW");}); 注意如果你有兩個版本的切換，是按照這篇文章Hexo - Butterfly 版本的語言切換功能設置。 js檔案要存放在source-en\self底下，並且我們要修改兩個地方： 3. 設定_config.yml 前往config-butterfly.yml，按照順序添加以下內容： 一定要下載jquery，不然日曆會無法顯 ...

1 題目描述 這題很easy，就是要找出s是否為t的subsequence。 2 解法 我的想法一開始很簡單，two pointer從同一個起點0出發，如果相同，兩個pointer都往下走一步，如果不同，只有t的pointer往下走一步。如果s的pointer走到底，表示是subsequence，否則不是。 12345678class Solution: def isSubsequence(self, s: str, t: str) -> bool: i, j = 0, 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s) 有另一個寫法也很特別，我以s為主，for迴圈iterate每個char在s裡面的。然後去判斷char是否在t裡面，如果有，就找出該char在t的位置idx，然後t變成t[idx+1:]，因為t[:idx]之前已經 ...

1 題目描述 找到所有可以使三個數字的和為零的不重複組合。 2 解法 看到不重複，腦子第一個冒出來是set。應該要把所有的組合都放進去，然後再轉成list。 而這題是two pointer卻要找3個數字的和為0，而two pointer使用的前提最好是==排序==過的數組。我們可以透過固定一個數字，然後使用two pointer的方式找到另外兩個數字。 2.1 Hash Set 12345678910111213141516171819202122232425262728293031323334==== Step 1 ====# nums 排序過# i 是固定的數值# l, r 分別是 left pointer 和 right pointer[-4,-1,-1,0,1,2] i l r# 因為還太小，我們透過移動l來使總合變大nums[i] + nums[l] + nums[r] = -3==== Step 2 ====[-4,-1,-1,0,1,2] i l r# 因為還太小，我們透過移動l來使總合變大nums[i] + nums[l] + nu ...

1 題目描述 給定一個非負整數的數組height，每個元素代表一個垂直線，並且每個線的寬度都是1。找出兩條線，使得他們和x軸組成的容器可以容納最多的水。 （注意不可以傾斜容器） 2 解法 2.1 暴力解法 這題的暴力破解是O(N)基本上就是遍歷所有的組合，找出最大的容器。 12345678class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) ans = 0 for i in range(n): for j in range(i+1, n): ans = max(ans, min(height[i], height[j]) * (j-i)) return ans 2.2 Speed O(N) 從知道這是two pointer的時候就要有個認知，那就是某種程度上他是有序的，這個案例有兩個變數，在計算面積 = 距離(指標距離) * 高度(min指標值)，我們知道，距離最大 ...

1 題目描述 從numbers裡面找出兩個數字，使得他們的和等於target，並且返回這兩個數字的索引，且索引是從1開始。 這個題目要求空間複雜度為O(1)，因此我們不能使用hashmap。 2 解法 2.1 暴力解法 最純的暴力破解法，就是O(N^2)遍歷所有的組合，找出符合條件的組合。 1234567class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: n = len(numbers) for i in range(n): for j in range(i+1, n): if numbers[i] + numbers[j] == target: return [i+1, j+1] 2.2 Speed O(N) 這題的關鍵是，我們該如何避免檢查那些不可能的組合？ 我一開始沒有立刻領悟出 numbers[right] + numbers[left ...

前言 今天想要深度的去了解Two pointer與sliding window 的使用，這也是面試常見的技巧。主要整理出『如何辨識要使用這些技巧』。 Two Pointer 那我們先從two pointer開始，因為sliding window其實是two pointer的一種特例，或是進階應用。 那麼什麼是two pinter呢？pinter 俗稱指標，指標用來儲存另一個物件的記憶體位置，通常在leetcode中，指標只是一個整數，用來指向陣列的某個物件索引。 12345678pointer = 0arr = [10, 30, 50, 70, 100] ^arr[pointer] = arr[0] = 10pointer = 3arr = [10, 30, 50, 70, 100] ^arr[pointer] = arr[3] = 70 Two pointer就是指向陣列的兩個指標，通常是指向陣列的頭尾，然後向中間移動，或是指向陣列的兩個不同位置，然後向中間移動。雙指標允許我們同時查看兩個不同的值，然後我們根據這兩個值的關係來決定下一 ...