LeetCode 刷題知識總整理
前言這篇用來記錄刷leetcode 的各類主題，以及不同情境下要用的對應解題策略是哪些，也連接到之前所做的筆記跟部落格
Roadmap
這邊是參考 NeetCode 官網的roadmap 按照不同主題進行刷題的
Big-O
https://www.bigocheatsheet.com/
Two PointersTwo pointer 如果出現在陣列題目中，代表兩個索引(index)，如果出現在 Linked List題目中，代表兩個不同的指標。但核心目的都是一樣的，透過移動pointer位置來減少溶於計算提高效率。
常見的Two pointer類型：
反向指針: 一個指向頭部一個指向尾部，逐漸向中間靠攏，檢查回文, 兩數之和通常很常用這種類型
快慢指針: 一個指針較快，另一個指針較慢，可以用於檢測Linked List 中是否有環。
某些情況下會搭配 Sliding Windo ...
DevOps技能樹知識整理 |【筆記目錄】
前言這裡紀錄 DevOps 面試常見的知識點，主要是參考了這個 github repository: DevOps Exercises 和 ByteByteGo 的 GitHub Repo 所做的筆記整理
可能會花很久時間才能夠全部整理完成~
DevOps GeneralPython
Basic Data Types
OOP / Class
Raise Exceptions
Regex
Async
File Manipulation
OS
lambda
decorator
Flask
文章： Python for DevOps |【DevOps技能樹】
Networking
TCP/UDP
OSI Model
CIDR
Mac Addr.
CSMA/CD
NAT
DNS
ICMP
TLS/SSL Handshake
Route Table
...
Git for DevOps 筆記 |【DevOps技能樹】
Basic
Q:你要如何確認一個目錄是一個 git repository?
檢查是否有 .git 文件
Q:請解釋什麼是 git directory, working directory, staging area
Git目錄:適用於儲存項目歷史紀錄的地方。包含所有 commit history, branch, label 等資料，存放於專案目錄中的 .git 資料夾內。
Git 目錄其實就是負責管理版本的主要資料存放地，可以透過 git log 命令查看資訊
工作目錄目前正在操作的專案目錄。在工作目錄中，git 會去提取 Git 目錄中的某個特定版本(正常會是最新版本)，並將檔案提取出來，讓使用者可以直接編輯跟修改。
使用者對於工作目錄的變更並不會自動被 git 偵測，需要手動進行 add 以及 commit 進行更新。
Staging Area(暫存區)是一個臨時空間，可以讓你 ...
KoKo 吃香蕉 | Medium | LeetCode#875. Koko Eating Bananas
題目敘述
題目難度： Medium
題目描述：Koko 愛吃香蕉，今天有 n 堆的香蕉，第 i 堆香蕉的數量會是 piles[i]，香蕉由守衛看守，守衛目前不在，但他會在 h 小時候回來。Koko 每小時吃香蕉的速度會是 k，每一小時 Koko 會去挑選一堆香蕉吃，如果某堆香蕉的數量小於 k 則Koko 會將它們全吃掉，並且在那一小時中不會再去吃其他堆香蕉。雖然 Koko 吃的很慢，但是他還是希望在守衛回來前將所有的香蕉都吃完，為了達到這個目的，Koko 每小時吃香蕉的速度 k 最小會是多少？
解法一開始的想法一開始還在想要怎麼樣決定k，這裡可以透過 Binary Search 的方式去將不同堆的元素作為 k 去嘗試，嘗試的方式就是將每堆元素扣除 K 直到變成 0，同時記錄時數，只要最終時數小於 h 則回傳 k 值，只要最終時數大於 h 則繼續透過二元法找其他的 k
我的解法12345 ...
替換後的最長重複字元 | Medium | LeetCode#424. Longest Repeating Character Replacement
題目敘述
題目難度： Medium
題目描述： 給定一個字串 s 以及整數 k ，題目要求我們需要去將 s 中的任意字元替換成其他英文大寫字母，這樣的替換操作可以進行 k 次，在進行 k 次操做後，請回傳具有相同字母的最長的子字串
解法一開始的想法對於關鍵字，最長子字串，可以直接聯想到要使用 Sliding Window，但這題除了找到子字串之外，還需要透過 Hash Table 來去紀錄個別字母的出現頻率，同時在滑動窗口的同時需要紀錄最大長度。
我的解法1234567891011121314151617181920212223class Solution {public: int characterReplacement(string s, int k) { unordered_map<char, int> umap; ...
太平洋-大西洋水流 | Medium | LeetCode#417. Pacific Atlantic Water Flow
題目敘述
題目難度： Medium
題目描述： 有個大小 m x n 的長方形島嶼，它的邊界被太平洋與大西洋包圍。與太平洋交界的會是島嶼的上方以及左側邊緣，與大西洋交界的會是島嶼的下方和右側邊緣。島嶼被切分成許多網格單元，可以視為一個 m x n 大小的矩陣 heights，其中 heights[r][c] 代表座標 (r,c) 位置的海拔高度。 島上很常下雨， 只要當前單元格的海拔高度大於或等於其上下左右單元格的海拔高度，則雨水可以自由流向他的上下左右單元格。 雨水可以透過相鄰單元格一路流到海洋中。 題目要求回傳一個 2D 矩陣 result， 其中 result[i] = [r_i, c_i] 代表雨水可以從座標 (r_i, c_i) 同時流到太平洋與大西洋。
解法一開始的想法一開始覺得這題一樣會是 connected components 只是 connected 的條件變成只 ...
LRU 快取 | Medium | LeetCode#146. LRU Cache
題目敘述
題目難度： Medium
題目描述： 題目要求設計一套結構能夠滿足 [LRU(Least Recently Used) Cache])(https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU)
題目要求實踐 LRUCache class：
LRUCache(capacity): 使用 capacity 初始化 LRUCache 大小
int get(int key): 如果 key 存在，則返回對應的值，若不存在則返回 -1
void put(int key, int value): 如果 key 存在，則更新它的值，否則添加 key-value pair 到 cache。若 key 的數量車超出 capacity 大小，則逐出最近最少使用的Key
解法一開始的想法這題因為很偏系統設計，所以剛接觸的時 ...
包圍的區域 | Medium | LeetCode#130. Surrounded Regions
題目敘述
題目難度： Medium
題目描述： 給定一個 m x n 大小的 board，包含兩種字母 X 或者 O，目的是捕捉被包圍的區域：
Connected： 一個格子可以與相鄰的格子（水平或垂直）相連Region： 通過連接每個 O 格子來形成一個區域(Region)Surround： 如果一個區域的所有 O 格子都能被 X 格子連接，並且該區域中的 O 格子不在矩陣的邊緣上，則該區域被視為被包圍
題目要捕捉被包圍的區域， 將原始矩陣中所有被包圍的 O 替換為 X。 此操作應直接在原始矩陣上進行，無需返回任何值。
解法一開始的想法這題我一開始的想法有點偏掉，但這題的意思就是：
找出被包圍 Region 並將 Region 中的 O 換成 X
如果 Region 有接到矩陣邊緣，則不替換成 X
這樣依舊會需要先透過 DFS 或者是 BFS 來先去走訪 connect ...
有效的數獨 | Medium | LeetCode#36. Valid Sudoku
題目敘述
題目難度： Medium
題目描述： 給定一個 9 x 9 大小的數獨 board 請確認該數獨是否是有效的。
只有當被填入數字滿足下面條件，數獨才會是有效的:(1) 每一列只包含非重複的數字 1-9(2) 每一行只包含非重複的數字 1-9(3) 共9個 3 x 3 的子方格, 每個子方格中的數字 1-9 都不重複
解法一開始的想法想法就偏向暴力解，首先就是要迭代 board 中每一列，看數字是否重複，這時可以用一個 unordered_set 去儲存數字，並在每一格檢查數字是否重複，如果重複就回傳 false，接著迭代每一行檢查是否重複。每次換行換列 unordered_set 都要清空為的是保存新的一行/列的數字。 最後就是需要迭代 9 個 3*3 大小的子方格，如果重複就回傳 false 函數最後代表檢查完畢，回傳 true。
我的解法12345678 ...
腐爛中的橘子 | Medium | LeetCode#994. Rotting Oranges
題目敘述
題目難度： Medium
題目描述： 給定一個 m x n 大小的矩陣叫做 grid ，其中每一格可能會這三種值其中一種： (1) 0 代表那格是空的 (2) 1 代表新鮮橘子 (2) 2 代表腐爛橘子。每分鐘在腐爛橘子四周的(上下左右)其他新鮮橘子都會腐爛，請回傳整個 grid 中所有新鮮橘子都腐爛最少需要幾分鐘，如果不可能全都腐爛，則回傳 -1
解法一開始的想法我原先認為這題就是要將腐爛橘子作為搜尋起點，然後BFS走訪附近的新鮮橘子，並且計算距離，每多走一格就會變成腐爛橘子，最後回傳最小距離就好。但後來發現這樣不符合題意，因為題目的要求是每一分鐘腐爛過子四周的新鮮橘子也會變腐爛，原先的做法會忽略了 「一輪 BFS 表示一分鐘」的關鍵邏輯。 腐蝕的時間應該是按 層數來計算，而非單純依照單一節點的距離。並且在BFS結束後，可能還是會有新鮮橘子存在(可能是分隔在其他cell中) ...