hashmap是一個很好用的資料結構，可以把資料對應成key-value pairs，實際的實做是red-black tree，所以Time complexity為O(logN)。
給定兩個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.
解題思路:
- 使用map建立一個value和position的對應。這樣可以快速找到nums1的值在nums2的位置。
- 找到位置之後，找尋下一個位置到最後大於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;
}
這類問題除了用two pointer也可以用map來解。
給你四個vector<int> nums1, nums2, nums3, nums4，求出四個vector可以組合出來sum為0。
- 使用map來統計兩兩個和。
- 因為沒賦值得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;
}
給你一個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;
}
};
- 因為是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;
}
};
和138類似，題目改成無向圖。
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;
}
};
使用客製的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。
這題和297. 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;
}
一個數列中，找出nums[i] + nums[j] + nums[k] == target的所有組合數，其中i < j 且 j < k。數列中會有重複的數字。
- 使用map來統計所以數的出現次數。
- 使用兩個for來traverse map。
- 三種情況，
- 三個數都一樣
- 兩個數一樣，一個不一樣
- 三個數都不一樣。
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);
}
給你一個vector<int>，求出最長的連續數字的長度。
- 使用unordered_map來記錄，每個數字的長度。
- 如果目前的數字有旁邊的數，就把他接起來。並且更新最前面和最後面的長度。
- 如果兩邊都有數字，就把兩邊的長度加起來再加一，一樣更新最前面和最後面的長度。
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;
}
給你一個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; //
}
};
leetcode 刷題
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe