371. Sum of Two Integers
題目網址：https://leetcode.cn/problems/sum-of-two-integers/
題意：給兩整數 a 和 b, 在不使用 +、 - 運算的情況下, 返回兩整數之和。
Solution：
想法：將加法拆分成無進位加法、進位這兩個部分
XOR：為無進位的加法, 透過 a ^ b 得到無進位的加法結果, 還需要找到進位的數, 並把這兩者相加才能得到答案
&、shift：a & b 把 a、b 中相同位置皆為 1 的 bit 設為 1, 最後再將 a & b 左移一位即可得到進位的數e.g. a = 5, b = 4, 則進位數 = a & b = 0100, 但 0100 並非進位的數, 1000 才是真正進位的數
因此, 我們的步驟如下：
得到 a 和 b 的進位數
得到無進位加法
循環此過程, 直到 carry = 0
e.g. a = 5, b = 4
得到 carry b = (a & b) << 1 = 1000、無進位加法 a = (a ^ b) = ...
7. Reverse Integer
題目網址：https://leetcode.cn/problems/reverse-integer/
題意：給一 32-bit 的有號整數 x, 返回將 x 中的數字部分反轉後的結果。
如果反轉後的整數超過 32-bit 的有號整數的範圍 [−$2^{31}$, $2^{31}$ − 1], 則返回 0。
假設不允許儲存 64-bit 整數（有號 or 無號）, 也就是說結果只能用 int 來儲存, 不允許用 long 之類的 data type。
Solution：
想法：int 的範圍是 [-2147483648, 2147483647], 因此在執行 res = (10 * res) + (x % 10) 前, 要先判斷這樣做是否會 overflow
class Solution {public: int reverse(int x) { int res = 0; while (x) { // 避免下面 (10 * res) + (x % 10) ...
442. Find All Duplicates in an Array
題目網址：https://leetcode.cn/problems/find-all-duplicates-in-an-array/
題意：給一有 n 個數的 array nums, 每個元素值皆在 [1, n], 且每個元素可能出現 一次 or 兩次, 求所有出現兩次的數。
注意：使用 $O(n)$ time 和 $O(1)$ space 的演算法
Solution：
想法：將數字乘以負號來標記我們看到的數字的 index, 然後遍歷 nums 元素, 若 nums[i] > 0, 代表數字 i + 1 出現過兩次(類似 448. Find All Numbers Disappeared in an Array)
e.g. [1, 1, 2] ➔ [1, -1, 2], nums[i - 1] 決定數字 i 出現的次數
class Solution {public: vector<int> findDuplicates(vector<int>& nums) { vector<int> r ...
784. Letter Case Permutation
題目網址：https://leetcode.cn/problems/letter-case-permutation/
題意：給一 string s, 將 s 中的每個字母轉變大小寫, 可得到新的 string。求所有可能的 string, 可以按順序任意排列。
Solution：
想法：利用 DFS + Backtracking
若 s[i] 為數字, 則 s[i] 不變繼續往後走
若 s[i] 為字母, 則有兩種情況：
s[i] 不變繼續往後走
s[i] 轉變大小寫後, 繼續往後走
class Solution {public: vector<string> letterCasePermutation(string s) { dfs(s, 0, s.size()); return res; }private: vector<string> res; void dfs(string& s, const int i, const int n) ...
647. Palindromic Substrings
題目網址：https://leetcode.cn/problems/palindromic-substrings/
題意：給一 string s, 返回迴文 substring 數量。
Solution 1：
想法：利用DP, 可參考 5. Longest Palindromic Substring
class Solution {public: int countSubstrings(string s) { const int n = s.size(); int res = n; // 每個 char 自己本身(對角線)為回文 vector<vector<bool>> dp(n, vector<bool>(n, true)); for (int j = 1; j < n; ++j) { for (int i = 0; i < j; ++i) { dp[i][j] = (s[i ...