981. Time Based Key-Value Store

解題思路

這題必須用到 map，然後因為還有 timestamp，要在時限內的話要用到 binary search。

從這題中學到：

1. unordered_map 可以用來加速、提升效率

2. upper_bound 可以用來找到第一個大於給定數值的

3. auto iterator 可以用 -- 移到上一個

程式碼

class TimeMap {
public:
    unordered_map<string, map<int, string>> mp;

    TimeMap() {
    }
    
    void set(string key, string value, int timestamp) {
        mp[key][timestamp] = value;
    }
    
    string get(string key, int timestamp) {
        if(!mp.count(key)) return "";
        auto it = mp[key].upper_bound(timestamp);
        if(it == mp[key].begin()) return "";
        return (--it)->second;
    }
};

236. Lowest Common Ancestor of a Binary Tree

解題思路

會有兩種情況： p, q 屬於同一個 subtree 或不是。如果不是，那麼回傳的就會是他們的再往上的 root，不然就是 p 跟 q 自己。

判斷方法就是一直往下看左右子樹有沒有 p 跟 q，如果有的話就回傳那個 node，如果沒有就是回傳 root。

程式碼

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left != nullptr && right != nullptr)
            return root;
        else if(left != nullptr)
            return left;
        else
            return right;
    }
};

56. Merge Intervals

解題思路

先把 interval 給 sort 過一次，確保數字至少是遞增上去的。

接下來 traverse 每一個 element，因為新 element 只可能跟上一個 overlap，或乾脆就在上一個右邊，因此依照情況決定是要 merge 還是 push_back 就好。

比 57. Insert Interval 簡單很多。

程式碼

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;

        ans.push_back(intervals[0]);
        for(int i=1; i<intervals.size(); i++)
        {
            if(ans.back()[1] >= intervals[i][0]) // merge
            {
                ans.back()[0] = min(ans.back()[0], intervals[i][0]);
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);
            }
            else
                ans.push_back(intervals[i]);
        }
        return ans;
    }
};

46. Permutations

解題思路

排列組合經典題。

想像每一次都從現有的 nums 拿一個走，接著繼續再從剩的在選一個，重複這個動作直到所有的都被選過為止。

程式碼

class Solution {
public:
    void helper(vector<int>& nums, vector<vector<int>>& ans, vector<int> comb, vector<bool> isUsed)
    {
        if(comb.size() == nums.size())
        {
            ans.push_back(comb);
            return;
        }
        for(int i=0; i<nums.size(); i++)
        {
            if(isUsed[i]) continue;
            comb.push_back(nums[i]);
            isUsed[i] = true;
            helper(nums, ans, comb, isUsed);
            comb.pop_back();
            isUsed[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> comb;
        vector<bool> isUsed(nums.size(), false);
        helper(nums, ans, comb, isUsed);
        return ans;
    }
};

39. Combination Sum

解題思路

也是經典的題型。

如果要確保 combination 是唯一的，用 start 標記起始點可以避免重複拿取 element，以至於產生相同的組合。

程式碼

class Solution {
public:
    void helper(vector<int>& candidates, vector<vector<int>>& ans, vector<int> result, int target, int start)
    {
        if(target == 0)
            ans.push_back(result);
        if(target < 0)
            return ;

        for(int i=start; i<candidates.size(); i++)
        {
            vector<int> result_new = result;
            result_new.push_back(candidates[i]);
            helper(candidates, ans, result_new, target - candidates[i], i);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> result;
        helper(candidates, ans, result, target, 0);
        return ans;
    }
};

33. Search in Rotated Sorted Array

解題思路

分三個部分：

1. 藉由 binary search 的方式找到 pivot。

2. 由 pivot 可推知 target 在其左邊還右邊，更新 left 與 right

3. 拿更新後的 left 與 right 再做一次 binary search 找 target。

pivot 是指 sorted array 經過旋轉後產生的不連續遞增斷點的右側，ex: [4,5,6,7,0,1,2] 中的 0。

一直卡在 pivot 求法，最後求助於 chatGPT 生出答案，改天再寫一次。

程式碼

class Solution {
public:
    int findPivot(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int pivot = findPivot(nums);
        int left, right;
        if (target >= nums[pivot] && target <= nums[nums.size() - 1]) {
            left = pivot;
            right = nums.size() - 1;
        } else {
            left = 0;
            right = pivot - 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;
    }
};

994. Rotting Oranges

解題思路

看出來是 BFS 後，就很好解了。

程式碼

struct P {
    int x;
    int y;
};
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<P> q1, q2;
        int minute = 0, dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[i].size(); j++)
            {
                if(grid[i][j] == 2)
                    q1.push({i, j});
            }
        }
        while(true)
        {
            while(!q1.empty())
            {
                for(int i=0; i<4; i++)
                {
                    int newX = q1.front().x+dx[i], newY = q1.front().y+dy[i];
                    if(0 <= newX && newX < grid.size() && 0 <= newY && newY < grid[0].size() && grid[newX][newY] == 1)
                    {
                        q2.push({newX, newY});            
                        grid[newX][newY] = 2;
                    }
                }
                q1.pop();
            }
            minute += 1;
            if(q2.empty()) break;
            swap(q1, q2);
        }
        for(int i=0; i<grid.size(); i++)
            for(int j=0; j<grid[i].size(); j++)
                if(grid[i][j] == 1)
                    return -1;

        return minute - 1;
    }
};

