阿風的學業紀錄: 1月 2023

2023年1月31日星期二

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

2023年1月30日星期一

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

2023年1月29日星期日

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

2023年1月28日星期六

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

2023年1月27日星期五

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

2023年1月26日星期四

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

2023年1月25日星期三

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

2023年1月24日星期二

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

133. Clone Graph

解題思路

用 map 紀錄走訪過該 node 與否，並用 DFS 看過整張圖。

程式碼

class Solution {
public:
    map<Node*, Node*> oldToNew;
    Node* dfs(Node* node)
    {
        if(oldToNew.count(node))
            return oldToNew[node];

        Node* clone = new Node(node->val);
        oldToNew[node] = clone;
        for(int i=0; i<node->neighbors.size(); i++)
        {
            clone->neighbors.push_back(dfs(node->neighbors[i]));
        }
        return clone;
    }
    Node* cloneGraph(Node* node) {
        if(node == nullptr)
            return nullptr;

        return dfs(node);
    }
};

2023年1月23日星期一

200. Number of Islands

解題思路

每當找到一個沒看過的島，就四方探索整個範圍並且把該位置抹掉。

程式碼

class Solution {
public:
    void bfs(vector<vector<char>>& grid, int x, int y)
    {
        int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, 1, -1, 0};
        if(0 <= x && x < grid.size() && 0 <= y && y < grid[0].size() && grid[x][y] == '1')
        {
            grid[x][y] = '0';
            for(int i=0; i<4; i++)
                bfs(grid, x+dx[i], y+dy[i]);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;

        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[0].size(); j++)
            {
                if(grid[i][j] == '1')
                {
                    num++;
                    bfs(grid, i, j);
                }
            }
        }
        return num;
    }
};

322. Coin Change

解題思路

零錢問題之找最少零錢數。

程式碼

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int index[10001] = {0};
        for(int i=1; i<10001; i++)
            index[i] = amount + 1;
        for(int i=1; i<10001; i++)
        {
            for(int j=0; j<coins.size(); j++)
            {
                if((i - coins[j]) >= 0)
                {
                    index[i] = min(index[i], 1 + index[i - coins[j]]);
                }
            }
        }
        if(index[amount] == amount + 1) return -1;
        return index[amount];
    }
};

2023年1月22日星期日

155. Min Stack

解題思路

要 getMin，就要想方法去紀錄最小值。沒辦法只用一個變數記錄當下最小值，因為如果 pop 掉的剛好是最小值，那要如何再回溯找到上一個最小值？

所以會需要另一個 stack，用來記錄當下以這個 element 為 top 時，最小值是誰？然後每當有 push 或 pop ，要同步更新。

程式碼

class MinStack {
public:
    stack<int> st;
    stack<int> minSt; // record the min value at that point

    MinStack() {
        
    }
    
    void push(int val) {
        st.push(val);
        if(minSt.empty())
            minSt.push(val);
        else if(val < minSt.top())
            minSt.push(val);
        else
            minSt.push(minSt.top());
    }
    
    void pop() {
        st.pop();
        minSt.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.top();
    }
};

98. Validate Binary Search Tree

解題心得

如果只比 root 值還有 root 左子樹右子樹三個節點會錯。

改用傳當前區間去做比對。

程式碼

class Solution {
public:
    bool isValid(TreeNode* root, long min, long max)
    {
        if(root == nullptr)
            return true;
        if(!(min < root->val && root->val < max))
            return false;
        return isValid(root->left, min, root->val) && isValid(root->right, root->val, max);
    }
    bool isValidBST(TreeNode* root) {
        return isValid(root, LLONG_MIN, LLONG_MAX);
    }
};

2023年1月20日星期五

102. Binary Tree Level Order Traversal

解題思路

用兩個 queue，一個是現在的 level 的所有 node，一個是下個 level 的 node。

當當前 level 的 node 的 queue 清空，就換成下個 level。一直重複直到空了為止。

