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

題目敘述 題目難度: 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 元素進行反序排列，會橫跨不同子陣列的元素交換，處 ...

題目敘述 題目難度：Medium 題目描述： 題目給定一個整數陣列，請旋轉該陣列元素到右邊 k 次，其中 k 為非負整數 這裡的陣列會是一維陣列，旋轉的意思是尾端元素移動到首端，其餘元素跟著連帶移動。 解法一開始的想法我首先觀察到 k 的範圍會是 0 <= k <= 10^5 因此會需要對 k 取餘數看最少旋轉幾次。另外就是旋轉的方法，最直觀就會是透過迴圈把尾端元素不斷往首端放，但是 nums.length 範圍挺廣，這樣不停移動剩下元素，時間複雜度會到 $O(n^2)$ 肯定會 time limit exceeded。 我想到另一個方法，就是找插入點，看題目給的測資可以發現，旋轉幾次其實只是取末端元素數量不同而已，然後再把末端整組元素接回首端，就能夠完成旋轉。 我的解法123456789101112131415161718class Solution {p ...

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

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

題目敘述 題目難度：Medium 題目描述： 給定一個 m x n 的 matrix，請以螺旋順序回傳 matrix 內的所有元素 看題目的範例應該是要用順時鐘方向然後由外而內來螺旋 解法一開始的想法一開始看到，想說應該要能夠用遞迴方式來逐一存取特定的格子，可能指定 row 跟 column 然後要想某種方式來每次都跑完一層後轉向，但我後來發現這樣的判斷方式會太複雜，因為我原本的想法是每一層遞回要跑一個螺旋邊 (Ex. 最上層的元素依序存入輸出vector) 但這樣遞迴終止條件會太複雜，用來控制轉向的參數也會太多。 後來改成將四個螺旋邊的存取放在相同的遞迴中，螺旋到內圈時才會進到下一層遞迴。 我的解法123456789101112131415161718192021222324252627282930313233class Solution {public: vec ...

🔋 基本介紹： 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 的無線通訊技術的開源專案 ...

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

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

題目敘述 題目難度：Medium 題目描述： 給定一個整數陣列 temperatures 代表每天的氣溫，請回傳一個陣列 answer，answer[i] 代表你必須再等 i-th 天才能夠獲得一個更溫暖的天氣，如果接下來幾天的天氣不可能變更溫暖，則 answer[i] == 0。 解法一開始的想法我一開始的想法會是，如果隔天溫度比今天溫度低，則將氣溫丟入 Stack 中，但是這樣會有問題，你要額外紀錄當初第一個push進入 stack 的 Index 這樣再回傳陣列的時候才能夠知道從哪個 index 會隔多少天才能夠溫度提升。 這樣不如直接用 Stack 紀錄 index 本身。 我的解法123456789101112131415161718class Solution {public: vector<int> dailyTemperatures(vect ...

題目敘述 題目難度: medium 題目敘述: 在這個問題中，Tree是一個無向圖，它是Connected的且沒有環。給定一個圖，它最初是一棵包含 n 個節點（標記為 1 到 n）的樹，但後來新增了一條額外的邊。這條新增的邊連接了從 1 到 n 中選擇的兩個不同的節點，且這條邊之前並不存在於樹中。這個圖由一個長度為 n 的陣列 edges 表示，其中 edges[i] = [a_i, b_i] 表示在圖中節點 a_i 和 b_i 之間存在一條邊。題目要求 返回一條可以被移除的邊，使得剩下的圖仍然是一棵包含 n 個節點的樹。 如果有多個答案，請返回輸入中 最後出現的那條邊。 解法一開始的想法一開始的想法想說，只要按照原先找 Connected Components 的思路，在 Adjacency List 找鄰居的時候，如果找回到已經造訪過的點，那就會是有迴圈，則該edge 是可被移除的 ...