链接:https://leetcode.com/tag/binary-search-tree/
【220】Contains Duplicate III (2019年4月20日) (好题)
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
题解:
解法1. brute force。 O(NK)
解法2. set + lower_bound(), sliding window, time complexity: O(NlogK), space O(K)
解法3. bucket:unordered_map<int, int> : key bucket idx, value nums[i], time complexity: O(N), space: O(K)
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (k <= || t < ) {return false;}
set<int> st;
for (int i = ; i < nums.size(); ++i) {
int num = nums[i];
auto iter = st.lower_bound(num);
if (iter != st.end()) {
int greater = *iter;
if ((long)greater - num <= t) {return true;}
}
if (iter != st.begin()) {
--iter;
int less = *iter;
if ((long)num - less <= t) {return true;}
}
if (st.size() == k) {
st.erase(nums[i-k]);
}
st.insert(num);
}
return false;
}
};
solution2
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.empty() || k <= || t < ) {return false;}
long bucketSize = (long)t + ;
int minn = nums.front();
for (auto& num : nums) {
minn = min(num, minn);
}
unordered_map<long, int> bucket; //key: bucketIdx, value: nums[i]
for (int i = ; i < nums.size(); ++i) {
long bucketIdx = ((long)nums[i] - minn) / bucketSize;
if (bucket.count(bucketIdx)) {return true;}
int left = bucketIdx - , right = bucketIdx + ;
if (bucket.count(left) && (long)nums[i] - bucket[left] <= t) {return true;}
if (bucket.count(right) && (long)bucket[right] - nums[i] <= t) {return true;}
if (i >= k) {
long removeKey = ((long)nums[i-k] - minn) / bucketSize;
bucket.erase(removeKey);
}
bucket[bucketIdx] = nums[i];
}
return false;
}
};
solution3
【315】Count of Smaller Numbers After Self
【327】Count of Range Sum
【352】Data Stream as Disjoint Intervals
【493】Reverse Pairs
【530】Minimum Absolute Difference in BST (2019年3月10日)(Easy)
返回一棵 BST的两个结点的最小绝对值的距离之差。
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
题解:根据 BST 的性质,我们只需要用一个变量记录中序遍历的前一个结点prev即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
if (!root) {return ;}
inorder(root);
return res;
}
int res = INT_MAX;
TreeNode* prev = nullptr;
void inorder(TreeNode* root) {
if (!root) {return;}
inorder(root->left);
if (prev) {
res = min(res, root->val - prev->val);
}
prev = root;
inorder(root->right);
return;
}
};
【683】K Empty Slots
【699】Falling Squares
【715】Range Module
【731】My Calendar II (2019年3月21日)
题意是每次给定一个 event [start, end) ,如果插入这个 event 之后, 当前有个时刻的同时进行的 event 的数量大于等于 3,那么就不插入这个 event,返回这个 event 能不能被插入。
此题只要找出所有与[start,end)重合的区间,再检查这些区间是否有互相的重合。是的话,说明必然有triple booking。
【732】My Calendar III (2019年3月21日)
题意是每次插入一个 event,返回插入这个event之后,对于任意一个时刻,同时在进行的 event 有多少个。
https://leetcode.com/problems/my-calendar-iii/description/
sweep line 的思想,用一个 multiset,记录 event 和 event 类型,如果是 start,event就表示成{start, 1}, 如果是 end,event 就表示成 {end, -1},然后每次插入之后,去遍历 multiset,如果碰到 1, 就 +1, 如果碰到 -1 ,就 -1。
【776】Split BST
【783】Minimum Distance Between BST Nodes (2019年3月10日)(Easy)
返回一棵 BST的两个结点的最小的距离之差。
Given a Binary Search Tree (BST) with the root node root
, return the minimum difference between the values of any two different nodes in the tree.
题解:同上面 530 题,一样的解法。
【938】Range Sum of BST