# Leetcode刷題學習筆記--map
hashmap是一個很好用的資料結構，可以把資料對應成key-value pairs，實際的實做是red-black tree，所以Time complexity為O(logN)。
+ map(key會從小到大排序，==字串的話則是依字典序排序==)
+ unordered_map(key不會排序)
+ multimap(允許key重複)
+ unordered_multimap
## Problems
### [496. Next Greater Element I(Easy)](https://leetcode.com/problems/next-greater-element-i/)
給定兩個array，nums1和nums2。其中nums1為nums2的子集合。找出nums1[i]在nums2出現的位置以後，第一個大於nums1[i]的值，如果沒有return -1。範例如下:
>Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
>- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
>- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
>- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

解題思路:
> 1. 使用map建立一個value和position的對應。這樣可以快速找到nums1的值在nums2的位置。
> 2. 找到位置之後，找尋下一個位置到最後大於nums1[i]的值。

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    map<int, int> m;
    auto nums2_size = nums2.size();
    for(int i = 0; i < nums2.size(); ++i)
        m[nums2[i]] = i;
    vector<int> rtn;
    for(auto& n : nums1) {
        int val = -1;
        for(int i = m[n] + 1; i < nums2_size; ++i) {
            if(nums2[i] > n) {
                val = nums2[i];
                break;
            }
        }
        rtn.push_back(val);
    }
    return rtn;
}

### [454. 4Sum II(Medium)](https://leetcode.com/problems/4sum-ii/)
這類問題除了用[two pointer](/gg-708HfRomJ66P7XX_QKQ)也可以用map來解。
給你四個vector<int> nums1, nums2, nums3, nums4，求出四個vector可以組合出來sum為0。
> 1. 使用map來統計兩兩個和。
> 2. 因為沒賦值得map為零，所以不須再額外判斷是否存在。

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    auto n = nums1.size();
    unordered_map<int, int> m1, m2;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            m1[nums1[i] + nums2[j]]++;
            m2[nums3[i] + nums4[j]]++;
        }
    }    
    
    int rtn{0};
    for(auto& a : m1)
        rtn += a.second * m2[-1 * a.first];
            
    return rtn;
}

### [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)
給你一個linked list node，除了指向next之外還指向random node，如下。copy所有的node。

class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

> 1. 因為是copy所有的node，所以用map來記錄新舊的對應。

class Solution {
    unordered_map<Node *, Node *> m;
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        if(m.count(head)) return m[head]; // 已經copy過了直接return
        Node *n = new Node(head->val);
        m[head] = n;    // 紀錄新舊對應
        n->random = copyRandomList(head->random);
        n->next = copyRandomList(head->next);
        
        return n;
    }
};

### [133. Clone Graph](https://leetcode.com/problems/clone-graph/)
和[138](/XfUiK191STCsppXWkgjbXQ#138-Copy-List-with-Random-Pointer)類似，題目改成無向圖。

class Solution {
    unordered_map<Node *, Node *> m;
public:
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;
        if(m.count(node)) return m[node];
        Node *n = new Node(node->val);
        m[node] = n;;
        for(Node *adj : node->neighbors) {
            n->neighbors.push_back(cloneGraph(adj));
        }
        return n;
    }
};

### [36. Valid Sudoku](https://leetcode.com/problems/valid-sudoku/)
使用客製的key來統計是否有資料重複在row, column和block中重複出現。

bool isValidSudoku(vector<vector<char>>& board) {
    unordered_set<string> s;
    for(int y = 0; y < 9; ++y) {
        for(int x = 0; x < 9; ++x) {
            if(!isdigit(board[y][x])) continue;
            string row = "r" + to_string(y) + "-" + board[y][x];
            string col = "c" + to_string(x) + "-" + board[y][x];
            string blk = "b" + to_string((y / 3) * 3 + (x / 3)) + "-" + board[y][x];
            if(s.count(row) || s.count(col) || s.count(blk)) return false;
            s.insert(row);
            s.insert(col);
            s.insert(blk);
        }
    }
    return true;
}

time complexity :
每一次的count為$O(logN)$，所以為$O(3logN)$，
每一次的insert為$O(logN)$，所以也是$O(3logN)$，
其中N為board的全部element數目($N = m * n$)。
所以$O(N * (3logN + 3logN)) = O(6NlogN) = O(NlogN)$

space complexity : $O(N)$，使用一個set紀錄全部的element。

### [652. Find Duplicate Subtrees](https://leetcode.com/problems/find-duplicate-subtrees/)
這題和[297. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)類似。
==客製key，把BST變成string，就可以用map來記錄是否有重複的BST。==

