【LeetCode】二叉查找树 binary search tree(共14题)

链接: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

上一篇:【LeetCode】212. Word Search II 解题报告(C++)


下一篇:SharePoint自动化系列——Add content type to list.