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

題目敘述 題目難度： Medium 題目描述： 題目要求給定一個字串陣列 strs，需要將 Anagrams 分組，並且回傳經過分組過的陣列，回傳陣列中的Anagrams 可以是任何順序 Anagram 代表兩個單字裡面組成的字母和數量是完全一樣的，簡單來說 Anagram 就是由A單字重新排列組合成一個B單字。 解法一開始的想法 迭代 Input Vector 為每個Obj 建立Table 迭代 Vector 檢查是否有其他匹配的 Pair 如果有 insert item 我的解法我後來沒有在時間內解出來，因此還是參考了一下網路上的作法 123456789101112131415161718192021222324252627282930313233class Solution {public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> ...

題目敘述 題目難度: Easy 題目敘述: 題目要求給定兩個字串 s 與 t，若 t 為 s 的 Anagram，則回傳 true，若不是則回傳 false Anagram 代表兩個單字裡面組成的字母和數量是完全一樣的，簡單來說 Anagram 就是由A單字重新排列組合成一個B單字。 解法一開始的想法這次的想法一樣是建立 HashTable，所以一開始的想法如下: 迭代 s，建立 HashTable 迭代 t，依序檢查字母是否有出現在 HashTable，進行比對 迭代完畢後，若全部匹配則回傳True 若無則否 我的解法1234567891011121314151617181920212223242526272829303132333435363738class Solution {public: bool isAnagram(string s, string t) { //character, times unordered_map<char, int> Dict; if (s.leng...

題目敘述 題目難度：Medium 題目敘述：題目主要需求是將輸入的整數 num 轉換成對應的羅馬數字符號，並給定一個對應表，在轉換過程有幾項轉換規則： 羅馬數字是通過從最高位到最低位將小數位值的轉換連接起來形成的 如果該值不以4或9開頭,則選擇可以從輸入中減去的最大值的符號,將該符號附加到結果中,減去其值,然後將剩餘部分轉換為羅馬數字。 如果該值以4或9開頭,則使用表示從下一個符號中減去一個符號的減法形式,例如,4是 5(V)減去1(I):IV,而9是10(X)減去1(I):IX。只使用以下減法形式:4(IV)、9(IX)、40(XL)、90(XC)、400(CD)和900(CM)。 只有10的次方(I、X、C、M)可以最多連續附加3次以表示10的倍數。不能多次附加5(V)、50(L)或500(D)。如果需要附加4次符號,需使用減法形式 限制： 1 <= num <= 3999 解法一開始的想法我其實一開始偏向暴力解，就根據條件去個別判斷，然後從數字的高位數開始判斷並轉換符號，已經轉過的數字就減掉 我的解法123456789101112131415161718...

甚麼是 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...