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

甚麼是 STL (Standard Template Library)?在 C++ 中，STL即為一群容器(Container)的集合，不同容器可以實現不同的資料結構，其實是大量使用了 C++中的 Template 來去實現的。透過該資料結構實現出演算法，STL還提供對於容器的操作，不同資料結構的容器分別也有不同的操作方式。 Template 簡單來說就是定義好結構，並且可用於不同的資料型別上，例如我寫了一個陣列的Template，但它可以是 int[], float[], double [] 或者是 char []template <typename T> 通常可以這樣來定義 Template ，通常使指角括號內的東西，可以想像成compiler 幫你做複製貼上 STL 元件主要有6大個元件: 容器 (Container) 演算法 (Algorithm) 迭代器（Iterator） 仿函數（Function object） 適配器（Adaptor） 空間配置器（allocator） 對於刷題，最需要focus的重點會是容器和迭代器，另外還有algorith...

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

題目敘述 題目難度: 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 - left)/2; if (target < nums[mid]){ right = mid; } ...

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

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