42. Trapping Rain Water

解題思路

這題看題目時沒想法，但看完 neetcode 的解法後恍然大悟。我覺得分析問題時，如果當下沒辦法想出演算法，可以先用人類笨方法思索人類會怎麼解問題。確定這解法 ok 後，再轉換成比較電腦的形式，一步步轉換過去。

程式碼

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0, minHeight;
        vector<int> leftMax(n, 0);
        vector<int> rightMax(n, 0);

        for(int i=1; i<n; i++)
        {
            leftMax[i] = max(leftMax[i-1], height[i-1]);
            rightMax[n-1-i] = max(rightMax[n-i], height[n-i]);
        }
        for(int i=0; i<n; i++)
        {
            minHeight = min(leftMax[i], rightMax[i]);
            ans += max(minHeight - height[i], 0);
        }
        
        return ans;
    }
};

167. Two Sum II - Input Array Is Sorted

解題思路

因為 sorted array 的特性，選擇用 two pointer 來解。

當 left pointer 往右移，代表數字總和會變大；當 right pointer 往左移，代表數字總和會變小。由於一定能找到解，因此就不斷重述這樣的動作，查看當下兩個 pointer 的數字和並跟 target 比較，一直到找到為止。

程式碼

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while((numbers[left] + numbers[right]) != target)
        {
            if((numbers[left] + numbers[right]) > target)
                right--;
            else
                left++;
        }

        vector<int> ans;
        ans.push_back(left + 1);
        ans.push_back(right + 1);
        return ans;
    }
};

347. Top K Frequent Elements

解題思路

這題可以用 maxHeap 的概念來解。又因為 sort 的依據是出現次數，但 key 是數字本身的值，所以用 pair。

首先建立 integer 跟其出現次數的 map，接著再從該 map 轉換放進 maxHeap 中。由於 priority_queue 是看 first 來 sort ，因此這邊選擇以 {e.second, e.first} 的形式來 push。

接下來只要 pop k 次 maxHeap 即可。注意此時要的是 maxHeap 的 second。

程式碼

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> maxHeap; // integer, occurence
        vector<int> ans;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++)
            mp[nums[i]]++;
        
        for(auto e:mp)
            maxHeap.push({e.second, e.first});
        
        for(int i=0; i<k; i++)
        {
            ans.push_back(maxHeap.top().second);
            maxHeap.pop();
        }
        return ans;
    }
};

128. Longest Consecutive Sequence

解題思路

基本上就是把不同的連續數列串在一起，每串的頭是最小的數，ex: 1->2->3->4。

所以先用 set 紀錄整個 array 中有哪些數字，接著再從頭看起。若該數是串的頭(不存在 nums[i]-1)，哪麼就計算該串的長度(用 set 一直檢查 nums[i]+offset 存不存在)。

程式碼

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        
        set<int> s;
        for(int i=0; i<nums.size(); i++)
            s.insert(nums[i]);
        
        int maxLen = 1;
        for(int i=0; i<nums.size(); i++)
        {
            // check if it the head of seq first
            if(!s.count(nums[i] - 1))
            {
                int curLen = 1, offset = 1;
                while(s.count(nums[i] + offset))
                {
                    offset++;
                    curLen++;
                    maxLen = max(maxLen, curLen);
                }
            }
        }
        return maxLen;
    }
};

19. Remove Nth Node From End of List

解題思路

不用 reverse 就能刪倒數第  n 個節點，只要用 two pointer。left pointer 跟 right pointer 不是平常的差一個，而是差 n 個節點。如此一來，當 right pointer 指向 null 時，left pointer 指到的恰好就是我們想要刪掉的節點。

但真正方便的是指向要刪掉的前一個節點，這樣才能進行刪除。為了達成此目標，選擇 left node 一開始指向 dummy node。

程式碼

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode();
        ListNode *left = dummy, *right = head;
        dummy->next = head;

        for(int i=0; i<n; i++)
            right = right->next;
        
        while(right != nullptr)
        {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return dummy->next;
    }
};

417. Pacific Atlantic Water Flow

解題思路

反向思考，從海到陸是否可以。

用 dfs 解兩次。

程式碼

class Solution {
public:

