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

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

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