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

🔋 基本介紹： 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....

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

題目敘述 題目難度: 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 是可被移除的。 這樣的想法沒錯，但實際執行時卻會碰到 DFS 遍歷順序的問題，例如測資 [[1,2],[1,3],[2,3]]，當加入 edges[2] = {2,3} 時，會形成一個...

題目敘述 題目難度：Medium 題目描述： 給定一張圖中有 n 個節點，以及一個陣列 edges 其中 edges[i] = [a_i, b_i] 代表從節點A到節點B存在 Edge，本題要求回傳這個圖紹 Connected Components 的數量。 解法一開始的想法由於題目給得是 edge 的陣列，可以由此陣列去建構出一個 n x n 的鄰接矩陣，如果矩陣中有值就為 true 開始針對已經有 true 的節點進行 DFS 然後每次返回到 Caller 時就讓某變數 sum 增加一，最後再回傳 sum 即可，就代表 Connected Components 的數量。 但 n x n 的鄰接矩陣，如果想要去選取出發點，勢必須要透過雙重迴圈來尋找，只要 n 夠大就會 Time Limit Excced，因此改良做法是改成鄰接串列（Adjacency List） 我的解法1234567891011121314151617181920212223242526272829303132333435class Solution { public: ...

題目敘述 題目難度: medium 題目敘述: 題目給定一個整數陣列 nums 包含了 n+1 個數字，每個數字範圍為 [1,n] ，在 nums 只會有一種數字重複，請回傳是哪個數字重複。 這題要求只能使用常數空間，並且不能夠修改 nums 本身 解法一開始的想法這題規定只能使用常數空間，就代表要用時間換空間，基本上陣列或是 unordered_set 這種額外樣保存 n筆陣列資料的方式都不能用了，另外如果直接使用雙重回圈暴力解應該也會 TLE，因此這裡需要別的做法 解法1234567891011121314151617181920212223242526class Solution {public: int findDuplicate(vector<int>& nums) { int left = 1; int right = nums.size()-1; while(left < right){ int mid = left + (right...

前言要能夠確保像是有先修微積分，才能修工程數學，這種 有前後關係的圖論問題，通常會用 拓樸排序(Topological Sort) 利用 DFS 尋找 Strong Connected Components(SCC)Strong Connected Components (SCC) Vertex 之間有雙向的 Edge 相連，例如 從 vertex(A) 走到 vertex(B) 同時 vertex(B) 也要有 edge 連到 vertex(A)，就會說這兩個vertex 是 strongly connected 的。 通常可以透過多次的 DFS 來確定 Directed Graph 中有哪些 Strongly Connected Components ， 要進行多次DFS的原因在於，只有一次DFS 可能沒辦法識別出全部的 COnnected Components，根據搜尋起點的不同，有可能也會將不同。每次在查找 Connected Components 的時候都會各自有 Depth-First Search Tree，根據不同的搜尋起點選擇，可能會形成一個大棵的Dept...

題目敘述 題目難度： Medium 題目描述： You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.Return true if the edges of the given graph make up a valid tree, and false otherwise. 解法一開始的想法這題會是一個無向圖要判斷有沒有 Cycle，由於是無向圖判斷Cycle，因此可以透過 DFS來去看能不能形成一個 DFS Tree，如果不行那就是會有Cycle。另外這題給的邊形成的陣列，也會需要額外處理變成鄰接串列進行處理。 我的解法12345678910111213141516171819202122232425262728293...

題目敘述 題目難度： Medium 題目描述： 總共有 numCourses 課程需要上，他們被標注為 0 - numCourses-1，給定一個陣列 prerequisites 其中 prerequisites[i] = [a_i, b_i] 代表你需要先上過 b_i 課你才夠去上 a_i 課程。舉例來說，[0,1] 代表你需要先上課程 1 才能夠去上課程 0，請以陣列形式回傳上完所有課程的休課順序，如果沒辦法完成請回傳空陣列。 這題基本上是接續 LeetCode-207 Course Schedule，只不過上一題是判斷能否修完課，這題是要把修課順序印出來 解法一開始的想法不能修完課的狀況就是同時存在 [0,1], [1,0] 因為順序就反了，會在Graph中構成 Cycle， 因此如果這是有向無環圖(DAG) 則可透過 topological sort 印出依序走訪完全部課程的路徑，如果有cycle 就回傳空陣列。 我的解法123456789101112131415161718192021222324252627282930313233343536373839404...