程式碼

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr)
            return ans;

        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        int num = 1;
        q1.push(root);
        
        vector<int> v;
        while(!q1.empty())
        {
            v.push_back(q1.front()->val);
            if(q1.front()->left != nullptr)
                q2.push(q1.front()->left);
            if(q1.front()->right != nullptr)
                q2.push(q1.front()->right);
            cout << v[v.size() - 1]  << " "<< v.size() << endl;
            q1.pop();
            if(q1.empty())
            {
                swap(q1, q2);
                ans.push_back(v);
                v.clear();
            }
        }
        return ans;
    }
};

15. 3Sum

解題思路

有兩個地方會造成 duplicate:

一、第一層 for loop 的數值相同

譬如 [-4, -1, -1, 0, 1, 2] ，會先看到 index = 1 的那個 -1 ，找出解 [-1, 0, 1]。接著來到 index = 2 的 -1，這時又找出同樣的 [-1, 0, 1] 這組解。

要避免這種情況，必須檢查是不是跟前面的數值相同。

二、找 second, third 時數值相同

譬如 [-2, 0, 0, 2, 2]，會找到同樣的兩組 [-2, 0, 2]。

要避免這種情況，在移動 left, right 時也要檢查。

程式碼

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for(int i=0; i<nums.size() - 2; i++)
        {
            if(i != 0 && nums[i] == nums[i-1])
                continue;

            int left = i+1, right = nums.size() - 1;
            while(left < right)
            {
                if(left > i+1 && right < nums.size() - 1 && nums[left] == nums[left - 1] && nums[right] == nums[right + 1])
                {
                    left += 1;
                    right -= 1;
                    continue;
                }
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0)
                {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    left += 1;
                    right -= 1;
                }
                else if(sum < 0)
                    left += 1;
                else
                    right -= 1;
            }
        }
        return ans;
    }
};

2023年1月19日星期四

3. Longest Substring Without Repeating Characters

解題思路

two pointer 的概念來解。

不知為何卡好久，要找時間再寫一次。

程式碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int index[128];
        int left = 0, right = 0, maxLen = 0;

        for(int i=0; i<128; i++)
            index[i] = -1;
        for(int i=0; i<s.size(); i++)
        {
            right = i;
            
            left = max(left, index[s[i]] + 1);
            maxLen = max(right - left + 1, maxLen);
            index[s[i]] = right;
        }
        return maxLen;
    }
};

2023年1月18日星期三

973. K Closest Points to Origin

解題思路

暴力解。先 sort 一輪，拿走前 k 個就好。

程式碼

bool cmp(vector<int> p1, vector<int> p2)
{
    return sqrt(p1[0] * p1[0] + p1[1] * p1[1]) < sqrt(p2[0] * p2[0] + p2[1] * p2[1]);
}
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        sort(points.begin(), points.end(), cmp);
        vector<vector<int>> ans; 
        for(int i=0; i<k; i++)
            ans.push_back(points[i]);
        return ans;
    }
};

542. 01 Matrix

解題思路

要先從 mat[i][j] == 0 的那些位置開始探索周圍未被探索過的，所以用 queue 一個個找。

程式碼

struct Point
{
    int x, y;
};
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> ans(mat.size(), vector<int> (mat[0].size(), -1));
        queue<Point> q;
        for(int i=0; i<mat.size(); i++)
        {
            for(int j=0; j<mat[0].size(); j++)
            {
                if(mat[i][j] == 0)
                {    
                    ans[i][j] = 0;
                    Point p; 
                    p.x = i;
                    p.y = j;
                    q.push(p);
                }
            }
        }
        int offset[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while(!q.empty())
        {
            for(int i=0; i<4; i++)
            {
                int newX = q.front().x + offset[i][0];
                int newY = q.front().y + offset[i][1];
                if(newX >= 0 && newX < mat.size() && newY >= 0 && newY < mat[0].size())
                {
                    if(ans[newX][newY] == -1)
                    {
                        ans[newX][newY] = ans[q.front().x][q.front().y] + 1;
                        Point p; 
                        p.x = newX;
                        p.y = newY;
                        q.push(p);
                    }
                }
            }
            q.pop();
        }
        return ans;
    }
};

2023年1月17日星期二

57. Insert Interval

解題思路

在 traverse 給定的 intervals 時，要思考的是：newInterval 是否與之重疊、或會插在哪裡？

而可以想像的是，當有兩個 intervals 時，關於重疊只會有三種情形：newInterval 要放 interval 左邊、放右邊，或者兩個重疊要 merge。

情況一：放左邊

這種情況代表要插入整個 intervals 的最前面。

情況二：放右邊

這種情況代表沒有重疊到，只是放入 intervals 中。

情況三：merge

如果既不屬於左邊也不屬於右邊，那就要把當前 interval 跟 newInterval merge起來。merge 取兩端點最小與最大即可。

程式碼

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        
        for(int i=0; i<intervals.size(); i++)
        {
            if(newInterval[1] < intervals[i][0])
            {
                ans.push_back(newInterval);
                newInterval = intervals[i];
            }
            else if(newInterval[0] > intervals[i][1])
            {
                ans.push_back(intervals[i]);
            }
            else
            {
                newInterval[0] = min(intervals[i][0], newInterval[0]);
                newInterval[1] = max(intervals[i][1], newInterval[1]);
            }
        }
        ans.push_back(newInterval);
        return ans;
    }
};

53. Maximum Subarray

解題思路

當探訪下一個 array 中的 element 時，要選擇把最大 subarray 的範圍包含進該 element，還是說以該 element 為起點重新計算？

決定完後，再把 element 值更新為當前最大 subarray 的總和值。

程式碼

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        for(int i=1; i<nums.size(); i++)
        {
            nums[i] = max(nums[i], nums[i] + nums[i-1]);
            ans = max(ans, nums[i]);
        }
        return ans;
    }
};

2023年1月16日星期一

844. Backspace String Compare

解題思路

看到#要忽略前一個字元，這點很直覺想到 stack 的操作。

程式碼

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> st1;
        stack<char> st2;

        for(int i=0; i<s.size(); i++)
        {
            if(s[i] == '#')
            {
                if(!st1.empty())
                    st1.pop();
            }
            else
                st1.push(s[i]);
        }
        for(int i=0; i<t.size(); i++)
        {
            if(t[i] == '#')
            {
                if(!st2.empty())
                    st2.pop();
            }
            else
                st2.push(t[i]);
        }
        while(!st1.empty() && !st2.empty())
        {
            if(st1.top() != st2.top())
                return false;
            st1.pop();
            st2.pop();
        }
        return st1.empty() && st2.empty();
    }
};

13. Roman to Integer

解題思路

特殊情況：左值 < 右值，要用右 - 左處理。

程式碼

class Solution {
public:
    int romanToInt(string s) {
        map<char, int> mp;
        mp['I'] = 1;
        mp['V'] = 5;
        mp['X'] = 10;
        mp['L'] = 50;
        mp['C'] = 100;
        mp['D'] = 500;
        mp['M'] = 1000;

        int value = 0;
        for(int i=0; i<s.size(); i++)
        {
            if((i != s.size() - 1) && mp[s[i]] < mp[s[i+1]])
            {
                value += mp[s[i+1]] - mp[s[i]];
                i++;
            }
            else
            {
                value += mp[s[i]];   
            }
        }
        return value;
    }
};

2023年1月14日星期六

217. Contains Duplicate

解題思路

很直覺的想到用 map 來記錄。

程式碼

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        map<int, int> mp;

        for(int i=0; i<nums.size(); i++)
        {
            if(mp.count(nums[i]))
                return true;
            mp[nums[i]] = 0;
        }
        return false;
    }
};

104. Maximum Depth of Binary Tree

程式碼

class Solution {
public:
    int getDepth(TreeNode* p)
    {
        if(p == nullptr)
            return 0;
        return max(getDepth(p->left), getDepth(p->right)) + 1;
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};

876. Middle of the Linked List

解題思路

因為 slow pointer 走的速度會是 fast pointer 的兩倍，正好用來找中間 node。

程式碼

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

2023年1月13日星期五

543. Diameter of Binary Tree

解題思路

一開始的想法是看 root->left 跟 root->right 各自的最大深度，然後加起來就是答案，因為等同於從左邊最深走到右邊最深的路徑。

不過後來有測資錯誤。要考量的不只是 root 底下的左子樹與右子樹，而是所有 node 底下的左子樹與右子樹都要檢查，所以要一直往下 recursive 的 max 當前最大與左右子樹的最大。

程式碼

class Solution {
public:
    int getDepth(TreeNode* p)
    {
        if(p == nullptr)
            return 0;
        return max(getDepth(p->left), getDepth(p->right)) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == nullptr)
            return 0;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        int sub = max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right));
        return max(sub, left + right);
    }
};

67. Add Binary

程式碼

class Solution {
public:
    string addBinary(string a, string b) {
        if(a.size() < b.size()) // a must longer than b
            swap(a, b);
        for(int i=0; i<b.size(); i++)
        {
            a[a.size() - 1 - i] += b[b.size() - 1 - i] - '0';
        }
        for(int i=a.size() - 1; i>0; i--)
        {
            if(a[i] >= '2')
            {
                a[i-1]++;
                a[i] -= 2;
            }
        }
        if(a[0] >= '2')
        {
            a[0] -= 2;
            a = "1" + a;
        }
        return a;
    }
};

169. Majority Element

解題思路

題目敘述都直接提到 "The majority element is the element that appears more than ⌊n / 2⌋ times." 了，可知占多數的 element 一定超過一半，那找一半的位子是甚麼數就好。

程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

206. Reverse Linked List

解題思路

紀錄上一個跟下一個是啥，一直重複直到底。最後回傳不是傳 head 是 prev，因為 head 已經是 null 了。

程式碼

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* next;
        while(head != nullptr)
        {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
};

2023年1月12日星期四

409. Longest Palindrome

解題思路

因為字串可能同時有大小寫字母，所以不能只開長度 26 的 array 來計數。不過 ascii code 本身的值介於 0 ~ 127 之間，所以就開 128 長度 array 即可。

另外，構成回文的條件，就是偶數一定可以都用上(左右各半)，奇數多出來的那個數字，最多只能用一次(放在正中間)。

程式碼

class Solution {
public:
    int longestPalindrome(string s) {
        int index[128] = {0};
        for(int i=0; i<s.size(); i++)
            index[s[i]]++;
        
        int length = 0;
        bool hasOdd = false;
        for(int i=0; i<128; i++)
        {
            length += index[i] / 2 * 2;
            if(index[i] % 2)
                hasOdd = true;
        }
        if(hasOdd)
            length += 1;
        return length;
    }
};

70. Climbing Stairs

解題心得

因為 n 的範圍不大，先算好全部，之後直接查。

程式碼

class Solution {
public:
    int climbStairs(int n) {
        int step[46] = {0, 1, 2};
        for(int i=3; i<=45; i++)
        {
            step[i] = step[i-1] + step[i-2];
        }
        return step[n];
    }
};

383. Ransom Note

解題心得

程式碼

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int index[26] = {0};
        for(int i=0; i<magazine.size(); i++)
            index[magazine[i] - 'a']++;
        for(int i=0; i<ransomNote.size(); i++)
        {
            index[ransomNote[i] - 'a']--;
            if(index[ransomNote[i] - 'a'] < 0)
                return false;
        }
        return true;
    }
};

278. First Bad Version

解題思路

覺得這題題目的 input 敘述沒寫好。input 寫會給 n 跟 bad，害我想好久都給 bad 了是要解甚麼。

題目可簡化為有一個長度為 n 的 array，長這樣：[0, 0, 0, ......, 1, 1]。問：第一個 1 在哪個位置？輸入給定 array 的長度，以及提供 isBadVersion(n) 的 API，以使用 API 次數最少的方法求解。

算是 binary search 的變化版？

另外由於 mid 直接 (left + right)/2 會太大，必須換一種寫法。

程式碼

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

2023年1月11日星期三

232. Implement Queue using Stacks

解題思路

用兩個 stack 來模擬，一個用來 push 的時候能塞到最後，一個用來 pop 的時候能拿到最前面的值。

注意每次都要先確保把另一個 stack 的東西搬過來。

程式碼

class MyQueue {
public:
    stack<int> s1; // for push
    stack<int> s2; // for pop

    MyQueue() {
        
    }
    
