題目： LeetCode - 7. Reverse Integer 題目說明給一個整數，將此整數反轉。 解題思路從最後面一位一位拿出來即可，需要特別注意若是過程中超過 int 的界限就直接回傳 0。 參考解法1234567891011121314class Solution {public: int reverse(int x) { int ans = 0, max = INT_MAX / 10, min = INT_MIN / 10; while(x != 0) { if(ans > max || ans < min) return 0; ans = ans * 10 + x % 10; x /= 10; } return ans; }};

題目： LeetCode - 705. Design HashSet 題目說明設計一個 Hash_set 的 Class。 解題思路使用 Unordered_set 實作即可。 參考解法12345678910111213141516171819202122// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class MyHashSet {public: /** Initialize your data structure here. */ MyHashSet() {} void add(int key) { hs.insert(key); } void remove(int key) { hs.erase(key); } ...

題目： LeetCode - 3. Longest Substring Without Repeating Characters 題目說明給一個 String，找出這個 String 裡面最長的不重複子陣列。 解題思路定義一個陣列紀錄每個英文字母最後出現的位置，使用一個迴圈，j 為子陣列的右端點，i 為子陣列的左端點，每一次 i 都更新為 max(i, v[s[j] + 1]) 這樣就可以確保子陣列中沒有重複的元素，此時子陣列的長度為 j - i + 1，最後更新 maxL 即可。 參考解法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 lengthOfLongestSubstring( ...

題目： LeetCode - 72. Edit Distance 題目說明給兩個 String word1、word2，求最少的操作數使得 word1 等於 word2。操作有以下三種： 插入 刪除 取代 解題思路動態規劃，核心想法為，目前這兩個字是否相等？若相等則表示不需要操作 dp[i][j] = dp[i - 1][j - 1]，若不相等則 dp[i][j] 為 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1] 三者最小值加一。需要注意的是，邊界需要初始化。 參考解法1234567891011121314151617181920212223242526// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int minDista ...

題目： LeetCode - 520. Detect Capital 題目說明給一個 String 代表一個單字，求單字是否符合以下條件： 所有字母都為大寫 所有字母都為小寫 只有第一個字母為大寫 解題思路紀錄大寫字母的數量及最後一個大寫字母的 index，最後再判斷即可。 參考解法123456789101112class Solution {public: bool detectCapitalUse(string word) { int index, count = 0, n = word.size(); for(int i = 0; i < n; ++i) if(word[i] >= 'A' && word[i] <= 'Z') ++count, index = i; if(!count || (count == 1 && index == 0) || count = ...

題目： LeetCode - 338. Counting Bits 題目說明給一個 num，回傳一個代表 0 ~ num 的二進制中 1 的數量的陣列。 解題思路觀察答案的陣列可以知道，對於 i 來說，如果 i 是奇數則 res[i] = res[i / 2] + 1，如果 i 是偶數則 res[i] = res[i / 2]。 參考解法123456789class Solution {public: vector<int> countBits(int num) { vector<int> res(num + 1); for(int i = 1; i <= num; ++i) res[i] = res[i / 2] + i % 2; return res; }};

題目： LeetCode - 1035. Uncrossed Lines 題目說明給兩個陣列，將陣列中相同的元素連線，連線不能交叉，求最大連線數。 解題思路其實題目的答案就是兩者的 LCS。找 LCS 的作法可參考本篇文章：LeetCode - 1143 解題紀錄。 參考解法12345678910111213141516171819// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int maxUncrossedLines(vector<int>& A, vector<int>& B) { int m = A.size(), n = B.size(); auto dp = vector&l ...

題目： LeetCode - 986. Interval List Intersections 題目說明給兩個代表區間的陣列，求兩陣列的交集。 解題思路使用雙指針，s 為兩者開頭較大的值，e 為兩者結束較小的值，若是 s <= e 則代表這是一段交集，最後看哪個的結尾比較小，就往前移動那個指針。 參考解法123456789101112131415161718192021222324// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int& ...

題目： LeetCode - 451. Sort Characters By Frequency 題目說明給一個 String，將 String 裡面的字元按照個數排序，例如： tree -> eert or eetr。需要注意的是大小寫為不同的字元。 解題思路先使用 hash_map 得到每個字出現的次數，再用 Vector 排序，最後串接到 String 即可。 參考解法12345678910111213141516171819202122232425262728// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: static bool cmp(const pair<char, int>& l,const pair<char, in ...

題目： LeetCode - 1277. Count Square Submatrices with All Ones 題目說明給一個二維陣列，裡面包含 0 和 1，求出其中值為 1 的元素能組出幾個不同的正方形。 解題思路對於陣列中的每個元素來說，若該值為 1，能組出的正方形個數為，左邊那個元素最多能組出的正方形個數、上面那個元素最多能組出的正方形個數 和 左上角那個元素最多能組出的正方形個數，三者的最小值 + 1，依照此想法做動態規劃即可。 參考解法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 countSquares(vector<vector<int>> ...