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(暫存區)是一個臨時空間，可以讓你 ...
基於時間的鍵值對儲存 | Medium | LeetCode#981. Time Based Key-Value Store
題目敘述
題目難度：Medium
題目描述： 題目要求設計一個 time-based 的 key-value 儲存結構，可以相同key可以儲存多種值並且對於相同Key可以有多個不同的timestamp，並且用戶可以透過特定 timestamp 獲取值
請實踐一個 TimeMap class:
TimeMap() 用於初始化物件
void set(String key, String value, int timestamp): 在給定 timestamp 條件下， 儲存 value 到對應到特定的 key 上
String get(String key, int timestamp): 回傳先前透過 set 函數儲存的值，並且請找出小於等於當前 timestamp 的timestamp。如果有多個值，請回傳具有最大但小於 timestamp 的 timestamp 值。若沒有值，則回 ...
尋找 K 對最小總和 | Medium | LeetCode#373. Find K Pairs with Smallest Sums
題目敘述
題目難度：Medium
題目描述： 題目給定兩個陣列 nums1 以及 nums2，兩者都以 non-decreasing order 排序，並且給定整數 k，題目要求你從兩個陣列中個取出一個整數，定義成 pair (u, v) 請找出 k 具有最小總和的 pair u1, v1), (u2, v2), ..., (uk, vk)
解法一開始的想法一開始的想法比較暴力一點，一共三步：
兩個陣列都各自迭代找出所有 pair 組合
定義 minHeap 和 comparator 來比較pair之間誰的總和比較小
pop k 次
123456789101112131415161718192021222324252627282930class Solution {public: vector<vector<int>> kSmallestP ...
Top k 個頻繁元素 | Medium | LeetCode#347. Top K Frequent Elements
題目敘述
題目難度：Medium
題目描述： 給定一個整數陣列 nums 以及整數 k 並回傳 nums 中 k 個出現最頻繁的元素，你可以以任意順序回傳答案
本題限制
1 <= nums.length <= 1051 <= k <= nums.length
解法一開始的想法看到這種前 k 個，k個最頻繁，十有八九最佳解會是用 priority queue 去解
我的解法1234567891011121314151617181920212223242526272829class Solution {public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> numCount(20001, 0 ...
任務排程器 | Medium | LeetCode#621. Task Scheduler
題目敘述
題目難度：Medium
題目描述：題目給了一個陣列 tasks 裡面有許多不同中類的任務要丟給CPU執行，任務種類有 A~Z，每個 CPU Interval 可以選擇執行完成一個任務或者空閒。任務可以以任何順序執行，但有個條件 任何兩個相同種類的任務，執行時需要相隔 n 個 intervals ， 請回傳完成所有任務時，CPU所需的最少 intervals。
解法一開始的想法一開始比較偏向暴力去解，就是宣告一個 hash table 來儲存每個任務類型的剩餘等待間隔為多少，透過遞迴去找最小intervals 解，但這樣容易 TLE，並且這樣的做法沒有考慮到 到底要不要放idle 這件事。
12345678910111213141516171819202122232425262728293031323334353637class Solution {public: ...
K個距離原點最近的點 | Medium | LeetCode#973. K Closest Points to Origin
題目敘述
題目難度：Medium
題目描述： 題目給定一個陣列 points 其中 points[i] = [xi, yi] 代表在X-Y座標軸中任意點的位置，給定整數 k 求 k 個最靠近原點(0,0)的點
兩點之間求距離公式： √(x1 - x2)2 + (y1 - y2)2
解法我一開始的想法會是因為求 k 個距離近的點，而距離近代表離原點數字小，因此要用 max Heap 來解，但是我希望在 maxHeap 中放入的會是座標本身，然後排序方式就用距離大小來排，因此會需要自定義 comparator
這邊關於使用 lambda 語法定義 comparator 可以參考這篇：https://notes.boshkuo.com/docs/C++/STL/priority_queue
我的解法12345678910111213141516171819202122232425cl ...
陣列中第K大的元素 | Medium | LeetCode#215. Kth Largest Element in an Array
題目敘述
題目難度：Medium
題目描述： 題目給定整數陣列 nums 以及整數 k，請回傳陣列中第 k 個大的元素。特別注意，會是需要由大到小第k個元素，並不是第k大的相異元素
解法我的解法12345678910111213class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.begin()+k); for(int i=k; i<nums.size(); i++){ if(nums[i]>minHe ...
字流中第K大的元素 | Easy | LeetCode#703. Kth Largest Element in a Stream
題目敘述
題目難度：Easy
題目描述： 你是某大學入學審核辦公室的人，你需要動態即時追縱所有申請裡面前 Kth 個高分的成績， 請設計一個 class，在具有參數整數 k，並在插入新成績後回傳第 k 高分的成績。 請實作 KthLargest class:
KthLargest(int k, int[] nums) 負責初始化整數 k 物件以及用來存放考試成績的陣列 nums
int add(int val) 負責添加新成績 val 到stream 並且需要再添加成績後回傳到目前為止第k個高分的成績
解法我的解法12345678910111213141516171819202122232425class KthLargest { public: int k; priority_queue<int, vector<int> ...