2026/04/30

[LeetCode] 424 Longest Repeating Character Replacement

 Two Pointer

右邊一直向前走

若是當前區間已經不合法, 則更新左邊直到合法為止

國人部落格跟LeetCode官方討論區充斥各種假解

要嘛更新左邊只更新一次

要嘛更新左邊時沒有同步更新當前主要char

不知道是測資太弱還是怎樣= ="

誰說AI時代code review才變得很重要呢?

搜尋引擎時代早就存在的問題

只是goolge search還搜不到一整個會動的code而已

std::max_element回傳的是iterator還要自己「*」

C++真的是太愚蠢了

 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 characterReplacement(string s, int k) {
    int N = s.size();
    std::vector<int> cnt(26);
    int ans = 0;
    int left = 0;
    int primeCnt=0;
    for (int right = 0; right < N; right++) {
      int rightIdx = s[right] - 'A';
      cnt[rightIdx]++;
      primeCnt = max(primeCnt, cnt[rightIdx]);
      while ((right - left + 1) - primeCnt > k) {
        int leftIdx = s[left] - 'A';
        cnt[leftIdx]--;
        left++;
        primeCnt = *std::max_element(cnt.begin(), cnt.end());
      }
      ans = max(ans, right - left + 1);
    }
    return ans;
  }
};
Labels:

[LeetCode] 417 Pacific Atlantic Water Flow

原本以為跟經典的滑雪一樣, 可以dfs/dp互通

結果這題的「小於等於」會破壞dp的方向性

所以只能改從終點往回走, 只能視為單純的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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
private:
  static constexpr int SIZE = 201;
  int N, M;
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {1, 0, -1, 0};

  void bfs(std::queue<pair<int, int>>& Q, 
           bool (&vis)[SIZE][SIZE],
           vector<vector<int>>& heights) {
    while(!Q.empty()) {
      int x = Q.front().first;
      int y = Q.front().second;
      Q.pop();
      
      vis[x][y] = true;
      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)
          if (!vis[dx][dy] && heights[x][y] <= heights[dx][dy])
            Q.push(std::make_pair(dx, dy));
      }
    }
  }

public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    N = heights.size();
    M = heights[0].size();
    
    bool visP[SIZE][SIZE] = {0};
    bool visA[SIZE][SIZE] = {0};
    std::queue<pair<int, int>> paQ;
    std::queue<pair<int, int>> atQ;

    for(int i = 0; i < N; i++) {
      paQ.push(std::make_pair(i, 0));
      atQ.push(std::make_pair(i, M - 1));
    }

    for(int i = 0; i < M; i++) {
      paQ.push(std::make_pair(0, i));
      atQ.push(std::make_pair(N - 1, i));
    }

    bfs(paQ, visP, heights);
    bfs(atQ, visA, heights);

    vector<vector<int>> ans;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++)
        if (visP[i][j] && visA[i][j])
          ans.push_back({i, j});
    return ans;
  }
};
Labels:

2026/04/27

[LeetCode] 33 Search in Rotated Sorted Array

世界最難二分搜XD

為什麼又變成小於等於了

使用「小於」跟「小於等於」的時機差別是甚麼?

回傳mid跟回傳low/high的時機差別又是甚麼?

 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 {
public:
  int search(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if(nums[mid] == target)
        return mid;
      
      if (nums[mid] >= nums[low]) 
        if (nums[low] <= target && target <= nums[mid]) 
          high = mid - 1;
        else
          low = mid + 1;
      else 
        if (nums[mid] <= target && target <= nums[high]) 
          low = mid + 1;
        else
          high = mid - 1;
    }
    return -1;
  }
};
Labels:

2026/04/26

[LeetCode]153 Find Minimum in Rotated Sorted Array

知道可以二分

但細節還是沒搞懂

實際會收斂在哪?

每個值是否unique會有甚麼影響?

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

[LeetCode] 152 Maximum Product Subarray 

 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 Solution {
  int max3(int x, int y, int z) {
    return max(max(x, y), z);
  }

  int min3(int x, int y, int z) {
    return min(min(x, y), z);
  }
public:
  int maxProduct(vector<int>& nums) {
    constexpr int SIZE = 20001;
    int maxP[SIZE];
    int minP[SIZE];

    int ans = nums[0];
    maxP[0] = nums[0];
    minP[0] = nums[0];
    for (int i = 1; i < nums.size(); i++) {
      maxP[i] = max3(nums[i], nums[i] * maxP[i - 1], nums[i] * minP[i - 1]);
      minP[i] = min3(nums[i], nums[i] * maxP[i - 1], nums[i] * minP[i - 1]);
      ans = max(ans, maxP[i]);
    }
    return ans;
  }
};
Labels:

