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:

[LeetCode] 409 Longest Palindrome 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
  int longestPalindrome(string s) {
    std::unordered_map<char, int> cntMap;
    for (auto c : s)
      cntMap[c]++;
    int len = 0;
    bool hasOdd = false;
    for (auto &entry : cntMap) {
      int cnt = entry.second;
      if (cnt % 2 == 0)
        len += cnt;
      else {
        len += cnt - 1;
        hasOdd = true;
      }
    }
    if (hasOdd)
      len++;
    return len;
  }
};
Labels:

2026/05/12

[LeetCode] 155 Min Stack

要怎麼知道stack當前元素內的「最小值」?

每次push時, 若當前element比minVal更小

則先把min給push進去, 再push當前element, 並且更新minVal

超有趣, 一次push兩個element進去!!

pop時還可以用這個多push進去的「次小值」還原成「最小值」

 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 MinStack {
private:
  std::stack<int> _stack;
  int minVal;

public:
  MinStack() { minVal = INT_MAX; }

  void push(int x) {
    if (x <= minVal) {
      _stack.push(minVal);
      minVal = x;
    }
    _stack.push(x);
  }

  void pop() {
    int topVal = _stack.top();
    _stack.pop();
    if (topVal == minVal) {
      minVal = _stack.top();
      _stack.pop();
    }
  }

  int top() { return _stack.top(); }

  int getMin() { return minVal; }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
Labels:

[LeetCode] 383 Ransom Note 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
  bool canConstruct(string ransomNote, string magazine) {
    std::unordered_map<char, int> cnt;
    for (auto c : magazine)
      cnt[c]++;
    for (auto c : ransomNote)
      if (cnt[c] > 0)
        cnt[c]--;
      else
        return false;
    return true;
  }
};
Labels:

2026/05/11

[LeetCode] 225 Implement Stack using Queues

用queue模擬stack

每次push時, 先push當前element, 再把所有element從新pop出來 + push進去

 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 MyStack {
private:
  std::queue<int> Q;

public:
  MyStack() {}
  void push(int x) {
    Q.push(x);
    int N = Q.size() - 1;
    for (int i = 0; i < N; i++) {
      Q.push(Q.front());
      Q.pop();
    }
  }

  int pop() {
    int ret = Q.front();
    Q.pop();
    return ret;
  }

  int top() { return Q.front(); }

  bool empty() { return Q.empty(); }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
Labels:

[LeetCode] 278 First Bad Version

二分搜真的很難= ="

index從1開始又要怎麼處理?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
  int firstBadVersion(int N) {
    int left = 1;
    int right = N;
    int ans = N;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (!isBadVersion(mid)) {
        left = mid + 1;
      }
      else {
        ans = mid;
        right = mid - 1;
      }
    }
    return ans;
  }
};
Labels:

2026/05/10

[LeetCode] 232 Implement Queue using Stacks

用兩個stack模擬queue的FIFO行為

一個input stack負責push

一個output stack負責pop

要pop的時候, 把input倒過來推進去output

要怎麼做到amortized O(1)呢 ?

不是每次pop都要把全部元素pop+push一次

而是只要output stack空掉的時候再從input stack倒element出來即可

 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 MyQueue {
private:
  std::stack<int> input;
  std::stack<int> output;

  // amortized O(1)
  void sync() {
    if (!output.empty())
      return;
    while (!input.empty()) {
      int tmp = input.top();
      output.push(tmp);
      input.pop();
    }
  }

public:
  MyQueue() {}

  void push(int x) { input.push(x); }

  int pop() {
    sync();
    int tmp = output.top();
    output.pop();
    return tmp;
  }

  int peek() {
    sync();
    return output.top();
  }

  bool empty() { return input.empty() && output.empty(); }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
Labels:

[LeetCode] 169 Majority Element 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
  int majorityElement(vector<int>& nums) {
    int ans;
    int cnt = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (cnt == 0)
        ans = nums[i];
      if (ans == nums[i])
        cnt++;
      else
        cnt--;
    }
    return ans;
  }
};
Labels:

