陣列中第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]>minHeap.top()){ minHeap.pop(); minHeap.push(nums[i]); ...
字流中第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>, greater<int>> minHeap; KthLargest(int k, vector<int>& nums) { ...
旋轉圖片 | Medium | LeetCode#48. Rotate Image
題目敘述 題目難度: medium 題目敘述: 題目給定一個 matrix 請將其順時針旋轉一次,並且必須 in-place修改,也就是不能宣告額外二元陣列去儲存元素 解法一開始的想法這題我是畫圖直接看矩陣關係 首先其實觀察 matrix 再經過一次順時針旋轉後的位置,然後比對原本的,可以發現一些關係。旋轉的過程也只是列元素變成行元素,可以觀察到 123- matrix[0][0] = matrix[0][2]- matrix[1][0] = matrix[0][1]- matrix[2][0] = matrix[0][0] 透過上面關係可以發現, 順時鐘旋轉一次,其實只是先將 matrix 相同 column 元素全部 reversed 排列後,再去進行對稱的過程。 我的解法 不過實際在解的時候,如果要對每一個 column 元素進行反序排列,會橫跨不同子陣列的元素交換,處理上比較不直觀, 因此我發現其實也可以先反序排列同一列元素再進行對稱,只不過這樣的結果會是原本 matrix 逆時針轉一次,但是其實逆時針轉三次就等於順時針轉一次。 1234567891011...
旋轉陣列 | Medium | LeetCode#189. Rotate Array
題目敘述 題目難度:Medium 題目描述: 題目給定一個整數陣列,請旋轉該陣列元素到右邊 k 次,其中 k 為非負整數 這裡的陣列會是一維陣列,旋轉的意思是尾端元素移動到首端,其餘元素跟著連帶移動。 解法一開始的想法我首先觀察到 k 的範圍會是 0 <= k <= 10^5 因此會需要對 k 取餘數看最少旋轉幾次。另外就是旋轉的方法,最直觀就會是透過迴圈把尾端元素不斷往首端放,但是 nums.length 範圍挺廣,這樣不停移動剩下元素,時間複雜度會到 $O(n^2)$ 肯定會 time limit exceeded。 我想到另一個方法,就是找插入點,看題目給的測資可以發現,旋轉幾次其實只是取末端元素數量不同而已,然後再把末端整組元素接回首端,就能夠完成旋轉。 我的解法123456789101112131415161718class Solution {public: void rotate(vector<int>& nums, int k) { int n=nums.size(); ...
BST的最小共同祖先(LCA) | Medium | LeetCode#235. Lowest Common Ancestor of a Binary Search Tree
題目敘述 題目難度:Medium 題目描述:給定一個BST, 求在BST內任意兩節點的最小共同祖先,其中自己可以是自己的祖先,求任意兩節點 p, q 的LCA 解法一開始的想法首先一定是先 traversal 查找 p, q 兩節點,而我的想法是,如果用 post-traversal 來走訪測資一,這樣對於任意兩節點,假設是 3,或是 5 這兩個元素的 caller(當前遞迴節點) 會是 4,而對於 5 或是 7 這兩個的caller會是節點 6。因此其實就是要找同時具有 p跟q節點返回值的那層 caller 就會是 LCA 我的解法123456789101112TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr) return nullptr; if (root == p || root == q) return root; TreeNode *leftNode = lowestCommonAncestor(r...
車隊 | Medium | LeetCode#853. Car Fleet
題目敘述 題目難度:Medium 題目描述: 本題給定 n 個車輛,其中每輛車需要抵達到終點位置 target,第 i 輛車的位置為 position[i] 第 i 輛車的速度為 speed[i],題目中有個規定 輛車不得超越另一輛車,只能保持相同速度行駛,也就是說如果後車比前車快,那後車只能降速,降到與前車同等速度一同行駛,這樣就形成一個兩輛車行駛的車隊,題目中另外還有說明,單獨一輛車也算是車隊的一部份,題目最終要求,請計算共有多少車隊會抵達終點。 解法一開始的想法核心想法我覺得是首先, 要能夠記錄每輛車當前的位置 ,並且會需要知道每輛車速度與位置之間的關係。但我一開始的想法比較複雜,就是用 pair 或 hasp table 紀錄車輛當前位置跟速度,每一小時就更新車輛位置跟速度,一旦有車隊抵達終點後就不再更新那幾輛車,但這樣可能會有多重迴圈,並且需要額外紀錄是否抵達終點。 我的解法12345678910111213141516171819202122232425class Solution {public: int carFleet(int target, ...
螺旋矩陣 | Medium | LeetCode#54. Spiral Matrix
題目敘述 題目難度:Medium 題目描述: 給定一個 m x n 的 matrix,請以螺旋順序回傳 matrix 內的所有元素 看題目的範例應該是要用順時鐘方向然後由外而內來螺旋 解法一開始的想法一開始看到,想說應該要能夠用遞迴方式來逐一存取特定的格子,可能指定 row 跟 column 然後要想某種方式來每次都跑完一層後轉向,但我後來發現這樣的判斷方式會太複雜,因為我原本的想法是每一層遞回要跑一個螺旋邊 (Ex. 最上層的元素依序存入輸出vector) 但這樣遞迴終止條件會太複雜,用來控制轉向的參數也會太多。 後來改成將四個螺旋邊的存取放在相同的遞迴中,螺旋到內圈時才會進到下一層遞迴。 我的解法123456789101112131415161718192021222324252627282930313233class Solution {public: vector<int>output; void helper(vector<vector<int>> & matrix, int top, i...
開箱+基本設定 | 入坑 Meshtastic 開源專案 | Meshtastic 系列
🔋 基本介紹: https://hackmd.io/@BASHCAT/S1m_x-AOA/%2FUAmGpkIzQy-Fc5xKmcyBtQ🔋 Official Web Page: https://meshtastic.org/docs/about/🔋 Useful Videos: https://youtu.be/6hW40yaj3x4?si=rGFPADhNIWfiZnL8 https://youtu.be/x99R78fkSg0?si=cU1XbtR8HUWploHr 🔋 FB- 臺灣鏈網 https://www.facebook.com/groups/meshtastictw/about🔋 Reddit 討論串 https://www.reddit.com/r/meshtastic/ 什麼是 Meshtastic?基於 LoRa 的無線通訊技術的開源專案,可以透過LoRa相關設備透過 LoRa 協定進行低功耗遠距離的無線訊號傳輸,並且不仰賴現有的行動通訊架構,適合類似 緊急備援用的通訊系統,或是山區救援通訊。 藉由 Meshtastic 節點,...
鏈結串列排序 | Medium | LeetCode#148. Sort List
題目敘述 題目難度:Medium 題目描述:給定一個 Linked List 的 head 請將這個 list 進行升階排序 (由小排到大) 解法一開始的想法一開始有想到比較蠢的方法,就是把先在的節點對應到記憶體位址可能存到一個hasht table 之類的,然後把key額外存成陣列進行排序後再建立另一個 linked list。 但後來想要用題目的 follow up條件來做看看,也就是時間複雜度要 $O(nlogn)$ 然後空間複雜度要 $O(1)$ 但這空間複雜度 $O(1)$ 基本上就代表只能在原本的 list 上進行操作,然後時間複雜度 $O(nlogn)$ 就代表應該是要用 quick sort 或者 merge sort 之類的方式來對 linked list中的節點進行排序。 我原先想說可以用 quick sort 但 quick sort 比較適合對 Array 做排序,原因一:Linked Listed 不能夠 random access,存取第 n 個元素就真的要從頭走到第 n 個節點。第二個原因就是做partition 很困難,因為每次切完partit...
排序陣列轉換成 BST | Easy | LeetCode#108. Convert Sorted Array to Binary Search Tree
題目敘述 題目難度: Easy 題目敘述: 給定一個已排序的陣列 nums (升階排序),請將其轉換為 height-balanced BST Height-based BST: 其實就是左右子樹高度差距小於等於 1 。參考連結 解法一開始的想法太久沒刷題,回來從 Easy 開始刷,這也是第一次刷 Divide and Conquer 類別的題目,但這個概念很常用到,一開始以為跟 Quick Sort 很像,就是選pivot 比它大就放在右子樹,比它小就放到左子樹,但後來發現這想法有問題,因為 Quick Sort 會是要去做排序,這裡則是建構子樹。 回憶BST的特性,對於任意root,左子樹小於 root ,而root小於右子樹, 因此這題的重點會是要怎麼選擇 ROOT 這樣依序遞迴建構才會是 height-balanced BST 這常來說就會是要往中間找,建立出的 BST才會相對平衡。 我的解法123456789101112131415161718192021222324252627/** * Definition for a binary tree node....