[LeetCode] 49 Group Anagrams 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) { 
    // Use sorted string as key
    std::unordered_map<string, vector<string>> anagramMap;
    for (string s : strs) {
      string tmp = s;
      std::sort(tmp.begin(), tmp.end());
      anagramMap[tmp].push_back(s);
    }

    vector<vector<string>> ans;
    for (auto it : anagramMap)
      ans.push_back(it.second);
    return ans;
  }
};
Labels:

[LeetCode] 11 Container With Most Water

Two Pointer

容量大小是由小的那邊決定

每次收縮小的那邊

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  int maxArea(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int ans = 0;

    while (left < right) {
      int cur = (right - left) * min(height[left], height[right]);
      ans = max(ans, cur);
      if (height[left] < height[right])
        left++;
      else
        right--;
    }
    return ans;
  }
};
Labels:

2026/04/25

[LeetCode] 48 Rotate Image

正面實作轉90度極度難寫XD

改用轉置+反轉row

 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 {
public:
  void rotate(vector<vector<int>>& matrix) {
    int N = matrix.size();

    // step 1 : transpose
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        int tmp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = tmp;
      }
    }

    // step 2 : reverse each row
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N / 2; j++) {
        int tmp = matrix[i][j];
        matrix[i][j] = matrix[i][N - j - 1];
        matrix[i][N - j - 1] = tmp;
      }
    }
  }
};
Labels:

2026/04/24

[LeetCode] 73 Set Matrix Zeroes

 要求額外空間要是常數

用row0/col0 來存對應的row/col要不要清零

再用兩個變數來存row0/col0要不要清零

 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
class Solution {
public:
  void setZeroes(vector<vector<int>>& matrix) {
    int N = matrix.size();
    int M = matrix[0].size();
    bool isFirstColZero = false;
    bool isFirstRowZero = false;

    for (int i = 0; i < N; i++)
      if (matrix[i][0] == 0)
        isFirstColZero = true;

    for (int i = 0; i < M; i++)
      if (matrix[0][i] == 0)
        isFirstRowZero = true;
    
    for (int i = 1; i < N; i++) 
      for (int j = 1; j < M; j++)
        if (matrix[i][j] == 0) {
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }

    for (int i = 1; i < N; i++) 
      for (int j = 1; j < M; j++)
        if (matrix[i][0] == 0 || matrix[0][j] == 0)
          matrix[i][j] = 0;
    
    if (isFirstColZero)
      for (int i = 0; i < N; i++)
        matrix[i][0] = 0;
    
    if (isFirstRowZero)
      for (int i = 0; i < M; i++)
        matrix[0][i] = 0;
  }
};
Labels:

[LeetCode] 76 Minimum Window Substring

Two Pointer

右邊一直走

若達成substring window條件, left再開始走, 直到不構成window

特別情況是, 字元過多的時候, 要允許window內出現次數出現負數

 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
class Solution {
public:
  string minWindow(string s, string t) {
    std::unordered_map<char, int> chrMap;
    for (char c : t)
      chrMap[c]++;
    
    int ansLeft;
    int ansLen = INT_MAX;
    int cnt = 0;
    int left = 0;
    int right = 0;
    for (; right < s.size(); right++) {
      if (chrMap.count(s[right])) {
        if (chrMap[s[right]] > 0)
          cnt++;
        chrMap[s[right]]--;
      }

      while (cnt == t.size()) {
        if (right - left + 1 < ansLen) {
          ansLeft = left;
          ansLen = right - left + 1;
        }
        if (chrMap.count(s[left])) {
          chrMap[s[left]]++;
          if (chrMap[s[left]] > 0)
            cnt--;
        }
        left++;
      }
    }
    if (ansLen == INT_MAX)
      return "";
    return s.substr(ansLeft, ansLen);
  }
};
Labels:

2026/04/23

[LeetCode] 647 Palindromic Substrings 

 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 {
private:
  static constexpr int SIZE = 1005;
  bool vis[SIZE][SIZE] = {0};
  bool cache[SIZE][SIZE] = {0};
  int N;
  string str;
  bool dp(int i, int j) {
    if (vis[i][j])
      return cache[i][j];
    vis[i][j] = true;
    if (i >= j) {
      cache[i][j] = true;
      return cache[i][j];
    }
    if (this->str[i] == this->str[j]) {
      cache[i][j] = dp(i + 1, j - 1);
      return cache[i][j];
    }
    cache[i][j] = false;
    return cache[i][j];
  }

public:
  int countSubstrings(string s) {
    this->N = s.size();
    this->str = s;
    
    int ans = 0;
    for (int i = 0; i < N; i++)
      for (int j = i; j < N; j++)
        if (dp(i, j))
          ans++;
    return ans;
  }
};
Labels:

2026/04/21