238. Product of Array Except Self

解題思路

分別算出從前與從後算到該 index 的乘積，最後再相乘到 output 。

程式碼

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int prefix[100001] = {0}, suffix[100001] = {0};
        int pre = 1;
        for(int i=0; i<nums.size(); i++)
        {
            prefix[i] = pre * nums[i];
            pre = prefix[i];
        }
        int suf = 1;
        for(int i=nums.size() - 1; i>=0; i--)
        {
            suffix[i] = suf * nums[i];
            suf = suffix[i];
        }
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(i == 0)
                ans.push_back(suffix[i+1]);
            else if(i == nums.size()-1)
                ans.push_back(prefix[i-1]);
            else
                ans.push_back(prefix[i-1] * suffix[i+1]);
        }
        return ans;
    }
};

208. Implement Trie (Prefix Tree)

解題思路

先自定義 node，用 pointer 的方式連接。檢查 node 是否已經是字的結尾，就用 bool 來記錄。

程式碼

class Node{
public:
    bool isEnd;
    Node* child[26];
    Node()
    {
        isEnd = false;
        for(int i=0; i<26; i++)
            child[i] = nullptr;
    }
};
class Trie {
public:
    Node* root = new Node();

    Trie() {
    }
    
    void insert(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                current->child[word[i] - 'a'] = new Node();
            current = current->child[word[i] - 'a'];
        }
        current->isEnd = true;
    }
    
    bool search(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                return false;
            current = current->child[word[i] - 'a'];
        }
        return current->isEnd == true;
    }
    
    bool startsWith(string prefix) {
        Node* current = root;
        for(int i=0; i<prefix.size(); i++)
        {
            if(current->child[prefix[i] - 'a'] == nullptr)
                return false;
            current = current->child[prefix[i] - 'a'];
        }
        return true;
    }
};

207. Course Schedule

解題思路

感覺只是把 neetcode 的解法寫成 C++ 版本而已，改天要再練習一次。

程式碼

class Solution {
public:
    map<int, set<int>> preMap;
    set<int> checkCycle;
    bool dfs(int currentCourse)
    {
        if(checkCycle.find(currentCourse) != checkCycle.end()) // alreadly visited
            return false;
        if(preMap[currentCourse].empty()) // no prerequisites or are all valid
            return true;
        
        checkCycle.insert(currentCourse);
        for(auto c : preMap[currentCourse])
        {
            if(!dfs(c))
                return false;
        }
        checkCycle.erase(currentCourse);
        preMap[currentCourse].clear();
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for(int i=0; i<prerequisites.size(); i++)
            preMap[prerequisites[i][0]].insert(prerequisites[i][1]);
        
        for(int i=0; i<numCourses; i++)
        {
            if(!dfs(i))
                return false;
        }
        return true;
    }
};

150. Evaluate Reverse Polish Notation

解題心得

很經典的 stack 題目

程式碼

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0; i<tokens.size(); i++)
        {
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int second = st.top(); st.pop();
                int first = st.top(); st.pop();
                if(tokens[i] == "+") st.push(first + second);
                else if(tokens[i] == "-") st.push(first - second);
                else if(tokens[i] == "*") st.push(first * second);
                else if(tokens[i] == "/") st.push(first / second);
            }
            else
            {
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
    }
};