題目： LeetCode - 165. Compare Version Numbers 題目說明給兩個字串，代表兩個版本號，判斷兩者的大小。( leading zeroes 忽略不計 ) 解題思路使用兩個指針，每一次都分別遍歷到 . 號為止，將這段字串轉換為整數並且比大小即可。 參考解法12345678910111213141516class Solution {public: int compareVersion(string version1, string version2) { int i{}, j{}, n1 = version1.length(), n2 = version2.length(); while(i < n1 || j < n2) { int tmp1{}, tmp2{}; while(i < n1 && version ...

題目： LeetCode - 16. 3Sum Closest 題目說明給一個陣列及整數 target，求陣列內任意三數相加最接近 target 的值。 解題思路先將陣列由小到大排序。選定最左邊的那個數，接著選擇右邊兩數，l 從 i + 1 開始，r 從最後一個數開始，若這三者相加等於 target 直接回傳，否則檢查這次的值跟 target 的差距是否小於之前選定的，之後判斷若是這次的值大於 target 則代表 r 需要往前選，否則代表 l 需要往後選。 參考解法123456789101112131415161718192021class Solution {public: int threeSumClosest(vector<int>& nums, int target) { int n = nums.size(), res = nums[0] + nums[1] + nums[2]; sort(nums.begin(), nums.end()); for(int i{&# ...

題目： LeetCode - 677. Map Sum Pairs 題目說明設計一個 Class，並完成以下的函式。 void insert(string key, int val)：建立 key 及 val 的映射，若 key 已經存在就將新的 val 覆蓋舊的 val。 int sum(string prefix)：回傳所有 key 的前綴為 prefix 的 val 總和。 解題思路使用 Unordered_map 存放資料。 void insert(string key, int val)：直接讓 m[key] = val 即可。 int sum(string prefix)：遍歷 map，使用 String 的 find() 函式，若是結果為 0 代表 prefix 為當前 key 的前綴，計算總和即可。 參考解法1234567891011121314151617class MapSum {public: /** Initialize your data structure here. */ MapSum() {} ...

題目： LeetCode - 112. Path Sum 題目說明給一個 Binary Tree 及整數 sum，求是否有一段從樹根到葉子的總和會等於 sum。 解題思路使用遞迴的觀念遍歷整棵樹，curSum 紀錄從樹根遍歷到這裡的總和，若是到了葉子且 curSum == sum 回傳 True，否則回傳 hasPathSum(root->left, sum, curSum) || hasPathSum(root->right, sum, curSum) 參考解法12345678910class Solution {public: bool hasPathSum(TreeNode* root, int sum, int curSum = 0) // add curSum { if(!root) return false; curSum += root->val; if(!root->left && !root->right && curSum == ...

題目： LeetCode - 129. Sum Root to Leaf Numbers 題目說明給一個 Binary Tree，從樹根到每片葉子中間包含的數字代表一串十進位的數字，求總和。 類似題目：LeetCode - 1022 解題紀錄 / September LeetCoding Challenge Day 8 解題思路使用遞迴的概念遍歷整棵樹，sum 紀錄到目前的十進位總和，若是目前的 node 已經是葉子，直接回傳 sum，否則回傳 sumNumbers(root->left, sum) + sumNumbers(root->right, sum)。 參考解法123456789class Solution {public: int sumNumbers(TreeNode* root, int sum = 0) // add sum { if(!root) return 0; sum = sum * 10 + root->val; return !root->left &am ...

題目： LeetCode - 1022. Sum of Root To Leaf Binary Numbers 題目說明給一個 Binary Tree，從樹根到每片葉子中間包含的數字代表一串二進位的數字，求轉為十進位後的總和。 類似題目：LeetCode - 129 解題紀錄 解題思路使用遞迴的概念遍歷整棵樹，sum 紀錄到目前的十進位總和，若是目前的 node 已經是葉子，直接回傳 sum，否則回傳 sumRootToLeaf(root->left, sum) + sumRootToLeaf(root->right, sum)。 參考解法123456789class Solution {public: int sumRootToLeaf(TreeNode* root, int sum = 0) // add sum { if(!root) return 0; sum = sum * 2 + root->val; return !root->left && !root- ...

題目： LeetCode - 290. Word Pattern 題目說明給兩個字串 pattern 及 str 分別代表單詞的組成模式及單詞組成。求單詞組成是否符合組成模式。 解題思路使用 Stringstream 來分割 str，Unordered_map 紀錄組成模式及對應的字串，Unordered_set 避免兩個 key 對應到同一個字串，接著遍歷 pattern，若是碰到兩種 key 對應到同一個字串或是 val 與當前讀取到的字串不相等則回傳 False，最後判斷 str 是否已經全部處理，若是沒有代表 pattern 的長度不夠，此時也是回傳 False。 參考解法123456789101112131415161718class Solution {public: bool wordPattern(string pattern, string str) { string tmp; stringstream ss(str); unordered_map<char, string> m ...

題目： LeetCode - 6. ZigZag Conversion 題目說明給一個字串，依照要求 ( ZigZag ) 將字串轉換。題目其實就是每次都往下換行，到底再往上換行，到頂再往下不斷反覆直到 s 用盡。 解題思路使用陣列儲存每一行的字符，遍歷陣列，依照位置放入陣列中的字串，最後再把所有字串串接起來即可。 參考解法1234567891011121314151617181920212223242526class Solution {public: string convert(string s, int numRows) { if(numRows == 1) return s; int n = s.length(), j = -1; bool reverse = false; string res; vector<string> v(numRows); for(auto& c : s) { if ...

題目： LeetCode - 50. Pow(x, n) 題目說明設計一個 pow() 函數。 解題思路使用遞迴的觀念，先假設函式能取得 n / 2 次方的正確答案，此時若 n 為 2 的倍數，代表答案為 n / 2 次方的答案相乘，否則若是 n 大於 0，代表還要再乘一次 x，若 n 為負數則要除以一次 x。 參考解法12345678910class Solution {public: double myPow(double x, int n) { if(!n) return 1; auto tmp = myPow(x, n / 2); if(!(n % 2)) return tmp * tmp; return n > 0 ? x * tmp * tmp : tmp * tmp / x; }};

題目： LeetCode - 835. Image Overlap 題目說明給兩個只包含 0 和 1 的正方形陣列代表圖片，求兩者經過左右、上下平移後能造成 1 重疊的最多數量。 解題思路先使用兩個陣列紀錄兩者圖片為 1 的所有座標，接著使用 HashMap 紀錄兩張圖片任意兩個 1 的偏移量相同的個數 ( 偏移量相同代表經過同樣的平移能使得兩者都重疊 )，最後找出最大值即可。 參考解法12345678910111213141516171819202122232425// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int largestOverlap(vector<vector<int>>& A, vector<vector& ...