第25個冬天

  LeetCode常見題目 LeetCode 1. Two Sum LeetCode 268. Missing Number LeetCode 283. Move Zeroes LeetCode 26. Remove Duplicates from Sorted Array LeetCode 27.Remove Element LeetCode.485. Max Consecutive Ones

將陣列內指定的元素移除, 後面的元素往前推 這道題讓我們移除一個陣列中和給定值相同的數字，並返回新的陣列的長度。 (PS:不可以使用另外的陣列來處理，全部的操作都要在同一個陣列中。) 只需要一個變數用來計數，然後遍歷原數組，如果當前的值和給定值不同，就把當前值覆蓋計數變數的位置，並將計數變數加1。 class Solution { public:     int removeElement(vector<int>& nums, int val) {         int res = 0 ;          for ( int i = 0 ; i < nums.size(); ++ i) {              if (nums[i] != val) nums[res++] = nums[i];         }         return res;     } }; Ref: https://dotblogs.com.tw/abbee/2022/09/21/104648 https://www.cnblogs.com/grandyang/p/4606700.html

給一個排序過的陣列，移除重複的值，每個元素只能留下一個。 不能使用其他的陣列空間，必需在本來的陣列中操作。 備註:直接修改輸入的陣列，空間複雜度應為O(1) 範例： [1,1,2] 去除重複的1之後，剩下[1,2]，回傳陣列的長度2。 跟 LeetCode 283. Move Zeroes 很像，差別在於283移除的是0，這題移除的是重複的數字 時間複雜度:O(N) 空間複雜度O(1) class Solution { public:     int removeDuplicates(vector<int>& nums) {         int count = 1;         for(int i=0;i<nums.size();i++){             if(nums[count-1] != nums[i]){                 nums[count] = nums[i];                 count++;             }         }         return count;     } }; 移動不重複元素至陣列開頭 Step1.紀錄要改動的陣列位置 index Step2.若當前元素跟前一個元素相比值不同，則代表這是出現的第一個元素 Step3.陣列開頭的第一個元素一定是新的元素 Ref: https://cppsecrets.com/users/1559211698111109981081015450575064103109971051084699111109/C00-Program-to-Remove-Duplicates-from-Sorted-Array.php https://clay-...

