2026/05/26

[LeetCode] 310 Minimum Height Trees 

 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
class Solution {
public:
  vector<int> findMinHeightTrees(int N, vector<vector<int>> &edges) {
    if (N == 1)
      return vector<int>({0});
    queue<int> Q;
    vector<vector<int>> G(N);
    vector<int> inDegree(N);
    for (auto &edge : edges) {
      int u = edge[0];
      int v = edge[1];
      G[u].push_back(v);
      G[v].push_back(u);
      inDegree[u]++;
      inDegree[v]++;
    }

    for (int i = 0; i < N; i++)
      if (inDegree[i] == 1)
        Q.push(i);

    int size = N;
    while (size > 2) {
      int leafSize = Q.size();
      size -= leafSize;
      for (int i = 0; i < leafSize; i++) {
        int cur = Q.front();
        Q.pop();
        for (int adj : G[cur]) {
          inDegree[adj]--;
          if (inDegree[adj] == 1)
            Q.push(adj);
        }
      }
    }

    vector<int> ans;
    while (!Q.empty()) {
      ans.push_back(Q.front());
      Q.pop();
    }
    return ans;
  }
};
Labels:

2026/05/25

[LeetCode] 438 Find All Anagrams in a String

用 "==" 直接比較兩個std::unordered_map是否相同
要小心有插入過但又歸零的key
跟從沒插入過是不等價的
所以要檢查是否有在pattern字串裡
才能插入std::unordered_map

 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
class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    if (p.size() > s.size())
      return vector<int>();

    unordered_map<char, int> patMap;
    unordered_map<char, int> curMap;
    vector<int> ans;

    for (int i = 0; i < p.size(); i++)
      patMap[p[i]]++;

    for (int i = 0; i < p.size(); i++)
      if (patMap.count(s[i]))
        curMap[s[i]]++;

    if (patMap == curMap)
      ans.push_back(0);

    for (int left = 0, right = p.size(); right < s.size(); left++, right++) {
      if (patMap.count(s[left]))
        curMap[s[left]]--;
      if (patMap.count(s[right]))
        curMap[s[right]]++;
      if (curMap == patMap)
        ans.push_back(left + 1);
    }
    return ans;
  }
};
Labels:

2026/05/24

[LeetCode] 973 K Closest Points to Origin 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
  vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    vector<pair<int, int>> v;
    for (int i = 0; i < points.size(); i++) {
      int dis = points[i][0] * points[i][0] + points[i][1] * points[i][1];
      v.push_back(make_pair(dis, i));
    }
    sort(v.begin(), v.end());
    vector<vector<int>> ans;
    for (int i = 0; i < k; i++) 
      ans.push_back(points[v[i].second]);
    return ans;
  }
};
Labels:

2026/05/22

[LeetCode] 542 01 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
35
36
37
38
39
40
41
42
43
44
45
46
47
class Status {
public:
  int x, y, dis;
  Status(int _x, int _y, int _dis) : x(_x), y(_y), dis(_dis) {}
};

class Solution {
private:
  int N, M;
  vector<vector<int>> dis;
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {1, 0, -1, 0};

public:
  vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {
    queue<Status> Q;
    N = mat.size();
    M = mat[0].size();
    dis.resize(N);
    for (int i = 0; i < N; i++) {
      dis[i].resize(M);
      for (int j = 0; j < M; j++) {
        if (mat[i][j] == 0) {
          Q.push(Status(i, j, 0));
          dis[i][j] = 0;
        } else
          dis[i][j] = INT_MAX;
      }
    }

    while (!Q.empty()) {
      Status cur = Q.front();
      Q.pop();
      for (int i = 0; i < 4; i++) {
        int dx = cur.x + dirX[i];
        int dy = cur.y + dirY[i];
        if (dx < 0 || dx >= N || dy < 0 || dy >= M)
          continue;
        if (dis[dx][dy] <= cur.dis + 1)
          continue;
        dis[dx][dy] = cur.dis + 1;
        Q.push(Status(dx, dy, cur.dis + 1));
      }
    }
    return dis;
  }
};
Labels:

2026/05/21

[LeetCode] 199 Binary Tree Right Side View 

 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