    void push(int x) {
        while(!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
        s1.push(x);
    }
    
    int pop() {
        while(!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        int top = s2.top();
        s2.pop();
        return top;
    }
    
    int peek() {
        while(!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        return s2.top();
    }
    
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

141. Linked List Cycle

解題思路

slow/fast pointer 可以用來判斷 linked list 是否有環狀結構。因為 fast pointer traverse 的速度是 slow pointer 的兩倍，因此如果有環，兩個 pointer 一定會在繞圈圈的某次相遇。反之若無環，那當 fast 走到尾端就結束。

程式碼

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr)
            return false;

        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};

110. Balanced Binary Tree

解題思路

由上往下一個個 node 去檢查

程式碼

class Solution {
public:
    int getDepth(TreeNode* p)
    {
        if(p == nullptr)
            return 0;
        return max(getDepth(p->left), getDepth(p->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(root == nullptr)
            return true;

        int left = getDepth(root->left);
        int right = getDepth(root->right);
        if (abs(left - right) > 1)
            return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

235. Lowest Common Ancestor of a Binary Search Tree

解題思路

這題的目標，是找出兩個節點 p, q 的共同且 lowest 的祖先節點。又因為是 BST，所以一個節點的左子樹肯定都比它數值小、右子樹則會比較大。

觀察範例，會發現只要找到值介於 p, q 間的 node 就好。

程式碼

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val > q->val)
            swap(p, q);
        while(true)
        {
            if(p->val <= root->val && root->val <= q->val)
                return root;
            if(root->val > q->val)
                root = root->left;
            else
                root = root->right;
        }
    }
};

2023年1月10日星期二

733. Flood Fill

解題心得

如果一開始 image[sr][sc] 的顏色就跟 color 一樣，就不要往下了。卡在這邊好久。

程式碼

class Solution {
public:
    void helper(vector<vector<int>>& v, int target, int color, int sr, int sc)
    {
        if(!(0 <= sr && sr < v.size() && 0 <= sc && sc < v[0].size()))
            return;
        if(v[sr][sc] == target)
        {
            v[sr][sc] = color;
            helper(v, target, color, sr - 1, sc);
            helper(v, target, color, sr + 1, sc);
            helper(v, target, color, sr, sc - 1);
            helper(v, target, color, sr, sc + 1);
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image[sr][sc] != color)
            helper(image, image[sr][sc], color, sr, sc);
        return image;
    }
};

704. Binary Search

解題思路

中規中矩的 binary search tree。

程式碼

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

242. Valid Anagram

解題心得

第一時間想到用 hashTable，就是先算 s 的各 letter 數量，然後再用 t 的 letter 看一下。

但不小心手賤點開 tag，看到 sorting 的當下，默默就選擇這個寫法了......

程式碼

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

226. Invert Binary Tree

解題心得

想好一般條件跟終止條件。

程式碼

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)
            return nullptr;

        TreeNode* temp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = temp;
        return root;
    }
};

125. Valid Palindrome

解題思路

先把原始字串轉換成處理過後的，然後判斷回文。

小心除了小寫字母外，數字也要算進去。

程式碼

class Solution {
public:
    bool isPalindrome(string s) {
        string newS = "";
        for(int i=0; i<s.size(); i++)
        {
            if('A' <= s[i] && s[i] <= 'Z')
                newS += s[i] - 'A' + 'a';
            else if('0' <= s[i] && s[i] <= '9')
                newS += s[i];
            else if('a' <= s[i] && s[i] <='z')
                newS += s[i];
        }

        int front = 0, back = newS.size() - 1;
        while(front < back)
        {
            if(newS[front] != newS[back])
                return false;
            front++;
            back--;
        }
        return true;
    }
};

121. Best Time to Buy and Sell Stock

解題思路

從後面往前面看，找未來幾天最高價跟現在的價錢比，是不是值得賣出。

ps. 看了其他人的作法才發現我想的倒過來了，但想法正確就好 :D

程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int currentMax = prices[prices.size() - 1];
        int diffMax = 0;
        for(int i=prices.size() - 1; i>=0; i--)
        {
            if((currentMax - prices[i]) > diffMax)
                diffMax = currentMax - prices[i];
            if(prices[i] > currentMax)
                currentMax = prices[i];
        }
        return diffMax;
    }
};

