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

題目敘述 題目難度: Medium 題目敘述: 給定一個 single linked list 的 head，將所有具有奇數索引的節點分組在一起，然後將具有偶數索引的節點分組，並傳回重新排序的list。第一個節點為奇數索引，接著第二個為偶數，以此類推，此題要求實作的演算法空間複雜度為 $O(1)$ 而時間複雜度為 $O(n)$ 解法一開始的想法 我的想法就是先traverse list，然後紀錄偶數節點個數和奇數節點個數，之後各自建立新的lists，最後合併兩個lists然後回傳薪的head 我的解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 ...

題目敘述 題目難度: Easy 題目敘述: 給定已排序的整數陣列，以及一個目標值，若再陣列中找到目標值就返回 index，如果沒有就返回適合插入的位址。另外題目也要求實作演算法的複雜度要是 $O(log n)$。 解法一開始的想法 針對已排序的陣列，尋找目標值的方法使用 Binary Search 可以滿足需求 我的解法123456789101112131415161718192021222324252627282930int searchInsert(int* nums, int numsSize, int target) { int right, left, mid; right = numsSize-1; left = 0; while(left < right){ mid = left + (right - ...

題目敘述 題目難度: Easy 題目敘述: 給定一個 single linked list 的 head 並且希望回傳 list 的中間節點，若中間節點有兩個，需要回傳第二個 解法一開始的想法 定義節點結構 建立 linked list 呼叫函數 middleNode() 在 middleNode 內: Traverse list，才有辦法知道中間節點，在 traverse過程透過一個counter來紀錄數量 判斷當前節點數量是奇數還是偶數，取得中間節點的 index 接著重新走訪到 middleNode，並回傳節點 我的解法1234567891011121314151617181920212223242526272829303132333435363738394041/** * Definition for singly-linked list. * struct List ...

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

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

題目敘述 題目難度: 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 應該不用單獨拿出來處理。 我的 ...

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

鏈結串列(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_n ...

題目敘述 題目描述給定整數的陣列以及整數 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)); // ...

基本介紹雜湊表是一種 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_h ...