題目： LeetCode - 733. Flood Fill 題目說明給一個二維的陣列當作 2d 圖片，陣列裡面的元素代表該座標的顏色，給一個座標及一個 newColor 做填滿顏色的動作 ( 與小畫家的 填入色彩 類似)。 解題思路先判斷舊顏色和新顏色是否相同，若相同就直接回傳 image，否則就從該點使用遞迴的概念替換顏色即可。 參考解法1234567891011121314151617181920class Solution {public: void fill(vector<vector<int>>& image, int i, int j, int oldColor, int newColor, int height, int width) { if(i < 0 || j < 0 || i >= height || j >= width || image[i][j] != oldColor) return; image[i][j] = ...

題目： LeetCode - 997. Find the Town Judge 題目說明給一個整數及一個陣列，整數代表某個城鎮的居民總數，陣列代表某個城鎮居民的信任關係，例如 [1, 2] 就代表居民 1 信任居民 2。題目要求我們找到城鎮中的法官，而法官會有以下特點： 法官被其他所有人所信任 法官不相信任何人 ※ 陣列中不會有重複的信任關係，例如居民 1 信任居民 2，則 [1, 2] 就會出現在陣列中並且只會出現一次。 解題思路使用一個陣列來紀錄居民們的信任關係，trusts[i][0] 代表居民 i 相信幾個人，trusts[i][1] 代表居民 i 被幾個人所信任。而法官必須滿足以下條件： trusts[i][0] == 0：因為法官不能相信任何人。 trusts[i][1] == N - 1：因為法官必須被除了自己以外的所有人所信任。 若是居民 i 滿足以上的條件，則居民 i 就是法官。 參考解法1234567891011121314151617181920// fast IOstatic auto __ = [](){ std::ios_base:: ...

當我們在用 C++ 解 LeetCode 的題目時，如果你覺得你的演算法已經很極致了，但是時間卻還是比別人慢，這時可能就是因為測資比較龐大，導致 I/O 需要花比較多的時間。而使用 C++ 解題的話，預設會使用 cin 來做測資的輸入，但是在使用 cin/cout 時，由於緩存及一些其他的問題，速度會比 scanf/printf 來的慢，所以如果是在程式競賽的時候，通常我們會使用 scanf/printf 來代替 cin/cout。但是在做 LeetCode 的題目時，LeetCode 會自動幫我們輸入測資，而它輸入的方法就是使用 cin，所以我們可以自己添加以下代碼，使得 cin/cout 的速度能和 scanf/printf 一樣快。 12345678// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}(); 只要把它添加在最前面即可 ...

題目： LeetCode - 367. Valid Perfect Square 題目說明給一個整數，求此數是否是完全平方數。( 開根號後還是整數 )※ 題目要求不要使用包含在 Library 內的 Function，如 sqrt()… 等等。 解題思路使用二元搜尋法即可。 參考解法12345678910111213141516171819class Solution {public: bool isPerfectSquare(int num) { int left = 1, right = num; long long mid, squareMid; while(left <= right) { mid = left + (right - left) / 2; squareMid = mid * mid; if(squareMid == num) return true; ...

題目： LeetCode - 1232. Check If It Is a Straight Line 題目說明給一個陣列，元素代表在 2d 座標中的點，求裡面所有的點是否在同一條線上。 解題思路數學題，判斷斜率即可。 參考解法1234567891011class Solution {public: bool checkStraightLine(vector<vector<int>>& coordinates) { int n = coordinates.size(); int dx = coordinates[1][0] - coordinates[0][0], dy = coordinates[1][1] - coordinates[0][1]; for(int i = 2; i < n; ++i) if(dy * (coordinates[i][0] - coordinates[0][0]) != dx * (coordinates[i][1] - ...

題目： LeetCode - 993. Cousins in Binary Tree 題目說明給一個 Binary Tree，兩個值，求該值是否在同一層且父節點不同。 解題思路使用 pair<int, int> 紀錄，first 放父節點的值，second 放深度。再使用遞迴計算即可。 參考解法123456789101112131415161718192021class Solution {public: pair<int, int> get(TreeNode* root, int target, int depth, int father) { if(!root) return {father, -1}; if(root->val == target) return {father, depth}; auto left = get(root->left, target, ++depth, ...

題目： LeetCode - 169. Majority Element 題目說明給一個陣列，求此陣列中出現最多次的數字。 解題思路 想法： 想像成是消去法，將數字兩兩消去，最後剩下的一定是出現最多次的那個數字。 作法： 定義一個 num 紀錄數字，count 紀錄該數字出現的次數。使用一個迴圈，當碰到數字和 num 不同時就把 count - 1，若 count 剩下 0 時，把 num 換成該數，count 設為 1。 參考解法123456789101112class Solution {public: int majorityElement(vector<int>& nums) { int num, count = 0; for(auto i : nums) if(i == num) ++count; else if(--count <= 0) num = i, count = 1; ...

題目： LeetCode - 387. First Unique Character in a String 題目說明給一個字串，求字串中只出現過一次的字元的 index。 解題思路使用一個陣列儲存字元出現的次數即可。由於測資只包含小寫的英文字母，所以陣列大小設為 26。 參考解法123456789101112class Solution {public: int firstUniqChar(string s) { int count[26] = {}, n = s.size(); for(auto i : s) ++count[i - 'a']; for(int i = 0; i < n; ++i) if(count[s[i] - 'a'] == 1) return i; return -1; }};

題目： LeetCode - 476. Number Complement 題目說明給一個數字，求這個數字的補數。補數的取法就是將數字轉為二進制，然後對代表數字的部分做 not 運算。例如： 12345： 00 00000 00000 00000 00000 00000 00|101 ^ 從這裡開始2： 00 00000 00000 00000 00000 00000 00|010所以 5 的補數就是 2。 解題思路先找出他代表數字的地方有幾位，求法就是一直往右推直到整個數字為 0。然後將數字往左推 count 位數，再使用 ~ 運算符對數字做 not 運算，最後再把 0 給推回去即可。※ 關於 << 及 >> 運算符的介紹可參考本篇文章：LeetCode - 201 解題紀錄 參考解法123456789class Solution {public: int findComplement(int num) { int count = 32, ...

題目： LeetCode - 383. Ransom Note 題目說明給兩個字串 ransomNote、magazine，求 ransomNote 是否能由 magazine 組成。對於一個字元來說，在 magazine 中出現的次數需大於等於在 ransomNote 中出現的次數。 解題思路使用一個陣列儲存字元出現的次數即可。由於測資只包含小寫的英文字母，所以陣列大小設為 26。 參考解法1234567891011121314class Solution {public: bool canConstruct(string ransomNote, string magazine) { int count[26] = {}; for(auto i : ransomNote) ++count[i - 'a']; for(auto i : magazine) --count[i - 'a']; for( ...