1047. Remove All Adjacent Duplicates In String

解題思路

看題目敘述就知道是用 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;
    }
};

1372. Longest ZigZag Path in a Binary Tree

解題思路

遍歷整棵樹，然後不斷更新當下的 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;
    }
};

2645. Minimum Additions to Make Valid String

解題思路

我是轉換成類似 finite state 的概念。假設當下預計要看到 a，但是字串當下指到的不是 a，就代表要多加一個字元；如果指到的是 a，則代表可以指到字串下一個位置繼續比對。

然後整個字串看完，還是要把檢查當下的 state。只有 stateA 是走完了，stateB 跟 stateC 要額外加上字元。

程式碼

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;
    }
};

743. Network Delay Time

解題心得

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;
    }
};