LeetCode 刷題知識總整理
前言這篇用來記錄刷leetcode 的各類主題，以及不同情境下要用的對應解題策略是哪些，也連接到之前所做的筆記跟部落格 Roadmap 這邊是參考 NeetCode 官網的roadmap 按照不同主題進行刷題的 Big-O https://www.bigocheatsheet.com/ Two PointersTwo pointer 如果出現在陣列題目中，代表兩個索引(index)，如果出現在 Linked List題目中，代表兩個不同的指標。但核心目的都是一樣的，透過移動pointer位置來減少溶於計算提高效率。 常見的Two pointer類型： 反向指針: 一個指向頭部一個指向尾部，逐漸向中間靠攏，檢查回文, 兩數之和通常很常用這種類型 快慢指針: 一個指針較快，另一個指針較慢，可以用於檢測Linked List 中是否有環。 某些情況下會搭配 Sliding Windows 來去動態調整子陣列的大小，Ex.右指針擴展Windows，左指針收斂windows。以下整理常見的 Two Pointer 使用時機： $O(N^2)$ 降低成 $O(N)$,題目要求降...
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 ARP DHCP VLAN SDN Configuration ..etc Linux Basic Commands Filesystem Hierarchy Standard Permi...
刪除 BST 當中的節點 | Medium | LeetCode#450. Delete Node in a BST
題目敘述 題目難度： Medium 題目敘述： 題目給定一個 BST 的 root 跟整數 key，請刪除給定的 key node 並回傳 root 刪除行為可以分成兩階段: 找到要被刪除的節點 如果節點被找到，那就刪除該節點 解法一開始的想法題目提示的很清楚，刪除行為分成兩階段，(1) 找到節點 (2) 刪除節點。重點會是刪除節點後，要怎麼接回原先的 BST。所以可以分成兩個問題對應處理:(1) 找到節點: DFS Traversal(2) 刪除節點，並接回原先的 BST: 可以細分成幾種處理狀況 - 要被移除的節點，左右子樹都存在: 這時候如果把當前節點移除，那可以選擇把: 恰好比當前節點大 或者 恰好比當前節點小 的節點移動到目前節點，做為新的 root。 - 要被移除的節點，只有左/右子樹都存在: 刪除當前節點，然後以左/右子樹做為新的 root 至於要找恰好比當前節點大，可以回想一下 BST 的性質，對於任意節點而言 $leftNode < root < rightNode$ 因此，要找當前節點右子樹的最左下角的節...
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(暫存區)是一個臨時空間，可以讓你暫時將工作目錄的變更添加到暫存區，等待進一步提交，所以當你進行 git add 的時候，檔案就會從工作目錄轉移到暫存區。最終當使用 git commit 的時候，Git 就會將暫存區內容提交到 ...
合法括號字串 | Medium | LeetCode#678. Valid Parenthesis String
題目敘述 題目難度: Medium 題目敘述: 題目給定一個字串 s 包含三種可能的字元: (, ) 以及 *，若 s 為Valid 請回傳 true 否則為 false 下面是判斷 s 是否合法的規則: 任何 ( 都需要有對應的 ) 才能閉合 任何 ) 都需要有對應的 ( 才能閉合 ( 需要出現在 ) 之前才可閉合 * 可以代表 (. ) 或者是空字串 "" 解法這題跟單純的括號閉合題型不太一樣的是，多了一個變因 * ，它可能是左括號也可能是右括號，因此我們會需要追蹤這種可能性 我的解法123456789101112131415161718192021222324252627282930class Solution {public: bool checkValidString(string s) { int leftMin = 0; int leftMax = 0; if(s.size()==1 && s[0]!='*') return false...
Pow(x, n) | Medium | LeetCode#50. Pow(x, n)
題目敘述 題目難度：Medium 題目描述：題目要求實現常見的 pow 函數，正常來說 pow(x, n) 就會回傳 x 的 n 次方的結果。 而題目有給下面限制: -100.0 < x < 100.0 -231 <= n <= 231-1 n is an integer. Either x is not zero or n > 0. -104 <= x^n <= 104 解法我的解法原先的方法會 TLE，原先這種逐項去乘會有溢位風險，如果次方給很大，Ex. x = 2.0, n = -2147483648 => 保證TLE 1234567891011121314151617181920212223242526class Solution {public: double myPow(double x, int n) { double ans; if(n == 0) return 1; else if(x==1) return x; ...
基於時間的鍵值對儲存 | 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 值。若沒有值，則回傳 "" 解法我的解法123456789101112131415161718192021222324252627282930313233343536373839404...
尋找 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>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<v...
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); //store the frequency of each number for(int n: nums){ numCount[...
任務排程器 | Medium | LeetCode#621. Task Scheduler
題目敘述 題目難度：Medium 題目描述：題目給了一個陣列 tasks 裡面有許多不同中類的任務要丟給CPU執行，任務種類有 A~Z，每個 CPU Interval 可以選擇執行完成一個任務或者空閒。任務可以以任何順序執行，但有個條件 任何兩個相同種類的任務，執行時需要相隔 n 個 intervals ， 請回傳完成所有任務時，CPU所需的最少 intervals。 解法一開始的想法一開始比較偏向暴力去解，就是宣告一個 hash table 來儲存每個任務類型的剩餘等待間隔為多少，透過遞迴去找最小intervals 解，但這樣容易 TLE，並且這樣的做法沒有考慮到 到底要不要放idle 這件事。 12345678910111213141516171819202122232425262728293031323334353637class Solution {public: unordered_map<char, int> taskCount = { {'A',0},{...