    void dfs(int x, int y, vector<vector<int>>& heights, vector<vector<bool>>& isVisited, int prevH)
    {
        if(x < 0 || y < 0 || x >= heights.size() || y >= heights[0].size() 
        || isVisited[x][y] || heights[x][y] < prevH)
            return;
        isVisited[x][y] = true;
        dfs(x - 1, y, heights, isVisited, heights[x][y]);
        dfs(x + 1, y, heights, isVisited, heights[x][y]);
        dfs(x, y - 1, heights, isVisited, heights[x][y]);
        dfs(x, y + 1, heights, isVisited, heights[x][y]);
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<bool>> pac(heights.size(), vector<bool>(heights[0].size(), false));
        vector<vector<bool>> alt(heights.size(), vector<bool>(heights[0].size(), false));

        for(int i=0; i<heights.size(); i++)
        {
            dfs(i, 0, heights, pac, heights[i][0]);
            dfs(i, heights[0].size() - 1, heights, alt, heights[i][heights[0].size() - 1]);
        }
        for(int i=0; i<heights[0].size(); i++)
        {
            dfs(0, i, heights, pac, heights[0][i]);
            dfs(heights.size() - 1, i, heights, alt, heights[heights.size()- 1][i]);
        }

        vector<vector<int>> ans;
        for(int i=0; i<heights.size(); i++)
        {
            for(int j=0; j<heights[0].size(); j++)
            {
                if(pac[i][j] && alt[i][j])
                    ans.push_back({i, j});
            }
        }
        return ans;

    }
};

208. Implement Trie (Prefix Tree)

解題思路

看題目敘述直接想到之前寫過的 208. Implement Trie (Prefix Tree)，所以直接拿那題的程式改改看。

Node class 跟 addWord 直接複製貼上，而 search 需要修改。兩題差別在於要思考遇到 . 要怎麼辦，其實就是找當下節點底下有哪些路徑，全走過一遍找看看，所以會需要重複呼叫函式。進一步改寫後就變 dfs 了。

程式碼

class Node{
public:
    bool isEnd;
    Node* child[26];
    Node()
    {
        isEnd = false;
        for(int i=0; i<26; i++)
            child[i] = nullptr;
    }
};
class WordDictionary {
public:
    Node* root = new Node();
    WordDictionary() {
        
    }
    
    void addWord(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 dfs(Node* root, int start, string& word)
    {
        Node* current = root;
        for(int i=start; i<word.size(); i++)
        {
            if(word[i] == '.')
            {
                for(auto child : current->child)
                {
                    if(child != nullptr && dfs(child, i+1, word))
                        return true;
                }
                return false;
            }
            else if(current->child[word[i] - 'a'] == nullptr)
                return false;
            current = current->child[word[i] - 'a'];
        }
        return current->isEnd == true;
    }
    bool search(string word) {
        return dfs(root, 0, word);
    }
};

152. Maximum Product Subarray

解題思路

題目敘述讓我想到之前寫過 53. Maximum Subarray 這題，只是變成乘積最大。

一樣另外開陣列，存當下那個數的 subarray 最大能多少。但乘法與加法不一樣，兩個負數相乘會變回正，所以也要存最負 array。

程式碼

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> maxArr(nums.size(), 0);
        vector<int> minArr(nums.size(), 0);
        maxArr[0] = nums[0];
        minArr[0] = nums[0];

        int maxP = maxArr[0];
        for(int i=1; i<nums.size(); i++)
        {
            maxArr[i] = max({nums[i], maxArr[i-1] * nums[i], minArr[i-1] * nums[i]});
            minArr[i] = min({nums[i], maxArr[i-1] * nums[i], minArr[i-1] * nums[i]});
            maxP = max(maxP, maxArr[i]);
        }
        return maxP;
    }
};

49. Group Anagrams

解題思路

anagram 經過 sort 後會長的一樣，用這個特性以 map 與 vector 紀錄，再轉成指定的型態回傳。

程式碼

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<int>> mp; // word -> index
        string s;
        for(int i=0; i<strs.size(); i++)
        {
            s = strs[i];
            sort(s.begin(), s.end());
            mp[s].push_back(i);
        }
        vector<vector<string>> ans;
        for(auto word : mp)
        {
            vector<string> v;
            for(int i=0; i<word.second.size(); i++)
            {
                v.push_back(strs[word.second[i]]);
            }
            ans.push_back(v);
        }
        return ans;
    }
};

36. Valid Sudoku

解題思路

分成 row, column 以及九個 box，個別計算。 

