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

題目敘述 題目難度: Easy 題目描述: 給定一個 linked list 的 head，希望整個 list 反轉，並且回傳反轉後的list 解法一開始的想法123456789101. 定義節點結構2. 建立 linked list3. reverseList()4. 建立暫存節點，用來存放下一個節點的位址，也需要站存上一個節點的位址4-1. 將下一個節點的位址鏈結到上一個節點4-2. 更新暫時存節點4-3 . 更新前一個節點4-4. 移動至下一個節點5. 更新初始節點指標6. 回傳初始節點指標 後來我發現 head 跟tail 其實可以不用各別分開處理 我的解法1234567891011121314151617181920/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head...

題目敘述 題目難度: Easy 題目描述: 給定一個 Linked List 的 head 以及想要刪除節點的數值 val，要我們移除list中所有等於 val 的節點，所以如果所有節點數值都等於 val 則結果會是一個 emptt list 解法一開始的想法123456781. 定義節點結構2. 建立 linked list3. removeElements3-1. 宣告暫存空間3-2 判斷是否是 Empty List3-3. 走訪整個List3-4. 判斷是否等於 val，如果等於:那就將前一個節點連接到後一個節點，並釋放記憶體以刪除 val 所在節點3-5 回傳head 這是看到題目後一開始的主要想法，並且一開始很天真的想說還需要考慮刪除節點在 Head, 中間 以及 Tail 三種狀況，實作後才發現其實只需要判斷頭跟其他地方就好，Tail 應該不用單獨拿出來處理。 我的解法12345678910111213141516171819202122232425262728293031323334353637/** * Definition for singly-li...

題目敘述 題目難度: Medium 題目描述: 如同圖中所述，題目中要求我們對一個 Single Linked List head 去實現一個刪除特定節點的函式，函式的輸入叫做 node，題目中有特別說明。 限制: node 不會是 head中的最後一個節點，並且我們並不能夠存取 head 中的第一個元素，也就是整個 List 的初始節點。 這題的刪除節點不需要釋放記憶體，僅需將前一個節點連接到 node 的後一個節點 在 Run 以及 Submit 的時候，題目會建好List 並且呼叫我們寫的function，來去進行測試，這題只需要專注在刪除節點的邏輯上就好 解法一開始的想法一開始我陷入了傳統刪除節點的做法當中，也就是已知初始節點的條件下去走訪每個節點，指到找到給定節點，再去執行刪除的邏輯。 傳統作法123456789101112131415161718192021222324Node* DeleteNode(Node* first ,Node* node){ Node* ptr= first; if (first == NULL) ...

鏈結串列(Linked List)介紹 Linked List 是一種常見的資料結構，其組成主要包含 資料 和 下一個節點的位址，因此構成節點與節點相互鏈結的結構，其中最後一個節點會指向到 NULL 這個位址。 我們實踐的主要方式還是透過 C 語言去操作，想要實現 Linked List 必須先透過 struct 來去先定義節點本身 Linked List 實踐定義節點1234typedef struct node{ int data; struct node *next;} Node; 上面定義了 node 這個結構，其中包含了整數資料 data， 代表節點本身存放的資料 以及struct 型別的指標，下一個結構相同節點的記憶體位址 next。並且此結構的宣告為 Node，方便我們後續宣告節點。 123Node *first_node;Node *current_node;Node *previous_node; 我們可以透過 Node 來去宣告三個指標，指向三個結構的記憶體位址，分別為 first_node, current_node, previou...

題目敘述 題目描述給定整數的陣列以及整數 target 值，請在陣列找到任兩元素相加等於 target，並且回傳元素的索引，另外對於每個輸入陣列只會有一組輸出答案。 解法-1: 暴力解首先一樣從暴力解開始，先有解法，後續再看要怎麼優化 123456789101112131415161718192021222324/** * Note: The returned array must be malloced, assume caller calls free(). */int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int i, j; // init return array int* results = (int*)malloc(2 * sizeof(int)); // i could not iterated to n-1, since every element is compared. for (i=0; i< numsSize-1; i++...

