題目： LeetCode - 543. Diameter of Binary Tree 題目說明給一個 Tree，找出它的最長路徑。 解題思路核心想法為，最長路徑有沒有通過 root？ 若有：最長路徑為 左邊 node 的最深深度 加上 右邊 node 的最深深度。 若沒有：最長路徑為 左邊 node 的最長路徑 或是 右邊 node 的最長路徑。 確定了上面想法後再利用遞迴的觀念找出答案即可。Tree 的最深深度的算法可參考：LeetCode - 104 解題紀錄 參考解法123456789101112131415161718192021222324class Solution {public: int maxDepth(TreeNode* root) { if(!root) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; } int diamete ...

題目： LeetCode - 104. Maximum Depth of Binary Tree 題目說明給一個 Tree，找出它的最深深度。 解題思路利用遞迴的概念，每個節點的最深深度為 左邊node 的最深深度 + 1 或是 右邊 node 的最深深度 + 1，終止條件為 root == nullptr 的時候。 參考解法12345678class Solution {public: int maxDepth(TreeNode* root) { if(!root) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; }};

題目： LeetCode - 155. Min Stack 題目說明設計一個 Stack，並完成部分功能。 解題思路可以直接使用 STL 的容器，所以只須明白 Stack 的運作模式即可。 解法一 Vector：速度較慢。( 因為插入與刪除元素的代價較高 ) 解法二 Stack：速度較快，這邊使用 stack<pair<int, int>> 來增加取得最小值的效率。 參考解法解法一： 1234567891011121314151617181920212223242526class MinStack {public: /** initialize your data structure here. */ vector<int> minstack; MinStack() { ios_base::sync_with_stdio(false); cin.tie(0); } void push(int x) { min ...

題目： LeetCode - 844. Backspace String Compare 題目說明給兩個字串，模擬字串的內容操作鍵盤，字串內的 # 代表 BackSpace，判斷模擬完後輸出的字串是否相同。 解題思路 解法一：定義新的兩個 String 並分別遍歷原本的字串，若不是 # 則 push_back() 到新字串，否則就 pop_back()。( 須注意字串的Size，若是 0 就不能在 pop_back() ) 解法二：使用雙指針，將模擬操作後的字串放入原本的字串。( 一樣要注意 Size 的問題 ) 參考解法解法一： 1234567891011121314151617181920class Solution {public: bool backspaceCompare(string S, string T) { string s, t; for(auto& i : S) if( i != '#') s.push_b ...

題目： LeetCode - 876. Middle of the Linked List 題目說明給一個 Linked List，找到 List 中間的那個 node。 解題思路 解法一：先遍歷一遍，得到整個 List 的長度，然後在用一個 node 走到長度的一半即可。 解法二：使用 Floyd Cycle Detection Algorithm 的概念，當 hare 走到結尾時，tortoise 剛好會走到一半。 參考解法解法一： 12345678910class Solution {public: ListNode* middleNode(ListNode* head) { int length = 0; auto ans = head; for(auto it = head; it != nullptr; it = it->next, ++length); for(int i = 0; i < length / 2; ++i, ans = ans->next); ...

題目： LeetCode - 49. Group Anagrams 題目說明給一個字串的陣列，將所有組成字串的字母相同的放在一起。 解題思路 想法：可使用 sort() 來排序 String，若是兩個組成字串的字母一樣，那排序過後會長的一樣。 解法一：使用 vector<pair<string, int>> 存放資料 ( 後面稱作 temp )，first 放排序過的字串，second 放該字串在 strs 裡面的 index。之後對 temp 進行排序 ( 預設會排序 first )。最後將排序過後相同的字串存入 res 即可。 解法二：使用 unordered_map<string, vector<string>> 存放資料，key 存放排序過後的字串，value 存放未排序的字串，最後將 value 存入 res 即可。 參考解法解法一： 123456789101112131415161718192021222324252627282930313233343536class Solution {public: ...

題目： LeetCode - 122. Best Time to Buy and Sell Stock II 題目說明給一個陣列代表股票的價格，賣的時間不可早於買的時間，求最大收益。 解題思路只需判斷相隔兩天即可，若第二天的價格大於第一天則於第一天購買並於第二天賣出。 參考解法12345678910class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(), profit = 0; for(int i = 0; i + 1 < n; ++i) if(prices[i] < prices[i + 1]) profit += prices[i + 1] - prices[i]; return profit; }};

紀錄使用 XOR 進行簡易加密，目前進行 2 次 XOR 運算 ( 太多次中文字會出錯 ) 作法 加密：隨機產生兩個數字，並將內容對這兩個數字做 XOR，最後這兩個數字對 9 做一次 XOR 並儲存在第一行 解密：先讀取第一行並對 9 做一次 XOR 可以得到兩個加密的數字，再將內容對這兩個數字做 XOR 並儲存即可 用法將要加密或解密的文字放在 data.txt 裡 加密：執行完成後會產生 encrypted.txt，裡面即是加密後的內容 解密：執行完成後會產生 decrypted.txt，裡面即是加密後的內容 已知 Bug 中文字有時會出錯 ( 變成其他文字或符號 ) 符號有時會出錯 ( 會不見 ) 努力方向 解決掉上面的 Bug 讓程式更有效率 ( 目前太多迴圈 ) code2020-07-08 第一版 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172 ...

題目： LeetCode - 283. Move Zeroes 題目說明給一個陣列，將陣列中的 0 全部都往最右邊移，而其他數字的順序不變。 解題思路使用一個迴圈，將陣列中不是 0 的從最前面開始放，最後再把 0 補上即可。 參考解法1234567891011class Solution {public: void moveZeroes(vector<int>& nums) { int j = 0, n = nums.size(); for(int i = 0; i < n; ++i) if(nums[i] != 0) nums[j++] = nums[i]; while(j < n) nums[j++] = 0; }};

題目： LeetCode - 53. Maximum Subarray 題目說明給一個陣列，找到具有最大總和的連續子陣列 ( 至少包含一個數字 )，並回傳其總和。 解題思路使用動態規劃的觀念，最大值為 mx + nums[i] 及 nums[i] 兩者取較大者，並隨時更新結果即可。 參考解法12345678910111213class Solution {public: int maxSubArray(vector<int>& nums) { int mx = nums[0], res = mx, n = nums.size(); for(int i = 1; i < n; ++i) { mx = max(mx + nums[i], nums[i]); res = max(res, mx); } return res; }};