程式碼

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][10] = {0}, col[9][10] = {0}, box[9][10] = {0};
        for(int i=0; i<9; i++)
        {
            for(int j=0; j<9; j++)
            {
                if(board[i][j] == '.') continue;
                row[i][board[i][j] - '0']++;
                col[j][board[i][j] - '0']++;
                box[i/3*3 + j/3][board[i][j] - '0']++;
                if(row[i][board[i][j] - '0'] > 1 || col[j][board[i][j] - '0'] > 1 || box[i/3*3 + j/3][board[i][j] - '0'] > 1)
                {
                    cout << row[i] << " " << col[j] << " " << box[i/3*3 + j/3] << endl;
                    return false;
                }    
            }
        }
        return true;
    }
};

198. House Robber

解題思路

是要 rob 當下這間以及上上間能 rob 的總和，還是不 rob 這間而取上間 rob 的總和？

程式碼

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0], nums[1]);
        vector<int> money(nums.size(), 0);
        money[0] = nums[0], money[1] = max(nums[0], nums[1]);

        for(int i=2; i<nums.size(); i++)
            money[i] = max(money[i-1], nums[i] + money[i-2]);
        return money[nums.size() - 1];
    }
};

739. Daily Temperatures

解題思路

用 stack 紀錄還沒找到 warmer 的日子。用 pair 同時保有日期跟溫度。

pair 用法：

pair<type, type> p;

p.first = ???, p.second = ???

make_pair(???, ???);

程式碼

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(), 0);
        stack<pair<int, int>> st; // stack for pair(temp, index)

        for(int i=0; i<temperatures.size(); i++)
        {
            while(!st.empty() && st.top().first < temperatures[i])
            {
                ans[st.top().second] = i - st.top().second;
                st.pop();
            }
            st.push(make_pair(temperatures[i], i));
        }
        return ans;
    }
};

230. Kth Smallest Element in a BST

解題思路

拿數字 k 來檢查現在用 inorder 走訪過幾個 node，每次走訪都把 k 減 1。

當 k 為 0，表示這個 node 就是我們要的。存在 ans 裡面。

程式碼

class Solution {
public:
    int ans = 0;

    void helper(TreeNode* root, int& k)
    {
        if(root == nullptr)
            return;
        
        helper(root->left, k);
        k--;
        if(k == 0) ans = root->val;
        helper(root->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        helper(root, k);
        return this->ans;
    }
};

146. LRU Cache

解題思路

看 neetcode 的影片，用他的解法來解。

改天自己重新思考重寫一次。

程式碼

class Node {
public:
    int key, value;
    Node *prev, *next;
    Node(int key, int value) {
        this->key = key;
        this->value = value;
        this->prev = this->next = nullptr;
    }
};

class LRUCache {
public:
    int cap;
    unordered_map<int, Node*> cache; // key to node pointer
    Node *left, *right; // least recent, most recent

    LRUCache(int capacity) {
        this->cap = capacity;
        this->left = new Node(0, 0);
        this->right = new Node(0, 0);
        this->left->next = this->right;
        this->right->prev = this->left;
    }

    void remove(Node* node) { // remove node from double linked-list
        Node *pre = node->prev, *nxt = node->next;
        pre->next = nxt;
        nxt->prev = pre;
    }

    void insert(Node* node) { // insert node into double linked-list
        Node *pre = this->right->prev, *nxt = this->right;
        pre->next = nxt->prev = node;
        node->prev = pre;
        node->next = nxt;
    }
    
    int get(int key) {
        if(cache.count(key)) { // first update the node to the right-most
            remove(cache[key]);
            insert(cache[key]);
            return cache[key]->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(cache.count(key))
        {
            remove(cache[key]);
        }
        cache[key] = new Node(key, value); // update hashmap
        insert(cache[key]); // update linked-list

        if(cache.size() > this->cap)
        {
            Node* LRU = this->left->next;
            remove(LRU); // remove the LRU 
            cache.erase(LRU->key);
        }
    }
};

621. Task Scheduler

解題思路

用公式計算。

程式碼

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        if(n == 0) return tasks.size();
        int arr[26] = {0}, maxTask = 0, maxTaskCount = 0;
        for(int i=0; i<tasks.size(); i++)
        {
            arr[tasks[i] - 'A']++;
            maxTask = max(maxTask, arr[tasks[i] - 'A']);
        }
        for(int i=0; i<26; i++)
        {
            if(arr[i] == maxTask)
                maxTaskCount++;
        }
        int ans = (n+1) * (maxTask-1) + maxTaskCount;
        return max((int)tasks.size(), ans);
    }
};