給一個裡面元素為int的陣列，陣列中會有兩個元素加起來等於target，回傳這兩個元素的位置。 範例： Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Input: nums = [3,2,4], target = 6 Output: [1,2] 從集合中，找到那兩個加總為 target 的數字，並回傳它們所在的 index。 method.1 Brute Force Time complexity:O(n^2) Space complexity:O(1) 暴力搜索的方法是遍歷所有的兩個數字的組合，然後算其和，這樣雖然節省了空間，但是時間複雜度高。一般來說，為了提高時間的複雜度，需要用空間來換。 class Solution { public:     vector<int> twoSum(vector<int>& nums, int target) {         for(int i = 0; i < nums.size(); i++) {             for(int j = i+1; j < nums.size(); j++) {                 if(nums[i]+nums[j] == target)                     return vector<int>({i,j});             }         }         return {};     } }; method.2 HashMap(HashTab...

找出陣列中最長的連續 1 https://leetcode.com/problems/max-consecutive-ones/description/ class Solution { public:     int findMaxConsecutiveOnes(vector<int>& nums) {         int result = 0,tmp=0;         for(auto x: nums){             if(x==1){                 tmp++;             }else{                 tmp=0;             }             if(result<tmp){                 result = tmp;             }         }         return result;     } };

  For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. https://leetcode.com/problems/move-zeroes/ class Solution { public:     void moveZeroes(vector<int>& nums) {         vector<int> v;         int count_of_zero=0;         for(int i=0;i<nums.size();i++){             if(nums[i] != 0){                 v.push_back(nums[i]);             }else{                 count_of_zero++;             }         }         int idx=-1;         for(int i=0;i<v.size();i++){             idx++;             cout << v[i] << endl;           ...

問題描述：給定一個二叉樹，返回它的後序遍歷。 ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector< int > postorderTraversal(TreeNode* root) { vector< int > result; if (root == nullptr) { return result; } stack<TreeNode*> nodes; nodes.push(root); while (!nodes.empty()) { TreeNode* node = nodes.top(); nodes.pop(); result.insert(result.begin(), node->val); if (node->left) { nodes.push(node-...

 問題描述：給定一個二叉樹，返回它的前序遍歷。 ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector< int > preorderTraversal(TreeNode* root) { vector< int > result; if (root == nullptr) { return result; } stack<TreeNode*> nodes; nodes.push(root); while (!nodes.empty()) { TreeNode* node = nodes.top(); nodes.pop(); result.push_back(node->val); if (node->right) { nodes.push(node->right); ...

LeetCode 224 題的問題是實現一個基本計算器，可以處理加法、減法、括號和空格。 範例 1： 輸入： s = "1 + 1" 輸出： 2 範例 2： 輸入： s = " 2-1 + 2 " 輸出： 3 範例 3： 輸入： s = "(1+(4+5+2)-3)+(6+8)" 輸出： 23 這個問題可以通過使用棧(Stack)來處理。 棧是一種先進後出的數據結構，對於處理嵌套結構（比如括號）很有用。 可將遍歷輸入字元串並使用兩個棧：一個棧用於存儲操作數，另一個棧用於存儲操作符。 Step1.初始化變數和Stack。 Step2.遍歷字元串中的每個字元： 如果是數字字元，構建當前操作數。 如果是 '+' 或 '-'，更新當前操作符。 如果是 '('，將當前結果和操作符分別入棧，並重置結果和操作符。 如果是 ')'，計算括號內的結果，並從棧中取出之前存儲的結果和操作符。 Step3.計算最後一個操作數。 Step4.返回最終結果。 ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public: int calculate(string s) { stack< int > nums; // 存儲操作數 stack< int > ops; // 存儲操作符 int num = 0 ; // 當前操作數 int result = 0 ; // 最終結果 int sign = 1 ; // 符號，默認為正 for ( char c : s) { if (isdigit(c)) { num = num * 10 + (c - '0' ); // 構建操作數 ...

 LeetCode287 要求找到給定的整數內存中重複的數字 二分查找: 時間複雜度：O(n log n)，其中n是索引的長度。每次二分查找都需要遍歷整個索引 空間複雜度：O(1)，只需要幾個額外的變量來保存狀態，不需要額外的存儲空間。 優點：時間複雜度為 O(n log n)，比線性時間複雜度要好。不需要額外的空間。 缺點：可能需要修改集群本身，破壞原始數據。 1.初始範圍設定：我們將搜索的範圍初始化為 [1, n-1]，其中 n 是備份的長度。因為根據問題描述，備份中的元素範圍是 [1, n]。 2.在每一步中計算中間值mid，並統計集群中小於等於mid的元素個數（記為count）。根據抽屜原理，如果沒有重複數字，count應該小於等於mid。如果count大於mid，說明重複數字一定在左半部分，否則在右半部分。 3.根據上一步的判斷，我們不斷調整搜索範圍，縮小範圍直到找到重複數字。 如果沒有重複數字，那麼每個倉庫中最多只有一個物體（即倉庫中的一個物體）元素），而如果倉庫中有兩個物體，那麼就說明至少有一個倉庫中放了兩個元素，那麼倉庫中存在重複數字。 因為我們在搜索重複數字的時候可以，將集群分割成不同的區間來進行二分查找，而根據抽屜原理，如果有n個抽屜，放入了n+1個物體，那麼至少有一個抽屜中放了兩個物體。 1.程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int findDuplicate(vector< int >& nums) { int left = 1 ; // 最小可能的重複數字 int right = nums.size() - 1 ; // 最大可能的重複數字 while (left < right) { int mid = left + (right - left) / 2 ; // 計算中間值 int count = 0 ; // 統計數組中小於等於 mid 的元素個數 ...

給一個aray，請你將每個元素用它右邊最大的元素替換，如果是最後一個元素，用-1替換。 Input: arr = [17,18,5,4,6,1] Output: [18,6,6,6,1,-1] Explanation:  - index 0 --> the greatest element to the right of index 0 is index 1 (18). - index 1 --> the greatest element to the right of index 1 is index 4 (6). - index 2 --> the greatest element to the right of index 2 is index 4 (6). - index 3 --> the greatest element to the right of index 3 is index 4 (6). - index 4 --> the greatest element to the right of index 4 is index 5 (1). - index 5 --> there are no elements to the right of index 5, so we put -1. ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: vector< int > replaceElements(vector< int >& arr) { int curMax = 0, tmp; for ( int i = arr.size() - 1; i >= 0; i--){ tmp = arr[i]; if (i == arr.size() - 1){ arr[i] = -1; } else { arr[i] = curMax; } ...

 檢查一串括號是否為合法括號，而合法括號的要件是要左括號等於右括號的數量，並且要兩兩成對，且相同類型的括號要配相同類型的括號（譬如大括號要配大括號）。 如果是合法括號就回傳true，否則回傳false。 Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Input: s = "(]" Output: false 從左看到右，只要看到左括號，就把它放進Stack中，而當看到右括號，就看跟Stack最上方(stack.top())的左括號有沒有匹配，如果有的話，就表示目前還是合法的括號，繼續往下看， 而如果不匹配，代表現在的括號已經不合法，可以直接返回False了。 還有一種不合法情況是，先看到右括號但Stack是空的，那這樣也是不合法的，例如"](())"。 ans1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: bool isValid(string s) { set< char > st{ '(' , '[' , '{' }; map< char , char > mp{{ '(' , ')' } ,{ '[' , ']' },{ '{' , '}' }}; stack< char > stk; for ( auto c:s){ if (st.find(c) != st.end()){ stk.push(c); } else { if (stk.empty()) return false; ...

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack.   Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class MinStack { stack< int > data; stack< int > helper; public: MinStack() { } void push( int val) { data.push(val); if (helper.empty() || helper.top() >= val) { helper.push(val); } } void pop() { int top = data.top(); data.pop(); ...

給兩個陣列，一個陣列是紀錄推入 stack 的元素、一個陣列是從 stack 頂部彈出的元素。我們要做的事情就是驗證，在『依照順序推入 stack，並且在需要 pop 特定元素時 pop』這樣的規定中，這個 stack 是否能剛好完全清空。 Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true Explanation: We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2] Output: false Explanation: 1 cannot be popped before 2. 可使用 stack 來依序儲存 pushed 的元素，然後在遇到 popped 的元素跟 stack 頂部相同時彈出。 要注意的是，可能會連續遇到好幾次的 popped 的元素跟 stack 頂部相同，所以需用 while 來解，直到元素不匹配時才停止。 ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: bool validateStackSequences(vector< int >& pushed, vector< int >& popped) { int pop_i = 0; stack< int > st; for ( int i=0; i<pushed.size(); ++i) { st.push(pushed[i]); while (!st.empty() && popped[pop_i] == st.top()) { ...

最長有效括號子字串長度 輸入一個只由 ‘(‘ 或是 ‘)’ 組成的字串，而我們要做的，就是判斷最長的『合理』子字串長度。 比方說， “()” 就是合理的子字串、”)(” 就是個不合理的子字串。 ans1. 從左到右讀一遍、然後再從右讀到左，最後決定最長的長度。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class Solution { public: int longestValidParentheses(string s) { // Init int max_len = 0; int left = 0; int right = 0; // Left to right for ( int i=0; i<s.size(); ++i) { if (s[i] == '(' ) { ++left; } else { ++right; } if (left == right) { max_len = max(max_len, left+right); } else if (left < right) { left = 0; right = 0; } } // Init left = 0; right = 0; // Right t...

 給定一含括弧字串,內另含*符號,可替代為  (  or  ) or 空字元 字串有效須滿足以下條件： 任何的左括弧必須要有對應的右括弧 任何的右括弧必須要有對應的右括弧 左括弧必須在對應的右括弧前面 可想像成左括弧會與最近的右括弧相消，使用一個 count 來記數，碰到左括弧就 + 1，碰到右括弧就 - 1。但由於還有一個 * 號，而 * 可以是左括弧、右括弧或空字元，所以它可能會 + 1、- 1、或不變，以至於我們的 count 會是一個範圍，所以使用 max、 min 來做記數。 在碰到括弧時一樣正常的 + 1、- 1，但碰到 * 號的話，max + 1、min - 1，而在做的期間 max 不可小於 0，因為 max 小於 0 的話代表會有右括弧前面沒有對應的左括弧，那這個字串就一定不是有效的，所以就直接返回 False，而 min 也不能小於 0，因為 min 若是 0 的話代表 * 號只能當作左括弧或空字元，不能是右括弧。 ans1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: bool checkValidString(string s) { int max = 0, min = 0; for ( auto & i : s) { if (i == '(' ) ++min, ++max; else if (i == ')' ) --min, --max; else if (i == '*' ) --min, ++max; if (max < 0) return false; if (min < 0) min = 0; } return min == ...

LeetCode1299. Replace Elements with Greatest Element on Right Side(Easy) https://coolmandiary.blogspot.com/2021/08/leetcode1299-replace-elements-with.html Stack 利用堆疊(Stack)先進後出(FILO,First-in-Last-out)、後進先出(LIFO,Last-In-First-Out=>LIFO)的特性來解題 amazon,google,snapchat,uber,阿里,腾讯,百度,字节 *** LeetCode 155. Min Stack(Medium) https://coolmandiary.blogspot.com/2021/08/leetcode-155-min-stackmediumstack.html amazon,airbnb,facebook,google,microsoft,twitter,阿里,腾讯,百度,字节 *** LeetCode20.Valid Parentheses(Easy) https://coolmandiary.blogspot.com/2021/08/leetcode20valid-parentheseseasystack.html LeetCode946. Validate Stack Sequences(Medium) https://coolmandiary.blogspot.com/2021/08/leetcode946-validate-stack.html LeetCode678. Valid Parenthesis String(Medium) https://coolmandiary.blogspot.com/2021/08/leetcode678-valid-parenthesis.html 阿里,腾讯,百度,字节 *** LeetCode32.Longest Valid Parentheses(Hard) https://coolmandiary.blogspot.com/2021/08/leetcode32longest-valid-parentheseshard.html 阿里,腾讯,百度,字节 *** LeetCode94...

當談論樹的探索方式時，針對二叉樹有以下三種尋訪方式 以下面的例子來看，數字表示樹節點的值。     1    / \   2   3  / \ 4   5 https://s3.amazonaws.com/issac-ghost/2019/03/preorder-traversal.gif 前序遍歷（Preorder Traversal）：按照根節點 -> 左子樹 -> 右子樹的順序遍歷。 結果：1 -> 2 -> 4 -> 5 -> 3 https://s3.amazonaws.com/issac-ghost/2019/03/inorder-traversal.gif 中序遍歷（Inorder Traversal）：按照左子樹 -> 根節點 -> 右子樹的順序遍歷。 結果：4 -> 2 -> 5 -> 1 -> 3 https://s3.amazonaws.com/issac-ghost/2019/03/postorder-traversal.gif 後序遍歷（Postorder Traversal）：按照左子樹 -> 右子樹 -> 根節點的順序遍歷。 結果：4 -> 5 -> 2 -> 3 -> 1 Inorder 中序遍歷:先走訪左子樹，再走訪父節點，再走訪右子樹。從一棵 tree 的 root 開始，只要 root 的左邊還有 node 就代表還有左子樹可以走訪，接著把左邊的 node 當成 root 再看其左邊是否還有子樹，若有則繼續往左走訪直到左邊沒有 node 為止。 Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 遞迴 (recursive) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: void traversal(TreeNode *node, vector< int > &res) { if (node) { ...

 通常假設搜尋對象是一個有序的數列。這種搜尋算法通過將數列分成兩半，並比較中間元素與目標值的大小來迅速定位目標值的位置。 固定左右邊界，用中間值與目標值判斷大小，根據情況收縮左邊界或者右邊界即可。 https://ninagirl1998.medium.com/leetcode-33-search-in-rotated-sorted-array-da1df6111576 https://www.guru99.com/binary-search.html 假設我們有一個有序的整數陣列：[2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]，現在我們想要找到目標值 23 是否在這個陣列中，如果在，我們還希望知道它的索引位置。 傳統的線性搜索方法是從陣列的第一個元素開始，逐一比較直到找到目標值或者確定目標值不存在。但是這種方法的時間複雜度是O(n)，當數列很大時，效率較低。 運用二分搜索的方法 Step1. 首先指定搜索範圍，即整個數列。左邊界設置為0，右邊界設置為陣列長度減1：left = 0，right = 10（假設陣列索引從0開始計算）。 Step2. 接下來，我們計算中間元素的索引：mid = (left + right) / 2 = 5。 Step3.比較中間元素23與目標值23的大小。[2, 5, 8, 12, 16,  23 , 38, 45, 56, 72, 91] 由於它們相等，我們已經找到目標值，並且其索引為5。 Step4.搜索結束。 透過二分搜索，我們只用了幾次比較就找到了目標值的位置。這種方法的時間複雜度是O(log n)，比線性搜索的O(n) 效率更高。當數列很大時，二分搜索的優勢就會體現出來。 在有序數列中，二分搜索的平均時間複雜度是O(log n)，非常高效。特別在大數據量下，相比於線性搜索的O(n)，速度快得多。 二分搜索是一種高效的搜尋算法，特別適用於有序數列。它通過將搜索範圍分為兩半來迅速定位目標值，從而大大節省了搜索的時間。 69. Sqrt(x)(Easy) https://leetcode.com/problems/sqrtx/ 題目描述：計算非負整數 x 的平方根。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...