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

1 題目描述 有一個linked list，要求將linked list中小於x的node放在前面，大於等於x的node放在後面。 2 解法 這題不難，可以直接使用兩個linked list，一個是小於x的linked list，一個是大於等於x的linked list，最後再將兩個linked list合併即可。 123456789101112131415161718192021222324252627282930class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: # 建立兩個虛擬頭節點，分別用於小於x的節點和大於等於x的節點 small_head = ListNode(0) large_head = ListNode(0) # 當前指針指向小鏈表和大鏈表的頭節點 small = small_head large = large_head ...

1 題目描述 給定一個鍊錶，將鍊錶向右旋轉 k 步，其中 k 是非負數。 2 解法 看到這個題目的時候，有想到如果今天k很大，這個linked list多少步驟會回到原本的樣子？基本上是當 k 是 鍊錶長度的倍數時，鍊錶會回到原本的樣子，因此我們可以先計算出鍊錶的長度，然後取餘數，這樣就可以得到我們要旋轉的步數。 當last.next是空的時候，表示觸底 12345678# 先計算長度last, count = head, 1while (last.next): count += 1 last = last.next# 重新計算k取餘數k = k % count 接下來如果k是2，代表最後面的兩個node會被擠到最前面，因此我們主要有兩個步驟： 找到last，把last跟head連接起來 找到新的head，把新head的前一個node的next設為None 12345678910# 找到last，把last跟head連接起來last.next = head# 找到新head的前一個node （從上圖例子為4)tmp = headfor _ in range(c ...

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