基本介紹雜湊表是一種 Key Value Mapping 的結構，可以用快速查找資料，相較於一般搜尋演算法的時間複查度 $O(Log n)$ 他時間複雜度會是 $O(1)$ 主要神速的原因是因為 Hash Function，如果先把 n 個數字儲存在 Hash Table 裡面，那如果要判斷這個數字 A 是不是已經被存在 Hash Table 裡面，只要先把這個數字丟進 hash function，就可以直接知道 A 對應到 Hash Table 中哪一格。 Hash Table 不適合使用的時機 資料有處理上的時間優先順序，這種比較適合 Queue (FIFO)的結構 如果資料想要被排序，那也不適合用 Hash Table https://www.reddit.com/r/learnprogramming/comments/29t4s4/when_is_it_bad_to_use_a_hash_table/ Hash Table 適合的使用條件 題目要求使用時間複雜度 $O(1)$ 的演算法來存取元素 最糟的狀況也有 $O(n)$ 時間複雜度 Hash Functio...

題目敘述 題目中有一個整數陣列 nums, 這個陣列是以排序的陣列，並且在這當中想要找到 target 這個元素的 index, 如果沒找到就回傳 -1。並且要求所實現的演算法其實時間複雜度為 $O(Log n)$ 解法我的作法123456789101112131415161718192021222324252627282930int search(int* nums, int numsSize, int target) { // init int i,mid=0,low=0, high=numsSize-1; // Binary search // 1. find lower index and high index according to the length of array // 2 calculate middle value // 3. update low and high value // 4. again calcuate the new middle value until derive the ...

甚麼是 Lambda URL ? 官方定義: 函數 URL 是 Lambda 函數專用的 HTTP(S) 端點。您可以透過 Lambda 主控台或 Lambda API 建立及設定函數 URL。當您建立函數 URL 時，Lambda 會自動為您產生不重複的 URL 端點。函數 URL 一旦建立，其 URL 端點便永遠不會變更。 函數 URL 端點的格式如下： 1https://<url-id>.lambda-url.<region>.on.aws 要特別注意的是，某些region並不支援使用 function URL，這時可能就要用老方法: API Gateway + Lambda Integration 存取控制在建立 function URL 的時候可以透過 AuthType 參數，來決定 Lambda 如何對 funcion URL 的請求執行身分驗證或授權 AuthType 選項: AWS_IAM : 　如果想讓已完成身分驗證的使用者或Role透過function URL 呼叫你的函數，就要選 AWS_IAM NONE: Lambda 不...

Amazon MQAmzon MQ 上有託管 Active MQ 這個訊息佇列的服務，近期有碰到問題是問說，要怎麼樣在 Amazon MQ 上做 Horizontal Scaling， 首先簡單解釋一下 Vertical Scaling 跟 Horizontal Scaling 的差異。 Scaling意味著擴展，Vertical Scaling著重於單一實體的運算能力增強，所以Vertical Scaling可能會是更好的 CPU/GPU,更大的記憶體容量等等， 以 AWS 服務來說，可能會是更換實例，MQ的話就會是從 t3.Micro 換成 m5.large [+] 執行個體類型 - https://docs.aws.amazon.com/zh_tw/amazon-mq/latest/developer-guide/broker-instance-types.html 而若要水平擴展，通常代表架構會接收到更多消息，所以會需要根據流量/訊息量來去擴展並且分擔單一實例的負擔。 ActiveMQ 代理網路（Network of brokers）這是一個 Ac...

什麼是 OTA Update (Over The Air Updtae)?透過無線通訊去對設備進行軟體/韌體更新 OTA 的流程 Notify 設備會被通知有擱置的OTA更新 設備可以選擇忽略更新或者接受更新以觸發下載 Download 設備通過各種支援的協定進行更新下載 更新包會下載到預先設定好的儲存區域 Ex. S3 Bucket 更新可能是全新的韌體映像或現有韌體的補丁 Verify 驗證更新包的有效性 Install 設備通過更新包開始更新（通常是通過 bootloader）成最新的韌體 安裝後可以執行檢查以驗證功能 設備將向 OTA 更新提供者報告韌體更新成功 主要分成這四個步驟 模組化 OTA 更新 模組化 OTA 由幾個小型函式庫和一個協調器(Orchestrator)組成。 每個 Lib 負責特定的子任務，例如通知待處理的 OTA 更新或透過 MQTT 下載檔案 編排器將所有小型程式庫與bootloader 和 Memory Pool 同步以執行 OTA 更新。 模組化 OTA 方法可讓您根據需求的變化更換或更改 OTA 的不同部...