string helper(TreeNode *root, unordered_map<string, int>& m, vector<TreeNode *>& rtn) {
    if(!root) return "#";
    string cur = to_string(root->val) + " " + helper(root->left, m, rtn) + " " + helper(root->right, m, rtn);
    if(m[cur] == 1) rtn.push_back(root);
    m[cur]++;
    return cur;
}

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    vector<TreeNode *> rtn;
    unordered_map<string, int> m;
    helper(root, m, rtn);
    return rtn;
}

### [923. 3Sum With Multiplicity](https://leetcode.com/problems/3sum-with-multiplicity/)
一個數列中，找出nums[i] + nums[j] + nums[k] == target的所有組合數，其中i < j 且 j < k。數列中會有重複的數字。

> 1. 使用map來統計所以數的出現次數。
> 2. 使用兩個for來traverse map。
> 3. 三種情況，
> + 三個數都一樣
> + 兩個數一樣，一個不一樣
> + 三個數都不一樣。

int threeSumMulti(vector<int>& arr, int target) {
    map<int, long> m;
    for(auto& n : arr) m[n]++;
    long rtn = 0;
    for(auto it1 = m.begin(); it1 != m.end(); ++it1 ) {
        for(auto it2 = it1; it2 != m.end(); ++it2) {
            int i = it1->first, j = it2->first, k = target - i - j;
            if(!m.count(k)) continue;
            // 三個都一樣
            if(i == j && j == k)
                rtn += (m[i] * (m[i] - 1) * (m[i] - 2)) / 6;
            // 兩個一樣，一個不一樣，包括(1, 2, 2)或是(2, 2, 3)
            else if(i == j && j != k)
                rtn += (m[i] * (m[i] - 1)) / 2 * m[k];
            // 三個都不一樣
            // 因為不照順序會有重複的問題
            else if(i < j && j < k)
                rtn += m[i] * m[j] * m[k];
        }
    }
    return rtn % (long)(1e9 + 7);
}

### [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)
給你一個vector<int>，求出最長的連續數字的長度。

> 1. 使用unordered_map來記錄，每個數字的長度。
> 2. 如果目前的數字有旁邊的數，就把他接起來。並且更新最前面和最後面的長度。
> 3. 如果兩邊都有數字，就把兩邊的長度加起來再加一，一樣更新最前面和最後面的長度。

int longestConsecutive(vector<int>& nums) {
    int sz = nums.size();
    if(sz <= 1) return sz;
    unordered_map<int, int> m;
    int maxlen = 1;
    for(auto& n : nums) {
        if(m.count(n)) continue;
        else if(m.count(n - 1) && m.count(n + 1))
            m[n] = m[n + m[n + 1]] = m[n - m[n - 1]] = m[n + 1] + m[n - 1] + 1;
        else if(m.count(n - 1))
            m[n] = m[n - m[n - 1]] = m[n - 1] + 1;
        else if(m.count(n + 1))
            m[n] = m[n + m[n + 1]] = m[n + 1] + 1;
        else 
            m[n] = 1;
            
        maxlen = max(maxlen, m[n]);
    }
    // time  : O(N)
    // space : O(N)
    return maxlen;
}

### [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/description/)
給你一個vector<int> nums找出第一個missing positive。

> + 因為題目要求找出 missing positive，所以negtive用不到
> + 因為array的長度為sz，所以假設array都塞滿positive，則[1, 2, 3, ..., sz]，
答案一定是在[1, sz + 1] 之間
> + 使用index當成key，則0用不到，sz沒辦法用。所以把0當成sz
> + 當我們把negative或是n > sz換成1，則==數值的正負可以用來當成是否有找到數值的代表==
> + space : O(1), 只能使用固定長度的variable或是運用input本身。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int sz = nums.size();
        int containOne = 0;
        for(auto& n : nums) {
            if(n == 1) {
                containOne = 1;
                break;
            }
        }
        if(containOne == 0) return 1;
        for(auto& n : nums)
            if(n <= 0 || n > sz) n = 1;
        
        for(int i = 0; i < sz; ++i) {
            int a = abs(nums[i]);
            if(a == sz) nums[0] = -abs(nums[0]);
            else nums[a] = -abs(nums[a]);
        }

        for(int i = 1; i < sz; ++i) {
            if(nums[i] > 0) return i;
        }
        if(nums[0] > 0) return sz; // 少了sz
        else return sz + 1; // 
    }
};

###### tags: `leetcode` `刷題`