2023年1月9日星期一

21. Merge Two Sorted Lists

解題思路

本題的目標是不額外生成 linked list 的情況下，將兩個 linked list 合併。

這個問題可以分三個部分來解決。首先，如何處理開頭的 node？該問題可以由 dummy node 的概念解決，意思是額外 new 一個多個 node 出來，用它的 next 來指向 merged list 的 head。

再來是如何 merge？其實也很簡單，想像說每次都比較 list 的頭，看哪個值比較小就把上個 node 的 next 指過來，同時記得更新 current 指到哪，以及 list 往後指一個。

最後是 while 迴圈結束時，並不代表事情做完了，兩個 list 還會有一個 list 沒空掉。那其實直接把 next 指向剩下的 list 就好了。

程式碼

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummpy;
        ListNode* current = &dummpy;

        while(list1 != nullptr && list2 != nullptr)
        {
            if(list1->val < list2->val)
            {
                current->next = list1;
                list1 = list1->next;
            }
            else
            {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        if(list1 != nullptr)
            current->next = list1;
        else if(list2 != nullptr)
            current->next = list2;
        return dummpy.next;
    }
};

20. Valid Parentheses

解題思路

這題是 stack 很經典的題目──括號匹配問題。

記得想好 edgecase。

程式碼

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for(int i=0; i<s.size(); i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                st.push(s[i]);
            else if(!st.empty() && s[i] == ')' && st.top() == '(')
                st.pop();
            else if(!st.empty() && s[i] == ']' && st.top() == '[')
                st.pop();
            else if(!st.empty() && s[i] == '}' && st.top() == '{')
                st.pop();
            else
                return false;
        }
        return st.empty();
    }
};

1. Two Sum

解題思路

第一時間想到的暴力解，是直接兩層迴圈去找相加和等不等於 target，時間複雜度 O(n^2)。

看提示中的 tag 有 hashTable，於是想到可以只用一次迴圈，也就是時間複雜度 O(n) 的解法。由於我們要找兩個 index，分別表示 array 中相加為 target 的兩個數，所以當我們有某個數值 n ，則需要找另一個數值 target - n 是否存在於 array。

既然這樣，那就在這一次的迴圈中，看當下這個新的數字 n，它的配對數字 target - n 是不是已經看過了(存在 map 中)。如果有，就結束這回合；如果沒有，記得把當下的數字 n 存進 map 中。

程式碼

方法一：暴力解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=i+1; j<nums.size(); j++)
            {
                if(nums[i] + nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
        return ans;
    }
};

方法二：hashTable

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(mp.count(target - nums[i]))
            {
                ans.push_back(i);
                ans.push_back(mp[target - nums[i]]);
                return ans;
            }
            mp[nums[i]] = i;
        }
        return ans;
    }
};

訂閱：文章 (Atom)

2023年1月31日 星期二

2023年1月30日 星期一

2023年1月29日 星期日

2023年1月28日 星期六

2023年1月27日 星期五

2023年1月26日 星期四

2023年1月25日 星期三

2023年1月24日 星期二

2023年1月23日 星期一

2023年1月22日 星期日

2023年1月20日 星期五

2023年1月19日 星期四

2023年1月18日 星期三

2023年1月17日 星期二

2023年1月16日 星期一

2023年1月14日 星期六

2023年1月13日 星期五

2023年1月12日 星期四

2023年1月11日 星期三

2023年1月10日 星期二

2023年1月9日 星期一

2023年1月31日星期二

2023年1月30日星期一

2023年1月29日星期日

2023年1月28日星期六

2023年1月27日星期五

2023年1月26日星期四

2023年1月25日星期三

2023年1月24日星期二

2023年1月23日星期一

2023年1月22日星期日

2023年1月20日星期五

2023年1月19日星期四

2023年1月18日星期三

2023年1月17日星期二

2023年1月16日星期一

2023年1月14日星期六

2023年1月13日星期五

2023年1月12日星期四

2023年1月11日星期三

2023年1月10日星期二

2023年1月9日星期一