[LeetCode] 5 Longest Palindromic Substring 

 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
class Solution {
private:
  string expandOdd(int idx, string& s) {
    int i = 1;
    for (; i < s.size(); i++) {
      if (idx - i < 0)
        break;
      if (idx + i >= s.size())
        break;
      if (s[idx - i] != s[idx + i])
        break;
    }
    i--;
    int left = idx - i;
    int len = i * 2 + 1;
    return s.substr(left, len);
  }

  string expandEven(int idx, string& s) {
    int i = 1;
    for (; i < s.size(); i++) {
      if (idx - i + 1 < 0)
        break;
      if (idx + i >= s.size())
        break;
      if (s[idx - i + 1] != s[idx + i])
        break;
    }
    i--;
    int left = idx - i + 1;
    int len = i * 2;
    return s.substr(left, len);
  }

public:
  string longestPalindrome(string s) {
    string ansStr = "";
    for (int i = 0; i < s.size(); i++) {
      string oddStr = expandOdd(i, s);
      if (oddStr.size() > ansStr.size()) 
        ansStr = oddStr;

      string evenStr = expandEven(i, s);
      if (evenStr.size() > ansStr.size())
        ansStr = evenStr;
    }
    return ansStr;
  }
};
Labels:

2026/04/19

[LeetCode] 211 Design Add and Search Words Data Structure 

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Trie {
public:
  static constexpr int CHILDSIZE = 26;
  bool isWord;
  string word;
  Trie* child[CHILDSIZE];

  Trie() {
    isWord = false;
    for (int i = 0; i < CHILDSIZE; i++)
      this->child[i] = nullptr;
  }

  void insert(string s) {
    Trie *node = this;
    for (auto &chr : s) {
        int idx = chr - 'a';
        if (!node->child[idx])
          node->child[idx] = new Trie();
        node = node->child[idx];
    }
    node->isWord = true;
    node->word = s;
  }

  bool search(string word) {
    if (word.empty())
      return this->isWord;
    
    if (word[0] == '.') {
      for (int i = 0; i < CHILDSIZE; i++) 
        if (this->child[i])
          if (this->child[i]->search(word.substr(1)))
            return true;
      return false;
    }

    int idx = word[0] - 'a';
    if (!this->child[idx])
      return false;
    return this->child[idx]->search(word.substr(1));
  }
};

class WordDictionary {
private:
  Trie* trie;

public:
    WordDictionary() {
      this->trie = new Trie();
    }
    
    void addWord(string word) {
      this->trie->insert(word);
    }
    
    bool search(string word) {
      return this->trie->search(word);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */
Labels:

2026/04/18

[LeetCode] 212 Word Search II

LeetCode 79 的推廣版
從尋找一個字串升級到尋找多個字串
建一個Trie
只沿著prefix做dfs

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Trie {
public:
  static constexpr int NODESIZE = 26;
  bool isWord;
  string word;
  Trie* child[NODESIZE];

  Trie() {
    isWord = false;
    for (int i = 0; i < NODESIZE; i++)
      this->child[i] = nullptr;
  }

  void insert(string s) {
    Trie *node = this;
    for (auto &chr : s) {
        int idx = chr - 'a';
        if (!node->child[idx])
          node->child[idx] = new Trie();
        node = node->child[idx];
    }
    node->isWord = true;
    node->word = s;
  }
};

class Solution {
private:
  int dx[4] = {1, -1, 0, 0};
  int dy[4] = {0, 0, 1, -1};
  static constexpr int SIZE = 20;
  bool vis[SIZE][SIZE] = {0};
  int M, N;
  vector<string> ans;

  void dfs(int x, int y, Trie* trie, 
           vector<vector<char>>& board) {
    if (trie->isWord) {
      ans.push_back(trie->word);
      trie->isWord = false;
    }

    for (int i = 0; i < 4; i++) {
      if (x + dx[i] >= 0 && x + dx[i] < M &&
          y + dy[i] >= 0 && y + dy[i] < N && 
          !vis[x + dx[i]][y + dy[i]]) {
        vis[x + dx[i]][y + dy[i]] = true;
        int idx = board[x + dx[i]][y + dy[i]] - 'a';
        if (trie->child[idx]) 
          dfs(x + dx[i], y + dy[i], trie->child[idx], board);
        vis[x + dx[i]][y + dy[i]] = false;
      }
    }
  }

public:
  vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    Trie* root = new Trie();
    for (string word : words)
      root->insert(word);

    M = board.size();
    N = board[0].size();
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) { 
        vis[i][j] = true;
        int idx = board[i][j] - 'a';
        if (root->child[idx]) 
          dfs(i, j, root->child[idx], board);
        vis[i][j] = false;
      }
    }
    return ans;
  }
};
Labels:
訂閱： 文章 (Atom)