310. Minimum Height Trees

解題思路

照著網路上其他人「一層層剝開 leaf node」的思維去寫。

有空再寫一次。

程式碼

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return vector<int>(1, 0);
        vector<set<int>> graph(n);
        for(int i=0; i<edges.size(); i++)
        {
            graph[edges[i][0]].insert(edges[i][1]);
            graph[edges[i][1]].insert(edges[i][0]);
        }
        vector<int> leafNode, nextLeafNode;
        for(int i=0; i<n; i++)
        {
            if(graph[i].size() == 1)
                leafNode.push_back(i);
        }

        while(!leafNode.empty())
        {
            for(auto node : leafNode)
            {
                for(auto connect : graph[node])
                {
                    graph[connect].erase(node);
                    if(graph[connect].size() == 1)
                        nextLeafNode.push_back(connect);
                }
            }
            if(nextLeafNode.empty()) break;
            swap(leafNode, nextLeafNode);
            nextLeafNode.clear();
        }
        
        return leafNode;

    }
};

438. Find All Anagrams in a String

解題思路

兩個 index 分別記錄出現次數，每次比對一不一樣。

滑動 window 的時候不用重新計算，而是以「拔掉 left」與「加上 right」的方式節省時間。

程式碼

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int sArr[26] = {0}, pArr[26] = {0}, left = 0;
        if(p.size() > s.size()) return ans;

        for(int i=0; i<p.size(); i++)
        {
            pArr[p[i] - 'a']++;
            sArr[s[i] - 'a']++;
        }
        while(left <= s.size() - p.size())
        {
            bool isSame = true;
            for(int i=0; i<26; i++)
            {
                if(sArr[i] != pArr[i])
                    isSame = false;
            }
            if(isSame) ans.push_back(left);

            if(left == s.size() - p.size()) break;
            sArr[s[left] - 'a']--; sArr[s[left+p.size()] - 'a']++;
            left++;
        }
        return ans;
    }
};

79. Word Search

解題思路

base case 是 word 只剩一個字而且是要找的字。以及錯誤判斷寫對。

isVisited 要先標記走過，接著遞迴下去找，最後記得改回來。

程式碼

class Solution {
public:
    bool search(vector<vector<char>>& board, string word, vector<vector<bool>>& isVisited, int x, int y)
    {
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
        if(isVisited[x][y] || word[0] != board[x][y]) return false;
        if(word.size() == 1 && word[0] == board[x][y]) return true;

        isVisited[x][y] = true;
        
        bool isFind = search(board, word.substr(1), isVisited, x-1, y) || search(board, word.substr(1), isVisited, x+1, y) || search(board, word.substr(1), isVisited, x, y-1) || search(board, word.substr(1), isVisited, x, y+1);

        isVisited[x][y] = false;
        return isFind;
    }
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> isVisited(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(search(board, word, isVisited, i, j))
                    return true;
            }
        }
        return false;
    }
};

17. Letter Combinations of a Phone Number

解題思路

對照的部分用 string array 紀錄，同時以 auto 方式遍歷會比較方便。

程式碼

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string mapping[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue<string> q;
        vector<string> ans;
        if(digits == "")
            return ans;

        q.push("");
        for(int i=0; i<digits.size(); i++)
        {
            int n = q.size();
            while(n--)
            {
                string temp = q.front();
                q.pop();
                for(auto c : mapping[digits[i] - '0'])
                    q.push(temp + c);
            }
        }

        while(!q.empty())
        {
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }
};

11. Container With Most Water

解題思路

哪兩條直線能圍出最大面積？用 two pointer 分別指向兩端，慢慢往內縮求極值。

程式碼

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxA = 0, curA;
        while(left < right)
        {
            curA = min(height[left], height[right]) * (right - left);
            maxA = max(maxA, curA);
            if(height[left] < height[right])
                left++;
            else
                right--;            
        }
        return maxA;
    }
};

105. Construct Binary Tree from Preorder and Inorder Traversal

解題思路

藉由 inorder 與 preorder 還原出原本的 binary tree 是資料結構中的內容，因此照著演算法模擬即可。

不過好像在時間複雜度上還有可進步的空間XD

程式碼

