# 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]的值。
```c++
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為零，所以不須再額外判斷是否存在。
```cpp=
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。
```cpp=
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
```
> 1. 因為是copy所有的node，所以用map來記錄新舊的對應。
```cpp=
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)類似，題目改成無向圖。
```cpp=
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中重複出現。
```cpp=
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。==
```cpp=
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. 如果兩邊都有數字，就把兩邊的長度加起來再加一，一樣更新最前面和最後面的長度。
```cpp=
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本身。
```cpp=
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` `刷題`
Sign in with Wallet
Connect another wallet