/**
 * 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 {
private:
  std::vector<int> ans;
  void dfs(TreeNode *node, int depth) {
    if (!node)
      return;
    if (ans.size() < depth)
      ans.push_back(node->val);
    dfs(node->right, depth + 1);
    dfs(node->left, depth + 1);
  }

public:
  std::vector<int> rightSideView(TreeNode *root) {
    dfs(root, 1);
    return ans;
  }
};
Labels:

2026/05/20

[LeetCode] 416 Partition Equal Subset Sum 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
  bool canPartition(vector<int> &nums) {
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    if ((sum & 1) == 1)
      return false;
    sum >>= 1;
    std::vector<bool> dp(sum + 1, false);
    dp[0] = true;
    for (int num : nums)
      for (int i = sum; i >= num; i--)
        dp[i] = dp[i] || dp[i - num];
    return dp[sum];
  }
};
Labels:

2026/05/19

[LeetCode] 150 Evaluate Reverse Polish Notation 

 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
class Solution {
private:
  bool isOperator(string token) {
    return token == "+" || token == "-" || token == "*" || token == "/";
  }

  int performOp(string op, int x, int y) {
    if (op == "+")
      return x + y;
    if (op == "-")
      return x - y;
    if (op == "*")
      return x * y;
    if (op == "/")
      return x / y;
    std::unreachable();
  }

public:
  int evalRPN(vector<string> &tokens) {
    std::stack<int> stack;
    for (string token : tokens) {
      if (isOperator(token)) {
        int opnd2 = stack.top();
        stack.pop();
        int opnd1 = stack.top();
        stack.pop();
        stack.push(performOp(token, opnd1, opnd2));
      } else
        stack.push(std::stoi(token));
    }
    int result = stack.top();
    return result;
  }
};
Labels:

2026/05/18

[LeetCode] 236 Lowest Common Ancestor of a 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
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
  TreeNode *LCABT(TreeNode *cur, TreeNode *p, TreeNode *q) {
    if (!cur || cur == p || cur == q)
      return cur;
    TreeNode *left = LCABT(cur->left, p, q);
    TreeNode *right = LCABT(cur->right, p, q);
    if (left && right)
      return cur;
    if (left)
      return left;
    return right;
  }

public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    return LCABT(root, p, q);
  }
};
Labels:

2026/05/17

[LeetCode] 78 Subsets 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
  int N;
  std::vector<vector<int>> ans;
  std::vector<int> cur;
  void dfs(int idx, vector<int>& nums) {
    if (idx == N) {
      ans.push_back(cur);
      return;
    }
    cur.push_back(nums[idx]);
    dfs(idx + 1, nums);
    cur.pop_back();
    dfs(idx + 1, nums);
  }

public:
  vector<vector<int>> subsets(vector<int>& nums) {
    N = nums.size();
    cur.clear();
    dfs(0, nums);
    return ans;
  }
};
Labels:

[LeetCode] 17 Letter Combinations of a Phone Number 

 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 {
private:
  int N;
  std::vector<int> digit, cur;
  std::vector<std::string> ans;
  std::unordered_map<int, std::string> phoneMap = {
      {2, "abc"}, {3, "def"},  {4, "ghi"}, {5, "jkl"},
      {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}};

  string makeResult() {
    string result;
    for (int i = 0; i < N; i++)
      result += phoneMap[digit[i]][cur[i]];
    return result;
  }

  void dfs(int idx) {
    if (idx == N) {
      ans.push_back(makeResult());
      return;
    }
    for (int i = 0; i < phoneMap[digit[idx]].size(); i++) {
      cur[idx] = i;
      dfs(idx + 1);
    }
  }

public:
  vector<string> letterCombinations(string digits) {
    for (char c : digits)
      digit.push_back(c - '0');
    N = digit.size();
    cur.assign(N, 0);
    ans.clear();
    dfs(0);
    return ans;
  }
};
Labels:

2026/05/16

[LeetCode] 733 Flood Fill 

 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 {
private:
  int N, M;
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {1, 0, -1, 0};
  void dfs(int x, int y, int color, vector<vector<int>> &image) {
    int originalColor = image[x][y];
    if (originalColor == color)
      return;
    image[x][y] = color;
    for (int i = 0; i < 4; i++) {
      int dx = x + dirX[i];
      int dy = y + dirY[i];
      if (dx >= 0 && dx < N && dy >= 0 && dy < M &&
          image[dx][dy] == originalColor)
        dfs(dx, dy, color, image);
    }
  }

public:
  vector<vector<int>> floodFill(vector<vector<int>> &image, int x, int y,
                                int color) {
    N = image.size();
    M = image[0].size();
    dfs(x, y, color, image);
    return image;
  }
};
Labels:

[LeetCode] 704 Binary Search 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
  int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] == target)
        return mid;
      else if (nums[mid] < target)
        left = mid + 1;
      else
        right = mid - 1;
    }
    return -1;
  }
};
Labels:

2026/05/15

[LeetCode] 994 Rotting Oranges

BFS

 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
class State {
public:
  int x, y, depth;
};

class Solution {
private:
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {1, 0, -1, 0};

public:
  int orangesRotting(vector<vector<int>> &grid) {
    int N = grid.size();
    int M = grid[0].size();
    std::queue<State> Q;

    int fresh = 0;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++)
        if (grid[i][j] == 1)
          fresh++;
        else if (grid[i][j] == 2)
          Q.push(State(i, j, 0));

    int maxDepth = 0;
    int rotten = 0;
    while (!Q.empty()) {
      State cur = Q.front();
      Q.pop();
      maxDepth = std::max(maxDepth, cur.depth);
      for (int i = 0; i < 4; i++) {
        int dx = cur.x + dirX[i];
        int dy = cur.y + dirY[i];
        if (dx >= 0 && dx < N && dy >= 0 && dy < M && grid[dx][dy] == 1) {
          grid[dx][dy] = 2;
          rotten++;
          Q.push(State(dx, dy, cur.depth + 1));
        }
      }
    }
    if (rotten == fresh)
      return maxDepth;
    return -1;
  }
};
Labels:

[LeetCode] 876 Middle of the Linked List 

 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
/**
 * 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 {
private:
  ListNode *takeOneStep(ListNode *node) {
    if (node)
      return node->next;
    return nullptr;
  }

  ListNode *takeTwoStep(ListNode *node) {
    return takeOneStep(takeOneStep(node));
  }

public:
  ListNode *middleNode(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast && fast->next) {
      slow = takeOneStep(slow);
      fast = takeTwoStep(fast);
    }
    return slow;
  }
};
Labels:

2026/05/14

[LeetCode] 75 Sort Colors

這演算法也太可愛

居然還有名字Dutch National Flag Algorithm!!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  void sortColors(vector<int> &nums) {
    int low = 0;
    int mid = 0;
    int high = nums.size() - 1;
    while (mid <= high) {
      if (nums[mid] == 0) {
        std::swap(nums[low], nums[mid]);
        low++;
        mid++;
      } else if (nums[mid] == 1)
        mid++;
      else {
        std::swap(nums[mid], nums[high]);
        high--;
      }
    }
  }
};
Labels:

[LeetCode] 543 Diameter 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
24
25
26
27
28
29
30
31
/**
 * 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 {
private:
  int ans;
  int dfs(TreeNode *node) {
    if (!node)
      return 0;
    int left = dfs(node->left);
    int right = dfs(node->right);
    ans = std::max(ans, left + right);
    return std::max(left, right) + 1;
  }

public:
  int diameterOfBinaryTree(TreeNode *root) {
    ans = 0;
    dfs(root);
    return ans;
  }
};
Labels:

2026/05/13

[LeetCode] 8 String to Integer (atoi) 

 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
class Solution {
private:
  string trimLeadingSpace(string s) {
    int i = 0;
    while (i < s.size() && s[i] == ' ')
      i++;
    return s.substr(i);
  }

  string trimSignedness(string s, int &sign) {
    int i = 0;
    sign = 1;
    if (s[i] == '-') {
      sign = -1;
      i++;
    } else if (s[i] == '+')
      i++;
    return s.substr(i);
  }

  int convert2Int(string s, int sign) {
    int i = 0;
    long long int result = 0;
    while (i < s.size() && std::isdigit(s[i])) {
      result = result * 10 + (s[i] - '0');

      if (sign * result > INT_MAX)
        return INT_MAX;
      if (sign * result < INT_MIN)
        return INT_MIN;

      i++;
    }
    return static_cast<int>(sign * result);
  }

public:
  int myAtoi(string s) {
    s = trimLeadingSpace(s);
    int sign = 1;
    s = trimSignedness(s, sign);
    int ret = convert2Int(s, sign);
    return ret;
  }
};
Labels:
訂閱： 文章 (Atom)