題目： LeetCode - 560. Subarray Sum Equals K 題目說明給一個陣列及一個 k，求陣列中連續子陣列的和等於 k 的個數。 解題思路使用一個迴圈，sum 為從 nums[0] 加到當前元素的值，使用 unordered_map<int, int> 紀錄子陣列和出現的次數。對於 sum 來說，每次得到新的 sum 時，若是前面的子陣列和有出現 sum - k 的話，代表新的子陣列和減掉舊的子陣列和就會得到 k，所以每次迴圈 count 都加上 hash[sum - k]，最後回傳 count 即可。 參考解法123456789101112131415161718class Solution {public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(); if(!n) return 0; unordered_map<int, int> ha ...

題目： LeetCode - 1008. Construct Binary Search Tree from Preorder Traversal 題目說明給一個陣列，將陣列造成一個二元搜尋樹。 解題思路 想法：樹根的值一定是 preorder[0]，使用 pos 來記數，然後先建左邊，建到 preorder[pos] 大於樹根的值時再建右邊。 作法：使用遞迴即可。 參考解法123456789class Solution {public: int pos = 0; TreeNode* bstFromPreorder(vector<int>& preorder, int max = INT_MAX) { if(pos == preorder.size() || preorder[pos] > max) return nullptr; return new TreeNode(preorder[pos], bstFromPreorder(preorder, preorder ...

題目： LeetCode - 33. Search in Rotated Sorted Array 題目說明給一個排序過的陣列，但是反轉一部份，給一個 target 求它在陣列中的 index，若不在陣列中則回傳 - 1。※ 題目希望時間複雜度為 O(log n) 解題思路基本為二分搜尋法，但是因為陣列反轉過，所以會有一些其他的規則，舉例子並自己設 target 就能找出其中的規則。以下是我觀察到的規則： 如果 nums[mid] > target 如果 nums[0] > nums[mid] 則 target 會在左邊這一段。 如果 nums[0] < nums[mid] 如果 nums[0] > target 則 target 會在右邊這一段。 如果 nums[0] < target 則 target 會在左邊這一段。 如果 nums[mid] < target 如果 nums[0] > nums[mid] 如果 nums[0] > target 則 target 會在右邊這一段。 如果 nums[0] < tar ...

題目： LeetCode - 64. Minimum Path Sum 題目說明給一個二維陣列，求從左上走到右下的最小數字和。 解題思路因為只能往右邊走或往下面走，所以 走到每個點的最短距離 為 走到左邊的點的最短距離 和 走到上面的點的最短距離 取最小值，根據此想法做動態規劃即可。 參考解法123456789101112class Solution {public: int minPathSum(vector<vector<int>>& grid) { int height = grid.size(), width = grid[0].size(); vector<vector<int>> dp(height + 1, vector<int>(width + 1, INT_MAX)); dp[0][1] = 0; for(int i = 1; i <= height; ++i) for(int j = 1 ...

題目： LeetCode - 200. Number of Islands 題目說明給一個二維的陣列當作 2d 地圖，1 代表土地，0 代表海水，求出地圖中島嶼的數量。( 上下左右相鄰的 1 代表同一座島 ) 解題思路將整個地圖訪問一次，若碰到 1 就使用遞迴的概念將相鄰的 1 都設成 0，做完一次代表找到一個島。 參考解法12345678910111213141516171819202122232425class Solution {public: void mark(vector<vector<char>>& grid, int i, int j, int height, int width) { if(i < 0 || j < 0 || i >= height || j >= width || grid[i][j] != '1') return; grid[i][j] = '0'; ma ...

題目： LeetCode - 678. Valid Parenthesis String 題目說明給一個字串，裡面只會有三種字元，(、)、*，要求檢驗字串是否有效。字串有效須滿足以下條件： 任何的左括弧必須要有對應的右括弧 任何的右括弧必須要有對應的右括弧 左括弧必須在對應的右括弧前面 ※ * 號可代表左括弧、右括弧或空字元。 解題思路可想像成左括弧會與最近的右括弧相消，所以使用一個 count 來記數，碰到左括弧就 + 1，碰到右括弧就 - 1。但是由於還有一個 * 號，而 * 可以是左括弧、右括弧或空字元，所以它可能會 + 1、- 1、或不變，以至於我們的 count 會是一個範圍，所以使用 max、 min 來做記數。在碰到括弧時一樣正常的 + 1、- 1，但碰到 * 號的話，max + 1、min - 1，而在做的期間 max 不可小於 0，因為 max 小於 0 的話代表會有右括弧前面沒有對應的左括弧，那這個字串就一定不是有效的，所以就直接回傳 False，而 min 也不能小於 0，因為 min 若是 0 的話代表 * 號只能當作左括弧或空字元，不能是右括弧。 參考 ...

題目： LeetCode - 238. Product of Array Except Self 題目說明給一個陣列 nums，要求回傳一個陣列 res，res[i] 的值為除了 nums[i] 以外，其他所有位於 nums 的元素的乘積。 解題思路 解法一：定義一個 index 起始值為 - 1，訪問 nums 內所有元素，當碰到 0 時，把 index 儲存，若再碰到 0，則代表整個 res 都是 0，可以直接回傳。若只有 1 個 0，則 res[index] = all，其餘都為 0，否則 res[i] = all / nums[i]。 解法二：對於 res 來說，res[i] = (nums[0] * nums[1] * ... * nums[i - 1]) * (num[nums.size() - 1] * num[nums.size() - 2] * ... * nums[i + 1])，所以使用一個陣列計算右邊的部分，左邊的部分直接在迴圈做即可得到 res。 參考解法解法一： 1234567891011121314151617181920class Soluti ...

題目： LeetCode - 1. Two Sum 題目說明給一個陣列和一個 target，找出陣列中兩數相加等於 target 的 index。 解題思路使用 unordered_map<int, int> 存放資料，key 存放 nums 裡面的元素的值，value 存放該值的 index。當每次訪問 nums 的元素時，若 target - nums[i] 的值在 map 中有出現表示找到答案，即為 map[target - nums[i]] 和 i，若沒出現則將 {nums[i]], i} 插入 map。 參考解法12345678910111213class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); ++i) ...

題目： LeetCode - 525. Contiguous Array 題目說明給一個陣列，找出一段裡面 0 和 1 個數相等的最長子陣列。 解題思路定義一個 target，當每次訪問 nums 的元素時，若元素為 1 則 + 1，若為 0 則 - 1，並查詢這個 target 是否出現過，若有則代表這一段子陣列裡面的 0 和 1 的個數相等。使用 unordered_map<int, int> 存放資料，key 為 target，value 為該 target 的 index。 參考解法1234567891011121314151617class Solution {public: int findMaxLength(vector<int>& nums) { int target = 0, maxLength = 0, n = nums.size(); unordered_map<int, int> map; map.insert({0, -1}) ...

題目： LeetCode - 1046. Last Stone Weight 題目說明給一個陣列，每次找出最大及次大的值，若是兩者相同則消除，否則消除小的，而大的值改為兩者相減。 解題思路 解法一：每次都從陣列中取出最大及次大的值，並同時將陣列該位置的值改為 0。使用 pair 儲存，first 放值，second 放 index。 解法二：使用 priority queue。 參考解法解法一： 12345678910111213141516171819202122232425class Solution {public: pair<int, int> findMax(vector<int>& stones) { pair<int, int> max; max = {stones[0], 0}; for(int i = 1; i < stones.size(); ++i) if(stones[i] > ma ...