class Solution {
public:
    TreeNode* append(TreeNode* root, int value, unordered_map<int, int>& mp)
    {
        if(root == nullptr)
            root = new TreeNode(value);
        else if(mp[root->val] < mp[value])
            root->right = append(root->right, value, mp);
        else
            root->left = append(root->left, value, mp);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> mp;
        for(int i=0; i<inorder.size(); i++)
            mp[inorder[i]] = i;
        
        TreeNode* root = nullptr;
        for(int i=0; i<preorder.size(); i++)
            root = append(root, preorder[i], mp);
        return root;
    }
};

62. Unique Paths

解題思路

直覺想到高中數學的排列組合。套公式為 C(m+n-2, m-1)，也就是 (m+n-2)! / (m-1)!(n-1)!。

寫成程式的話，必須進一步化簡計算量，模擬分母 (m+n-2)! 跟 (m-1)!, (n-1)! 中較大的數字約分，以及乘上(m-1)!, (n-1)! 中較小的數字。

可以進一步一邊乘 (top-i) 又一邊除 (i+1) 而不會說數字無法整除而有錯，背後的想法是連續整數在同樣乘或除第N個數的時候，因為連續的特性所以就能除盡。

也可以用 DP，下次試看看。

程式碼

class Solution {
public:
    int uniquePaths(int m, int n) {
        int top = m + n - 2;
        int down = min(m, n) - 1;

        long long int ans = 1;
        for(int i=0; i<down; i++)
        {
            ans = ans * (top - i) / (i + 1);
        }
        return ans;
    }
};

5. Longest Palindromic Substring

解題思路

根據 neetcode 的直覺解法解題。以「自己」為中心，左右尋找最佳可能解，分成偶數奇數長度兩種來判斷。

程式碼

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLen = 0, left, right;
        string maxP = "";

        for(int i=0; i<s.size(); i++)
        {
            // odd
            left = i, right = i;
            while(left >=0 && right < s.size() && s[left] == s[right])
            {
                if((right - left + 1) > maxLen)
                {
                    maxLen = right - left + 1;
                    maxP = s.substr(left, right - left + 1);
                }
                left--;
                right++;
            }

            // even
            left = i, right = i+1;
            while(left >=0 && right < s.size() && s[left] == s[right])
            {
                if((right - left + 1) > maxLen)
                {
                    maxLen = right - left + 1;
                    maxP = s.substr(left, right - left + 1);
                }
                left--;
                right++;
            }
        }
        return maxP;
    }
};

199. Binary Tree Right Side View

解題思路

一次檢查一個 level，每次都先把最右邊的紀錄下來，其他的把左右子節點放進 queue。

程式碼

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            ans.push_back(q.back()->val);
            int size = q.size();
            for(int i=0; i<size; i++)
            {
                if(q.front()->left) q.push(q.front()->left);
                if(q.front()->right) q.push(q.front()->right);
                q.pop();
            }
        }
        return ans;
    }
};

78. Subsets

解題思路

找出所有可能的子集。

方法就是用 for 看過從「開頭」以後的每個位置，每次都是「選」或者「不選」兩種可能。

程式碼

class Solution {
public:
    void helper(vector<int>& nums, int start, vector<vector<int>>& ans, vector<int> v)
    {
        ans.push_back(v);
        for(int i=start; i<nums.size(); i++)
        {
            v.push_back(nums[i]);
            helper(nums, i+1, ans, v);
            v.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> v;
        helper(nums, 0, ans, v);
        return ans;
    }
};

54. Spiral Matrix

解題思路

模擬好難......

程式碼

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int up = 0, down = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;

        while(true)
        {
            for(int i=left; i<=right; i++) ans.push_back(matrix[up][i]);
            up++; if(up > down || left > right) break;
            for(int i=up; i<=down; i++) ans.push_back(matrix[i][right]);
            right--; if(up > down || left > right) break;
            for(int i=right; i>=left; i--) ans.push_back(matrix[down][i]);
            down--; if(up > down || left > right) break;
            for(int i=down; i>=up; i--) ans.push_back(matrix[i][left]);
            left++; if(up > down || left > right) break;
        }
        return ans;
    }
};

8. String to Integer (atoi)

解題心得

很多 edge case 需要考慮的一題。

程式碼

