題目： LeetCode - 211. Add and Search Word - Data structure design 題目說明設計一個資料結構，完成題目要求的兩個函式，void addWord(string word)、bool search(string word)。在 word 中， . 代表任意字符。 解題思路使用字典樹來實現，關於字典樹的做法可參考本篇文章：LeeCode - 208 解題紀錄。 void addWord(string word)： 和字典樹的做法一模一樣，不再贅述。 bool search(string word)： 由於題目多了 . 的特殊情況，所以我們額外定義一個函式，bool exist(string& word, int pos, node* ptr) pos 代表目前要檢查的字元位置，當 word[pos] 不為 . 時，直接往下檢查即可。否則 ptr->child[] 全部都要往下檢查。 參考解法123456789101112131415161718192021222324252627282930313233 ...

題目： LeetCode - 20. Valid Parentheses 題目說明給一個只含有括號的字串，求此字串是否合法。字串合法須滿足以下條件： 開括號必須用相同類型的括號封閉 開括號必須以正確的順序關閉 解題思路由於閉括號必須搭配相同類型的開括號，所以可以使用 Stack，碰到開括號時直接推入，若碰到閉括號時只要看 stack.top() 是否是對應的開括號即可。 參考解法12345678910111213141516171819202122232425262728293031class Solution {public: bool isValid(string s) { stack<char> s_; for(auto i : s) if(i == '(' || i == '{' || i == '[') s_.push(i); else if(!s_.empty() ...

題目： LeetCode - 342. Power of Four 題目說明給一個整數，求此整數是否是 4 的次方數。 解題思路一個整數若是 4 的次方數，必定會是 2 的次方數，所以先判斷是否為 2 的次方數再判斷是否為 4 的次方數即可。 參考解法123456class Solution {public: bool isPowerOfFour(int num) { return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num; }};

題目： LeetCode - 14. Longest Common Prefix 題目說明給一個陣列，裡面的元素為 String，求此陣列中所有元素最長的相同開頭字串。 解題思路使用第一個元素去比對即可，若是碰到不符合的就直接回傳子串。若是都符合代表最長的就是 strs[0]。 參考解法123456789101112131415161718192021// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: string longestCommonPrefix(vector<string>& strs) { if(strs.empty()) return ""; int n ...

題目： LeetCode - 1536. Minimum Swaps to Arrange a Binary Grid 題目說明給一個二維陣列，代表一個正方形，裡面的值只有 0 或 1。題目要求第 n 行需要有 邊長 - n - 1 個 0 在最右邊，每次可以選擇一行與鄰近的行互換，求最少的交換次數，若題目無法達成要求的話回傳 - 1。 解題思路使用一個陣列紀錄每行右邊 0 的個數，之後找到要搬移的行進行搬移並紀錄次數即可。 參考解法12345678910111213141516171819202122232425262728293031323334// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int minSwaps(vector<vector<int ...

題目： LeetCode - 13. Roman to Integer 題目說明給一個羅馬數字，將此羅馬數字轉為整數。 解題思路建表比對即可，需先比對兩個英文字母的再比對一個英文字母的避免比對錯誤。 參考解法1234567891011121314151617181920212223// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int romanToInt(string s) { int pos, res = 0; pair<string, int> dict1[] = {{"I", 1}, {"V", 5}, {& ...

題目： LeetCode - 12. Integer to Roman 題目說明給一個整數，將此整數轉為羅馬數字。 解題思路建表比對即可，特別的是 4、9、40、90、400、900 也需要建。 參考解法12345678910111213141516class Solution {public: string intToRoman(int num) { string res; int pos = 12; pair<string, int> dict[] = {{"I", 1}, {"IV", 4}, {"V", 5}, {"IX", 9}, {"X", 10}, {"XL", 40}, {"L", 50}, { ...

題目： LeetCode - 11. Container With Most Water 題目說明給一個陣列代表容器的兩邊長，求最大容積。 解題思路使用雙指針即可，而移動指針時只需要移動長度較小的指針即可。 參考解法12345678910111213141516171819202122// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int maxArea(vector<int>& height) { int n = height.size(), m = INT_MIN, l = 0, r = n - 1, L, W; while(l < r) { L = ...

題目： LeetCode - 9. Palindrome Number 題目說明給一個整數，求此整數是否為回文。 解題思路從最後面一位一位拿出來即可，需要特別注意若是過程中超過 int 的界限就直接回傳 False。 參考解法12345678910111213141516class Solution {public: bool isPalindrome(int x) { if(x < 0) return false; int temp = x, reverse = 0, max = INT_MAX / 10; while(temp > 0) { if(reverse >= max) return false; reverse = reverse * 10 + temp % 10; temp /= 10; } return ...

題目： LeetCode - 125. Valid Palindrome 題目說明給一個 String，檢查此字串是否為回文。 解題思路使用雙指針即可，使用 isalnum() 判斷字符是否為數字或英文字母，使用 tolower() 將字母轉為小寫。 參考解法12345678910111213141516171819202122232425262728293031// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: bool isPalindrome(string s) { int i = 0, j = s.size() - 1; while(i <= j) { if(isalnu ...