2026/03/30

[LeetCode] 1143 Longest Common Subsequence 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
  int longestCommonSubsequence(string s1, string s2) {
    constexpr int SIZE = 1001;
    int dp[SIZE][SIZE] = {0};

    for (int i = 1; i <= s1.length(); i++) {
      for (int j = 1; j <= s2.length(); j++) {
        if (s1[i - 1] == s2[j - 1])
          dp[i][j] = dp[i - 1][j - 1] + 1;
        else
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
    return dp[s1.length()][s2.length()];
  }
};
Labels:

2026/03/29

[LeetCode] 98 Validate Binary Search Tree 

 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
/**
 * 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:
  bool check(TreeNode* node, long long int maxVal, long long int minVal) {
    if (node == nullptr)
      return true;
    if (node->val >= maxVal || node->val <= minVal)
      return false;
    return check(node->left, node->val, minVal) &&
           check(node->right, maxVal, node->val);
  }

  bool isValidBST(TreeNode* root) {
    if (root == nullptr)
      return true;
    return check(root, LONG_MAX, LONG_MIN);
  }
};
Labels:

2026/03/28

[LeetCode] 39 Combination Sum 

 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:
  void dfs(int idx, int size, int sum, int target,
           vector<int>& cur, 
           vector<int>& candidates,
           vector<vector<int>>& ans) {
   
    if (sum > target)
      return;
    if (sum == target) {
      ans.push_back(cur);
      return;
    }
    if (idx >= candidates.size())
      return;
    cur.push_back(candidates[idx]);
    dfs(idx, size + 1, sum + candidates[idx], target, cur, candidates, ans);
    cur.pop_back();
    dfs(idx + 1, size, sum, target, cur, candidates, ans);
  }

  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    std::vector<int> cur;
    dfs(0, 0, 0, target, cur, candidates, ans);
    return ans;
  }
};
Labels:

2026/03/27

[LeetCode] 572 Subtree of Another Tree

當val一樣時

如果已經固定了, 就一定要完全一樣到底

如果尚未固定, 則有兩種選擇

用當前root, 之後固定

不用當前root, 維持不固定

 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
/**
 * 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:
  bool check(TreeNode* root, TreeNode* subRoot, bool fixed) {
    if (root == nullptr && subRoot == nullptr)
      return fixed;
    if (root == nullptr || subRoot == nullptr)
      return false;
    if (root->val != subRoot->val) 
      if (fixed)
        return false;
      else 
        return check(root->left, subRoot, false) ||
               check(root->right, subRoot, false);
    if (fixed)
      return check(root->left, subRoot->left, fixed) && 
             check(root->right, subRoot->right, fixed);

    bool tryRoot = check(root->left, subRoot->left, true) && 
                   check(root->right, subRoot->right, true);
    if (tryRoot)
      return true;
    
    return check(root->left, subRoot, false) ||
           check(root->right, subRoot, false);
  }

  bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    return check(root, subRoot, false);
  }
};
Labels:

2026/03/26

[LeetCode] 338 Counting Bits 

 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:
  #if 1
  vector<int> countBits(int n) {
    vector<int> ans(n + 1);
    ans[0] = 0;
    int leadingOne = 1;
    for (int i = 1; i <= n; i++) {
      if ((leadingOne << 1) == i)
        leadingOne <<= 1; 
      ans[i] = ans[i - leadingOne] + 1;
    }
    return ans;
  }
  #else
  vector<int> countBits(int n) {
    vector<int> ans(n + 1);
    for (int i = 0; i <= n; i++)
      ans[i] = __builtin_popcount(i);
    return ans;
  }
  #endif
};
Labels:

2026/03/25

[LeetCode] 242 Valid Anagram 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.length() != t.length())
      return false;
      
    unordered_map<char, int> chrMap;
    for (auto &c : s)
      chrMap[c]++;

    for (auto &c : t) {
      if (chrMap.find(c) == chrMap.end() || chrMap[c] == 0)
        return false;
      chrMap[c]--;
    }
    return true;
  }
};
Labels:

[LeetCode] 226 Invert Binary Tree 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
  TreeNode* invertTree(TreeNode* node) {
    if (node == nullptr)
      return nullptr;
    TreeNode* invertLeft = invertTree(node->left);
    TreeNode* invertRight = invertTree(node->right);
    node->left = invertRight;
    node->right = invertLeft;
    return node;
  }
};
Labels:

2026/03/23

[LeetCode] 217 Contains Duplicate 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
  bool containsDuplicate(vector<int>& nums) {
    std::unordered_set<int> set;
    for (auto &num : nums) {
      if (set.count(num)) 
        return true;
      else 
        set.insert(num);
    } 
    return false;
  }
};
Labels:

2026/03/22

[LeetCode] 125 Valid Palindrome 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  string convert(string s) {
    string ret = "";
    for (auto &c : s)
      if (isalpha(c) || isdigit(c))
        ret += tolower(c);

    return ret;
  }

  bool isPalindrome(string s) {
    s = convert(s);
    int len = s.length();
    for (int i = 0; i < len; i++)
      if (s[i] != s[len - i - 1])
        return false;
    return true;
  }
};
Labels:

[LeetCode] 121 Best Time to Buy and Sell Stock 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int ans = 0;
    int minPrice = INT_MAX;
    
    for (auto &p : prices) {
      minPrice = min(minPrice, p);
      ans = max(ans, p - minPrice);
    }

    return ans;
  }
};
Labels:

2026/03/21

[LeetCode] 104 Maximum Depth of Binary Tree 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
  int dfs(TreeNode* node, int depth) {
    if (node == nullptr)
      return depth - 1;
    return max(dfs(node->left, depth + 1), dfs(node->right, depth + 1));
  }

  int maxDepth(TreeNode* root) {
    return dfs(root, 1);
  }
};
Labels:

[LeetCode] 100 Same Tree 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr)
      return true;
    if (p == nullptr || q == nullptr)
        return false;
    if (p->val != q->val)
      return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
  }
};
Labels:

2026/03/20

[LeetCode] 191 Number of 1 Bits 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  #if 0
  int hammingWeight(int n) {
    std::bitset<32> bs(n);
    return bs.count();
  }
  #endif

  int hammingWeight(int n) {
    int ans = 0;
    while(n) {
      n = n & (n - 1);
      ans++;
    }
    return ans;
  }
};
Labels:

2026/03/19

[LeetCode] 70 Climbing Stairs 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
  static constexpr int SIZE = 46;
  int cache[SIZE];
  int dp(int x) {
    if (cache[x])
      return cache[x];
    if (x <= 1) {
      cache[x] = dp(x - 1);
      return cache[x];
    }
    cache[x] = dp(x - 1) + dp(x - 2);
    return cache[x];
  }

  int climbStairs(int n) {
    std::fill(std::begin(cache), std::end(cache), 0);
    cache[0] = 1;
    return dp(n);
  }
};
Labels:

2026/03/16

[LeetCode] 190 Reverse Bits 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
  int reverseBits(int n) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
      ans <<= 1;
      ans |= (n & 1) ;
      n >>= 1;
    }
    return ans;
  }
};
Labels:

2026/03/14

[LeetCode ] 20 Valid Parentheses 

 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
class Solution {
public:
  std::unordered_map<char, char> parMap = {
    {')', '('},
    {']', '['},
    {'}', '{'}
  };
  std::unordered_set<char> leftParSet = {'(', '[', '{'};

  bool processRight(std::stack<char> &stack, char c) {
    cout << "right : c = " << c << endl;
    if (stack.size() == 0)
      return false;
    if (stack.top() != parMap[c])
      return false;
    stack.pop();
    return true;
  }
  
  bool isValid(string s) {
    std::stack<char> stack;
    for (char c : s)
      if (leftParSet.count(c)) 
        stack.push(c);
      else if (!processRight(stack, c)) 
        return false;
      
    return stack.size() == 0;
  }
};
Labels:

2026/03/13

[LeetCode] 268 Missing Number

n個數字只會出現n-1個

先把所有index : 0~n-1都XOR在一起

再把所有數字XOR在一起

結果就是沒出現的那個數字

因為input的數量少一個, 所以要記得多把nums.size()給XOR進來

1
2
3
4
5
6
7
8
9
class Solution {
public:
  int missingNumber(vector<int>& nums) {
    int x = nums.size();
    for (int i = 0; i < nums.size(); i++)
      x = x ^ i ^ nums[i];
    return x;
  }
};
Labels:

2026/03/09

[LeetCode] 23 Merge k Sorted Lists 

 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* startNode = new ListNode(5566);
    ListNode* curNode = startNode;

    while (list1 != nullptr && list2 != nullptr) {
      if (list1->val <= list2->val) {
        curNode->next = list1;
        list1 = list1->next;
      }
      else {
        curNode->next = list2;
        list2 = list2->next;
      }
      curNode = curNode->next;
    }

    if (list1 != nullptr && list2 == nullptr)
      curNode->next = list1;
    else if (list1 == nullptr && list2 != nullptr)
      curNode->next = list2;

    return startNode->next;
  }
  
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.size() == 0)
      return nullptr;
    ListNode* head = lists[0];
    for (int i = 1; i < lists.size(); i++)
      head = mergeTwoLists(head, lists[i]);
    return head;
  }
};
Labels:

2026/03/08

[Leetcode] 15 3Sum 

 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
class Solution {
public:
  int moveForward(std::vector<int> &nums, int idx) {
    while (idx + 1 < nums.size() && nums[idx] == nums[idx + 1])
      idx++;
    return idx + 1;
  }

  int moveBackward(std::vector<int> &nums, int idx) {
    while (idx -1 >= 0 && nums[idx] == nums[idx - 1])
      idx--;
    return idx - 1;
  }
  
  void twoSum(std::vector<int> &nums, int fixed, vector<vector<int>> &ans) {
    int left = fixed + 1;
    int right = nums.size() - 1;
    while(left < right) {
      if (nums[left] + nums[right] == -nums[fixed]) {
        ans.push_back({nums[fixed], nums[left], nums[right]});
        left = moveForward(nums, left);
        right = moveBackward(nums, right);
      }
      else if (nums[left] + nums[right] < -nums[fixed]) 
        left = moveForward(nums, left);
      else if (nums[left] + nums[right] > -nums[fixed]) 
        right = moveBackward(nums, right);
    }
  }

  vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    for (int i = 0; i < nums.size(); i = moveForward(nums, i)) 
      twoSum(nums, i, ans);
    return ans;
  }
};
Labels:

2026/03/06

[LeetCode] 54 Spiral Matrix 

 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
class Solution {
public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {
    constexpr int MAX = 11;
    bool vis[MAX][MAX] = {0};
    
    vector<int> ans;
    int M = matrix.size();
    int N = matrix[0].size();

    auto isValid = [&](int x, int y) -> bool {
      return x >= 0 && x < M && y >=0 && y < N;
    };

    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    int x = 0;
    int y = 0;
    int i = 0;    
    while (true) {
      ans.push_back(matrix[x][y]);
      if (ans.size() == M * N)
        break;
        
      vis[x][y] = true;
      while (!isValid(x + dx[i], y + dy[i]) || vis[x + dx[i]][y + dy[i]]) 
        i = (i + 1) % 4;

      x = x + dx[i];
      y = y + dy[i];
    }
    return ans;
  }
};
Labels:
訂閱： 文章 (Atom)