解題思路
看題目敘述就知道是用 stack 的概念。
原本是先用 stack 存字元，最後再從 stack 裡面把剩下的組合還原成答案。但這樣會 TLE。
改成不用 stack，直接在字串上操作。
程式碼
class Solution {
public:
string removeDuplicates(string s) {
string ans = "";
for(int i=0; i<s.size(); i++)
{
if(ans.back() == s[i])
ans.pop_back();
else
ans += s[i];
}
return ans;
}
};
解題思路
遍歷整棵樹，然後不斷更新當下的 zigzag 長度與整棵樹最常 zigzag 長度。
程式碼
原本的程式
class Solution {
public:
void helper(TreeNode* root, bool lastIsLeft, int currentL, int& maxL)
{
if(root == nullptr)
return;
maxL = max(maxL, currentL);
if(lastIsLeft)
{
helper(root->left, true, 1, maxL);
helper(root->right, false, currentL + 1, maxL);
}
else
{
helper(root->left, true, currentL + 1, maxL);
helper(root->right, false, 1, maxL);
}
}
int longestZigZag(TreeNode* root) {
int maxL = 0;
helper(root->left, true, 1, maxL);
helper(root->right, false, 1, maxL);
return maxL;
}
};
chatGPT 改進後的程式
class Solution {
public:
void helper(TreeNode* root, int leftLen, int rightLen, int& maxLen) {
if (root == nullptr) {
return;
}
maxLen = max(maxLen, max(leftLen, rightLen));
helper(root->left, rightLen + 1, 0, maxLen);
helper(root->right, 0, leftLen + 1, maxLen);
}
int longestZigZag(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int maxLen = 0;
helper(root, 0, 0, maxLen);
return maxLen;
}
};
class Solution {
public:
int addMinimum(string word) {
bool stateA = true, stateB = false, stateC = false;
int count = 0, i=0;
while(i < word.size())
{
if(stateA)
{
if(word[i] != 'a') count++;
else i++;
stateA = false;
stateB = true;
}
else if(stateB)
{
if(word[i] != 'b') count++;
else i++;
stateB = false;
stateC = true;
}
else if(stateC)
{
if(word[i] != 'c') count++;
else i++;
stateC = false;
stateA = true;
}
}
if(stateB) count += 2;
else if(stateC) count += 1;
return count;
}
};解題心得
Dijkstra 演算法實作。
1. emplace_back 會把該筆資料放到最末端；emplace 是放入任意位置。
2. 用 minHeap，是因為在演算法中，要取出當下 cost 最小的路徑來做更新。
3. 用 max()，是因為找出傳到所有 node 最少需要的時間，又最遠 node 要得最久。
4. 如果無法每個 node 都拜訪，則回傳 -1。
程式碼
typedef pair<int, int> edge; // target node, weight;
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<edge>> graph(n+1);
for(int i=0; i<times.size(); i++)
graph[times[i][0]].emplace_back(times[i][1], times[i][2]);
priority_queue<edge, vector<edge>, greater<edge>> minHeap;
vector<bool> isVisited(n+1, false);
minHeap.emplace(0, k);
int ans = 0;
while(!minHeap.empty())
{
int w1, n1;
w1 = minHeap.top().first, n1 = minHeap.top().second;
minHeap.pop();
if(isVisited[n1])
continue;
isVisited[n1] = true;
ans = max(ans, w1);
for(int i=0; i<graph[n1].size(); i++)
{
int w2 = graph[n1][i].second, n2 = graph[n1][i].first;
if(!isVisited[n2])
minHeap.emplace(w1 + w2, n2);
}
}
for(int i=1; i<=n; i++)
{
if(!isVisited[i])
return -1;
}
return ans;
}
};
解題思路
用 union find 來解這題。
如果 edge 的兩個 node 已屬於同個 union，即可知該 edge 為多餘的。
程式碼
class Solution {
public:
int *dsu, *rank;
int size;
int find_set(int v)
{
if(dsu[v] == v) return v;
return dsu[v] = find_set(dsu[v]);
}
void make_union(int u, int v)
{
u = find_set(u), v = find_set(v);
if(u != v)
{
if(rank[u] > rank[v])
{
dsu[v] = u;
rank[u] += rank[v];
}
else
{
dsu[u] = v;
rank[v] += rank[u];
}
}
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
this->size = edges.size() + 1;
this->dsu = new int[size];
this->rank = new int[size];
for(int i=0; i<size; i++)
{
dsu[i] = i;
rank[i] = 1;
}
for(int i=0; i<edges.size(); i++)
{
if(find_set(edges[i][0]) == find_set(edges[i][1]))
return edges[i];
make_union(edges[i][0], edges[i][1]);
}
return edges[0];
}
};
解題心得
從邊緣的 O 往內走訪，最後再回頭重新檢視誰要被翻過去。
程式碼
class Solution {
public:
void helper(vector<vector<char>>& board, vector<vector<bool>>& notFlip, int x, int y)
{
if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
return;
if(board[x][y] == 'X' || notFlip[x][y])
return;
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
notFlip[x][y] = true;
for(int i=0; i<4; i++)
{
helper(board, notFlip, x+dx[i], y+dy[i]);
}
}
void solve(vector<vector<char>>& board) {
vector<vector<bool>> notFlip(board.size(), vector<bool>(board[0].size(), false));
for(int i=0; i<board.size(); i++)
{
for(int j=0; j<board[0].size(); j++)
{
if(board[i][j] == 'O' && (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1))
{
helper(board, notFlip, i, j);
}
}
}
for(int i=0; i<board.size(); i++)
{
for(int j=0; j<board[0].size(); j++)
{
if(board[i][j] == 'O' && !notFlip[i][j])
board[i][j] = 'X';
}
}
}
};
解題思路
因為有重複的數字，所以可能會有重複的組合出現。
要避免這種情況，那麼就要知道，這個求解的過程就是每次都在選或不選當下的數字。如果不選，就代表該數字未來也不會選，所以要把 i 往後推。
程式碼
class Solution {
public:
void helper(vector<int>& nums, vector<vector<int>>& ans, vector<int> current, int start)
{
ans.push_back(current);
for(int i=start; i<nums.size(); i++)
{
current.push_back(nums[i]);
helper(nums, ans, current, i+1);
current.pop_back();
int next = i+1;
while(next <nums.size() &&nums[next] == nums[i])
next++;
i = next-1;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> current;
sort(nums.begin(), nums.end());
helper(nums, ans, current, 0);
return ans;
}
};
解題思路
覺得這題跟 703. Kth Largest Element in a Stream 非常像，甚至還比這題簡單，但兩個題目的難度標示卻不是這樣，不懂。
程式碼
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for(int i=0; i<nums.size(); i++)
{
pq.push(nums[i]);
if(pq.size() > k)
pq.pop();
}
return pq.top();
}
};
解題思路
每次要找出最大與次大，最方便的方法是用 max heap。
程式碼
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq;
for(int i=0; i<stones.size(); i++)
pq.push(stones[i]);
while(pq.size() != 1)
{
int first = pq.top(); pq.pop();
int second = pq.top(); pq.pop();
pq.push(first - second);
}
return pq.top();
}
};
解題思路
minHeap 以 priority queue 的實作練習。
程式碼
class KthLargest {
public:
priority_queue<int, vector<int>, greater<int>> pq;
int size;
KthLargest(int k, vector<int>& nums) {
size = k;
for(int i=0; i<nums.size(); i++)
{
pq.push(nums[i]);
if(pq.size() > size)
pq.pop();
}
}
int add(int val) {
pq.push(val);
if(pq.size() > size)
pq.pop();
return pq.top();
}
};
vscode 底下那條藍色的 bar 偏右側有一個地方，點擊後可選擇 interpreter。隨便選了一個後，莫名的用 vscode terminal 做某些操作就會出現問題，把 python 與 vscode 刪掉重裝仍然沒有解決。
後來是把 default 的 interpreter 改到新安裝的 python 的路徑就正常了，但是執行指令要打 py 而不 python，例如：py -m venv myenv。這個部分感覺跟這個有關，先存著以後有需要再來看。