class Solution {
public:
    int myAtoi(string s) {
        long double ans = 0;
        int i=0;
        bool isPositive = true;
        while(s[i] == ' ')
            i++; // ignore the leading whitespace
        if(s[i] == '-')
        {
            isPositive = false;
            i++;
        }
        else if(s[i] == '+')
        {
            isPositive = true;
            i++;
        }

        for(; i<s.size(); i++)
        {
            if(s[i] > '9' || s[i] < '0')
                break;
            ans = ans * 10 + s[i] - '0';
        }

        if(!isPositive) ans *= -1;
        if(ans > INT_MAX) return INT_MAX;
        else if(ans < INT_MIN) return INT_MIN;
        return ans;
    }
};

416. Partition Equal Subset Sum

解題思路

1. 如果 array 的總和是奇數，那麼不用想了，一定找不到能分兩半的組合

2. 接下來，題目被簡化成找 target = sum / 2 在 array 中是否有該組合

原本想用 set 做，traverse array[i] 的時候把新的可能加進去，但沒想到效率很慢。

改用 bool vector 來記錄 sum = i 的組合是否能找到。

程式碼

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
            sum += nums[i];
        
        if(sum % 2 == 1) return false;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=target; j>=nums[i]; j--)
                dp[j] = dp[j] || dp[j - nums[i]];
        }
        return dp[target];
    }
};

139. Word Break

解題思路

零錢問題的字串版(?)

要用 hashMap 來存已經看過的節省時間，不然就 TLE。

程式碼

class Solution {
public:
    unordered_map<string, bool> mp;
    bool helper(string s, vector<string>& wordDict)
    {
        if(mp.count(s))
            return mp[s];
        if(s == "")
            return true;
        for(int i=0; i<wordDict.size(); i++)
        {
            if(s.rfind(wordDict[i], 0) == 0)
            {
                if(helper(s.substr(wordDict[i].size()), wordDict))
                {
                    mp[s] = true;
                    return true;
                }
            }
        }
        mp[s] = false;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        return helper(s, wordDict);
    }
};

75. Sort Colors

解題思路

不能用寫好的 sort 函式，而且要 in-place。提示裡面說紀錄 0 跟 1 的數量，所以就照這個做法。

程式碼

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count0 = 0, count1 = 0;
        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i] == 0)
                count0++;
            else if(nums[i] == 1)
                count1++;
        }
        for(int i=0; i<count0; i++)
            nums[i] = 0;
        for(int i=count0; i<count0+count1; i++)
            nums[i] = 1;
        for(int i=count0+count1; i<nums.size(); i++)
            nums[i] = 2;
    }
};

721. Accounts Merge

解題思路

這類「誰跟誰是一個小群體」的題目跟 union find 有關，這題額外加上還有 "name" 這一個標示群體名稱的字串。

解題分為四步，

step1: 初始化，每一個 email 的老大(parent)都是自己，並且記錄 email 的擁有者叫甚麼名字。

step2: 透過 find function，把每串除了第一個(本來就指向自己)的其餘的老大都指向第一個。在這個過程中，如果兩串都有同一個 email 出現，那自然會被歸在同一個群體之中(因為老大都一樣)。

step3: 先前只是記錄 email 跟對應的老大是誰。在 step3 要轉成 map 結構，一個老大 string 所屬的擁有者名字會對應到 set of other strings in the same group。做法是 traverse 每一個 email，map[老大].insert(自己)

step4:  依題目要求把 email 們先 sort，接著把名字加入即可。

這題好難，改天再寫一次。

程式碼

class Solution {
public:
    string find(string email, unordered_map<string, string>& parent)
    {
        if(email != parent[email])
            parent[email] = find(parent[email], parent); // compress
        return parent[email];
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, string> owner; // email's owner(email -> name)
        unordered_map<string, string> parent; // email's parent for union
        unordered_map<string, set<string>> unions; // answer

        // Step 1
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                owner[account[i]] = account[0];
                parent[account[i]] = account[i];
            }
        }
        
        // Step 2
        for (auto account : accounts) {
            string p = find(account[1], parent);
            for (int i = 2; i < account.size(); i++) {
                parent[find(account[i], parent)] = p;
            }
        }
        
        // Step 3
        for (auto email : owner) {
            unions[find(email.first, parent)].insert(email.first);
        }
        
        // Step 4
        vector<vector<string>> result;
        for (auto union_ : unions) {
            vector<string> emails(union_.second.begin(), union_.second.end());
            emails.insert(emails.begin(), owner[union_.first]);
            result.push_back(emails);
        }
        return result;

    }
};