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

題目敘述 題目難度: Easy 題目敘述: 題目給定字串 s，當你把字串中的大寫字母轉換成小寫字母，並且把所有非字母或數字類的符號去除，如果從頭讀到尾跟從尾讀到頭都是一樣的字串，那就是一個有效的 回文(Palindrome) ，若回文有效就返回 true，反之則 false，s 僅包含ASCII當中可印出的符號。 解法一開始的想法 先將題目字串 s 中的大寫字母轉為小寫，並且將其餘符號去除 這部分可以宣告一個新的空字串，並且分別處理數字、大寫字母以及小寫字母 接著就是判斷回文，可透過迴圈同時檢查字串的頭跟尾是否一樣，若有發現不一致則回傳false，反之則True 頭尾pointer僅需scan到字串的中間即可 我的解法12345678910111213141516171819202122232425262728293031323334353637class Solution {public: bool isPalindrome(string s) { bool isPalindrome = false; string ...

題目敘述 題目難度: Easy 題目描述: 本題要求給定一個字串陣列 tokens，當中是以 逆波蘭表示法 的算式運算式，需要回傳算術運算的結果，結果為整數型態。 注意: 有效的運算子只會有: +, -, *,/。 Operand 都會是整數 除法採無條件捨去法 不可除以0 中間運算的數字會是 32-bit 整數 解法一開始的想法如果看上面的範例 ["4","13","5","/","+"]，可以看出，如果碰到operator，碰到operator前的兩個數字就會透過該operator進行運算。 因此我的想法是: 建立一個stack 迭代 tokens 若遇到數字就push進stack 若遇到運算子，則將兩個元素pop出來進行四則運算 運算結果丟回 stack 迭代完畢後回傳 stacK 頂端元素 我的解法1234567891011121314151617181920class Solution {public: int evalRPN(vector&l...

題目敘述 題目難度: Easy 題目敘述: 題目會給定一個 Unix 系統的檔案路徑字串，這題需要簡化路徑，並輸出簡化後的路徑字串。簡化路徑有下面幾項規則: 字串始終由 / 開始 路徑中的目錄僅可由一個 / 分隔開 除了 Root Dir 之外，不可由 / 作為字串結尾 輸出需要排除 . 或者 .. 在 Unix 系統中 . 代表當前目錄，可忽略，.. 代表跳到上一層目錄，舉例來說 /home/kevin/../LeetCode = /home/LeetCode 解法一開始的想法 獲取 / 與 / 中間的字串(即目錄)，如果滿足規則就 push 進 stack 中 如果 /與 / 中間會是 . 則跳過，如果是 .. 則將stack中元素 pop 出來 其餘的通通 push 到 stack 當中 之後就是依序將 stack 元素 pop 出來並串接在回傳字串當中 我的解法12345678910111213141516171819202122232425262728293031323334353637383940class Solution {pub...

題目敘述 題目難度: Medium 題目敘述: 題目要求設計一個 Stack, 可以支援 push, pop, top 以及在常數時間內獲取最小值 解法一開始的想法我的解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374class MinStack {public: int val, size = 0; MinStack *next; MinStack *Top = NULL; MinStack() : val(0), next(0) {} MinStack(int x) : val(x), next(0) {} MinStack(int x, MinStack *nextNode) : val(x), next(nextNode) {} ...

題目敘述 Constraints: 1 <= s.length <= 100 s consists of digits 0-9 and characters ‘+’, ‘-‘, ‘*’, ‘/‘, ‘(‘, and ‘)’. It is guaranteed that parentheses expression s is a VPS. 題目難度: Easy 題目敘述: 給定一個有效的括號字串 s，回傳括號nesting的深度 這裡有效的意思就代表不會有類似這種字串出現 )()()(())(，一定會是閉合成對的括號 解法一開始的想法 這題很簡單，從想解法(畫在平板上)到最後Submission Accept花了11分鐘。 首先要想的問題會是: 如何判斷nesting parentheses? 我認為只要有連續的左邊未閉合括號出現，就能夠判斷出nesting深度。因此要做的事情就是當出現左括號 ( 就 push 進 stack，當出現右括號就 pop出stack，這些操作進行的同時記錄下stack的數量變化，最大值即為深...

背景 目前在台灣亞馬遜網路服務公司 (Amazon Web Services) 擔任 雲端支援工程師 (Cloud Support Engineer) ，但兩天後就要離職了，因此想說趁離職前紀錄並回顧一下這一年半以來的工作以及生活。 我是在我碩二上的時候(2021年10月)投遞AWS Cloud Support 校園招聘的職缺，當時原本在找研發替代役，後來因為知道AWS有開缺，抱持著試試看的心情投遞了履歷。大概隔天就收到了Online Assessment 的通知。OA其實就是簡單的電腦基礎知識，應該只是拿來篩本科非本科的(?)，接著就是Phone Interview，當時的校招可以排志願序，我原本想去的是 Security 或者 Deployment Profile，但我在面試過程中，發現問題大多會跟 Troubleshooting 相關，因此Security Fail了，然後Deployment 進到最後的loop 的最後一關技術關也被問爆，後來轉面 DMS(Developer and Mobile Services) ，雖然是自己完全不太熟悉的領域，但好險最後通過面試了。...

題目敘述 題目難度: Easy 題目敘述: 給定一個字串 s，其中僅會包含 (、)、[、]、{、} 這些括號，需要在函式內判斷字串內的括號組合是否是合法得的，那怎樣算合法? 左括號一定要由相同類型的右括號閉合 括號閉合順序要正確 每個右括號也需要有相同類型的左括號閉合 舉例來說: Valid: 123s= "()[]{}"s= "([])"s= "[]" Invalid: 12s = "([)]"s = "(]" 解法一開始的想法 　我的想法就是在迭代字串中字元的時候，將所有左括號 push 進一個stack，如果下一個字元是相應的右括號，就將括號從 stack 中pop出來，只要最後檢查stack是否還有左括號在，就能判斷是否valid。當然還是有一些edge case需要處理 我的解法1234567891011121314151617181920212223242526272829303132333435363738394...

甚麼是 Stack?Stack 是一種資料結構，具有 後進先出(Last-In-First-Out, LIFO) 的特性， Stack 實作 (C++)這裡我想透過 C++ 去時做一個完整的 Stack 功能，並且實踐常見的 push, pop, isEmpty 等等操作 用 Array 實作 Stack再透過C++ 實作Stack得時候，需要注意某些變數不能被外部存取，像是 top: 用於指向stack 的頂端，也就是最上面的index capacity: stack的記憶體大小 *stack: 指向stack的指標 因此與上面相關的變數需要作為 Private 的成員變數。另外再使用陣列實踐Stack的時候有時候會出現，記憶體不夠的狀況，因此可以透過建立一個自動擴展capacity的函數來解決。 另外，在實作Pop的時候，並不需要將資料實際移除，而是將 top 扣掉1，好像是我們真的把資料從stack刪除一樣，但實際上並沒有，而是在未來Push的時候再將現有資料蓋過去即可，這樣的做法可以節省記憶體操作成本 注意: 在進行Pop或者是 Top操作(回傳現在Stack...

題目敘述 題目難度： Medium 題目敘述：這題要求給定兩個非空的linked list來代表兩個非整數數字，兩個數字以反向排序，每一個digit被存在個別的node上，題目要求將兩個數字相加後同樣以反向存成一個linked list並回傳 舉例：可以看範例1，342 和 465 分別以反向排序儲存，並且相加後的值為 807，最後再反向初存成list，輸出 [7,0,8] 解法一開始的想法 最一開始的想法大概花費10分鐘定義好，但實際上較為複雜我的想法是從個別List取得個別數字，相加後，再存成list 宣告變數 a1, a2. sum Traverse List1 長度 檢查 list1 的值，逐項相加，存入變數a1 Traverse List2 長度 檢查 list2 的值，逐項相加，存入變數a2 sum = a1 +a2; 建立新list，反向存入sum 中的值 回傳 new list head 我的解法123456789101112131415161718192021222324252627282930313233343536373839404142...

題目敘述 題目難度: Easy 題目敘述: 給定一個排序鍊結串列的 head, 刪除所有重複節點，每個節點元素僅能出現一次，回傳排列串列 解法 這是第一次改用 C++ 寫 Linked List 題目，但由於題目是 single linked list，因此沒能夠用到透過 double linked list 實作的 std:list STL Library，有點小可惜，所以思路上還是用到了慣用的 C 時間紀錄: 想解決辦法: 1min 實際撰寫程式碼: 15 minutes 大概 Run 兩次，第一次沒有考慮到結尾 Null Pointer 的狀況 一開始的想法 定義好兩個指標，分別指到前一個節點跟當前節點 遍歷整個list 每次都檢查當前節點值與前一個節點值是否一樣，結束後更新指標值 回傳head 我的解法1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for singly-linked list. * struct...