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

題目敘述 題目難度: Easy 題目描述: 給定兩個已排序 linked list 的 head，希望能夠合併成一個已排序的list 解法一開始的想法 一開始我想說可以先走訪 list1 然後逐項比對 list2 的item，如果 list1中的元素小於 list2 的，就插入到 list2，並且插入後，再繼續迭代 list1當中的元素 原始代碼： 1234567891011121314151617181920212223242526272829303132333435363738394041424344Node *ptr1, *ptr2, *previous, *preceding; ptr1 = list1;ptr2 = list2;preceding = ptr1;previous = ptr2;//Empty listsif(ptr1==NULL && ptr2==NULL){ //return empty list return ptr1;}else if (ptr1 == NULL ){ return...

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