[LeetCode] 46 Permutations 

 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 {
private:
  int N;
  vector<bool> used;
  vector<vector<int>> ans;
  vector<int> cur;
  void dfs(int idx, vector<int> &nums) {
    if (idx == N) {
      ans.push_back(cur);
      return;
    }
    for (int i = 0; i < N; i++) {
      if (!used[i]) {
        used[i] = true;
        cur[idx] = nums[i];
        dfs(idx + 1, nums);
        used[i] = false;
      }
    }
  }

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

[LeetCode] 110 Balanced 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
32
/**
 * 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:
  bool _isBalanced;
  int dfs(TreeNode *node) {
    if (!node)
      return 0;
    int leftHeight = dfs(node->left);
    int rightHeight = dfs(node->right);
    if (std::abs(leftHeight - rightHeight) > 1)
      _isBalanced = false;
    return std::max(leftHeight, rightHeight) + 1;
  }

public:
  bool isBalanced(TreeNode *root) {
    _isBalanced = true;
    dfs(root);
    return _isBalanced;
  }
};
Labels:

2026/05/09

[LeetCode] 67 Add Binary 

 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
52
class BinaryInteger {
private:
  std::vector<bool> _bits;

public:
  BinaryInteger() : _bits(1, false) {}
  BinaryInteger(const std::string &s) {
    int len = s.size();
    _bits.resize(len);
    for (int i = 0; i < len; i++)
      _bits[i] = (s[len - i - 1] == '1');
  }

  string to_string() const {
    std::string s;
    s.reserve(_bits.size());
    for (int i = _bits.size() - 1; i >= 0; i--)
      if (_bits[i])
        s += '1';
      else
        s += '0';
    return s;
  }

  friend BinaryInteger operator+(const BinaryInteger &a,
                                 const BinaryInteger &b) {
    BinaryInteger out;
    out._bits.clear();
    int carry = 0;
    int len = std::max(a._bits.size(), b._bits.size());
    for (int i = 0; i < len || carry != 0; i++) {
      int sum = carry;
      if (i < a._bits.size())
        sum += a._bits[i];
      if (i < b._bits.size())
        sum += b._bits[i];
      out._bits.push_back(sum % 2);
      carry = sum / 2;
    }
    return out;
  }
};

class Solution {
public:
  string addBinary(string strA, string strB) {
    BinaryInteger A(strA);
    BinaryInteger B(strB);
    BinaryInteger C = A + B;
    return C.to_string();
  }
};
Labels:

2026/05/08

[LeetCode] Blind 75 完食

Blind 75 完食!!

(除了鎖起來的6題)


Labels:

[LeetCode] 57 Insert Interval 

 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:
  vector<vector<int>> insert(vector<vector<int>> &intervals,
                             vector<int> &newInterval) {
    vector<vector<int>> ans;
    int newStart = newInterval[0];
    int newEnd = newInterval[1];
    int N = intervals.size();
    int i = 0;

    // step 1 : non-overlap left
    for (; i < N && intervals[i][1] < newStart; i++)
      ans.push_back(intervals[i]);

    // step 2 : merge overlap interval
    for (; i < N && intervals[i][0] <= newEnd; i++) {
      newStart = min(newStart, intervals[i][0]);
      newEnd = max(newEnd, intervals[i][1]);
    }
    ans.push_back({newStart, newEnd});

    // step 3 : non-overlap right
    for (; i < N; i++)
      ans.push_back(intervals[i]);

    return ans;
  }
};
Labels:

2026/05/07

[LeetCode] 56 Merge Intervals 

 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
class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    std::sort(intervals.begin(), intervals.end(),
      [](const vector<int>& v0, const vector<int>& v1) {
        if (v0[0] == v1[0])
          return v0[1] < v0[1];
        return v0[0] < v1[0];
      });
    vector<vector<int>> ans;
    int start = intervals[0][0];
    int end = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) {
      if (intervals[i][0] > end) {
        ans.push_back({start, end});
        start = intervals[i][0];
        end = intervals[i][1];
      }
      else {
        end = max(end, intervals[i][1]);
      }
    }
    ans.push_back({start, end});
    return ans;
  }
};
Labels:

2026/05/05

[LeetCode] 435 Non-overlapping Intervals

Greedy

排序區間 : 以終點從小到大

「當前區間」是能向前走最少的區間了

若「下一個區間」跟「當前區間」有重疊

則代表「下一個區間」一定更早出發, 且一定向前走得更遠, 或至少一樣遠

所以「下一個區間」一定比「當前區間」覆蓋更多其他區間

因此把「下一個區間」刪掉肯定穩賺不賠

 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:
  int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    std::sort(intervals.begin(), intervals.end(),
      [](const vector<int>& v0, const vector<int>& v1) {
        if (v0[1] == v1[1])
          return v0[0] < v0[0];
        return v0[1] < v1[1];
      });

    int remove = 0;
    int last = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) {
      int start = intervals[i][0];
      int end = intervals[i][1];
      if (start >= last)
        last = end;
      else
        remove++;
    }
    return remove;
  }
};
Labels:

2026/05/04

[LeetCode] 55 Jump Game 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
  bool canJump(vector<int>& nums) {
    int N = nums.size();
    int maxJump = 0;
    for (int i = 0; i < N; i++) {
      if (maxJump < i)
        break;
      maxJump = max(maxJump, i + nums[i]);
    }
    return maxJump >= N - 1;
  }
};
Labels:

2026/05/02

[LeetCode] 297 Serialize and Deserialize Binary Tree

因為會用自產自銷的方式來測試serialize

所以要怎麼表示nullptr的節點可以自己決定

 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
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
  static constexpr char NULLVAL = 'X';
  void serializeImpl(TreeNode *root, ostringstream &os) {
    if (root) {
      os << root->val << ' ';
      serializeImpl(root->left, os);
      serializeImpl(root->right, os);
    }
    else 
      os << NULLVAL << ' ';
  }

  TreeNode* deserializeImpl(istringstream &is) {
    string str;
    is >> str;
    if (str.size() == 1 && str[0] == NULLVAL) 
      return nullptr;
    TreeNode *root = new TreeNode(std::stoi(str));
    root->left = deserializeImpl(is);
    root->right = deserializeImpl(is);
    return root;
  }

public:

  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    ostringstream os;
    serializeImpl(root, os);
    return os.str();
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    istringstream is(data);
    return deserializeImpl(is);
  }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
Labels:

2026/05/01

[LeetCode] 295 Find Median from Data Stream 

 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
class MedianFinder {
private:
  std::vector<int> v;
public:
  void addNum(int num) {
    auto it = std::lower_bound(v.begin(), v.end(), num);
    v.insert(it, num);
  }
  
  double findMedian() {
    int N = v.size();
    if (N % 2 == 1)
      return v[N / 2];
    double left = v[N / 2]; 
    double right = v[N / 2 - 1];
    return (left + right) / 2.0;
  }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
Labels:
訂閱： 文章 (Atom)