題目： LeetCode - 771. Jewels and Stones 題目說明給兩個字串 J、S，求 S 裡面有多少個字元與 J 裡面的字元相同。 解題思路使用 String 裡面的 find() 即可。 參考解法12345678910class Solution {public: int numJewelsInStones(string J, string S) { int count = 0; for(auto i : S) if(J.find(i) != -1) ++count; return count; }};

題目： LeetCode - 278. First Bad Version 題目說明給一個整數 n，求 1, 2, …, n 中，從哪個數字開始是 Bad version。 解題思路使用二元搜尋法即可。※ 須注意溢位的問題，所以型態使用 long long。 參考解法123456789101112131415class Solution {public: int firstBadVersion(int n) { long long first = 1, last = n, mid = (first + last) / 2; while(!isBadVersion(mid) || isBadVersion(mid - 1)) { if(!isBadVersion(mid)) first = mid + 1; else last = mid - 1; mid = (first + la ...

題目： LeetCode - 2. Add Two Numbers 題目說明給兩個 Linked List ( 順序是由小位數到大位數 )，求相加後的結果。 解題思路定義一個 carry，使用一個迴圈，carry 每次都將 l1->val ( 若存在 ) 和 l2->val ( 若存在 ) 加上，然後新建一個 node，node-val 的值為 carry 除以 10 的餘數，最後再把新建的 node 接上即可。 參考解法123456789101112131415161718192021class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry = 0, firstNode = 1; auto res = l1, curr = l1; while(l1 || l2 || carry != 0) { if(l1) c ...

題目： LeetCode - 583. Delete Operation for Two Strings 題目說明給兩個 String，求刪除最少的字元數使兩者相等。 解題思路可將問題想成，找出兩者的 LCS 在將兩者的長度個別減去 LCS 的值即為答案。找 LCS 的作法可參考本篇文章：LeetCode - 1143 解題紀錄。 參考解法1234567891011class Solution {public: int minDistance(string word1, string word2) { int l1 = word1.size(), l2 = word2.size(); auto dp = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, 0)); for(int i = 1; i <= l1; ++i) for(int j = 1; j <= l2; ++j) ...

題目： LeetCode - 124. Binary Tree Maximum Path Sum 題目說明給一個 Binary Tree，求最大路徑和。 解題思路使用遞迴即可。核心觀念為：最大路徑和有沒有包含 root ( 自己 )？ 若有：最大路徑和為：左邊的最大路徑和 ( 需包含 root，但可以不選) + root->val + 右邊的最大路徑和 ( 需包含 root，但可以不選)。 若沒有：最大路徑和為：左邊的最大路徑和 ( 任意起點任意終點 ) 及 右邊的最大路徑和 ( 任意起點任意終點 ) 兩者取其大。 參考解法12345678910111213141516class Solution {public: // 找出以 root 為起點的最大路徑和 int maxPath(TreeNode* root) { if(!root) return 0; return max(maxPath(root->left) + root->val, max(maxPath(roo ...

題目： LeetCode - 221. Maximal Square 題目說明給一個二維陣列，裡面包含 0 和 1，求出其中值為 1 的元素能組出的最大正方形。 解題思路對於陣列中的每個元素來說，若該值為 1，能組出的最大正方形的長度為，左邊那個元素能組出的最大正方形的長度、上面那個元素能組出的最大正方形的長度 和 左上角那個元素能組出的最大正方形的長度，三者的最小值 + 1，依照此想法使用動態規劃即可。 參考解法123456789101112131415class Solution {public: int maximalSquare(vector<vector<char>>& matrix) { int height = matrix.size(); if(!height) return 0; int width = matrix[0].size(), Max = 0; auto dp = vector<vector<int> ...

題目： LeetCode - 1143. Longest Common Subsequence 題目說明給兩個 String，找出它們 LCS 的長度。 解題思路使用動態規劃即可。 參考解法1234567891011121314151617class Solution {public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(), n2 = text2.size(); // dp[i][j] = text1[i], text2[j] 的 LCS auto dp = vector<vector<int>>(n1 + 1, vector<int>(n2 + 1, 0)); for(int i = 1; i <= n1; ++i) for(int j = 1; j <= n2; ++j) // ...

題目： LeetCode - 55. Jump Game 題目說明給一個陣列，元素的值代表能走的步數，求是否能走到最後。 解題思路定義一個 maxPos 代表能走到的最遠位置。用一個迴圈訪問 nums，若是目前元素的值小於等於 maxPos，代表這一格是可以走到的，計算 i + nums[i] 是否有大於 maxPos，若是有就替換掉。最後看 maxPos 是否大於等於 nums.size() - 1 即可。 參考解法12345678910class Solution {public: bool canJump(vector<int>& nums) { int maxPos = 0, n = nums.size(); for(int i = 0; i < n; ++i) if(i <= maxPos) maxPos = max(maxPos, i + nums[i]); return maxPos >= n - 1; & ...

題目： LeetCode - 146. LRU Cache 題目說明建立一個類似快取記憶體的 Class，及對應的一些功能。 解題思路使用 list<pair<int, int>> 儲存資料，再利用 unordered_map<int, list<pair<int, int>>::iterator> 達到減少時間複雜度的效果。※ 對於 put 來說，如果資料已經滿了，那新的資料就要覆蓋最久沒有調用到的資料。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445class LRUCache {public: list<pair<int, int>> cache; // 儲存 key 及 value unordered_map<int, list<pair<int, int>>::iterator> hash; // 儲存 key ...

題目： LeetCode - 201. Bitwise AND of Numbers Range 題目說明給一個數值 m、一個數值 n，0 <= m <= n <= 2147483647。求 m & (m + 1) & ... & n 的值。 解題思路對於 & 運算來說，只要有一個是 0，那結果就會是 0，所以我們只要看 m 跟 n 轉換成二進位後，以左而右從哪個數字開始不一樣，就從那個數字開始到最後面補 0 即可。舉例來說： 123455：00 00000 00000 00000 00000 00000 001|017：00 00000 00000 00000 00000 00000 001|11 ^ 從這裡開始不一樣所以答案是：4：00 00000 00000 00000 00000 00000 001|00 做法也非常簡單，使用 >> 運算符，它會將數字轉換成二進位後，推掉最右邊的那一位，然後在最左邊補 0，而 >>= 的概 ...