Kevin Liu's 部落格 || Technical || Travel

題目敘述 題目難度：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]); &#...

題目敘述 題目難度：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 題目敘述: 題目給定一個 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 題目描述： 題目給定一個整數陣列，請旋轉該陣列元素到右邊 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(); ...

題目敘述 題目難度：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 題目描述： 本題給定 n 個車輛，其中每輛車需要抵達到終點位置 target，第 i 輛車的位置為 position[i] 第 i 輛車的速度為 speed[i]，題目中有個規定 輛車不得超越另一輛車，只能保持相同速度行駛，也就是說如果後車比前車快，那後車只能降速，降到與前車同等速度一同行駛，這樣就形成一個兩輛車行駛的車隊，題目中另外還有說明，單獨一輛車也算是車隊的一部份，題目最終要求，請計算共有多少車隊會抵達終點。 解法一開始的想法核心想法我覺得是首先， 要能夠記錄每輛車當前的位置 ，並且會需要知道每輛車速度與位置之間的關係。但我一開始的想法比較複雜，就是用 pair 或 hasp table 紀錄車輛當前位置跟速度，每一小時就更新車輛位置跟速度，一旦有車隊抵達終點後就不再更新那幾輛車，但這樣可能會有多重迴圈，並且需要額外紀錄是否抵達終點。 我的解法12345678910111213141516171819202122232425class Solution {public: int carFleet(int target, ...

題目敘述 題目難度：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...

🔋 基本介紹： 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 題目描述：給定一個 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...

題目敘述 題目難度: 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....