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