Chapter 10 Set and Map
Lower_bound
10.1 220. Contains Duplicate III
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.
https://leetcode.com/problems/contains-duplicate-iii/
这里有两个限制条件,两个数字的坐标差不能大于k,值差不能大于t.这道题如果用brute force会超时,所以我们只能另辟蹊径.这里我们使用map数据结构来解,用来记录数字和其下标之间的映射. 这里需要两个指针i和j,刚开始i和j都指向0,然后i开始向右走遍历数组,如果i和j之差大于k,且m中有nums[j],则删除并j加一.这样保证了m中所有的数的下标之差都不大于k,然后我们用map数据结构的lower_bound()函数来找一个特定范围,就是大于或等于nums[i] - t的地方,所有小于这个阈值的数和nums[i]的差的绝对值会大于t (可自行带数检验).然后检测后面的所有的数字,如果数的差的绝对值小于等于t,则返回true.最后遍历完整个数组返回false.
http://www.cnblogs.com/grandyang/p/4545261.html
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long long, int> m;
int j = 0, L=nums.size();
for (int i = 0; i < L; ++i) {
if (i - j > k)
m.erase(nums[j++]);
auto a = m.lower_bound((long long)nums[i] - t);
if (a != m.end() && abs(a->first - nums[i]) <= t)
return true;
m[nums[i]] = i;
}
return false;
}
};10.2 315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
https://leetcode.com/problems/count-of-smaller-numbers-after-self
开始用下面的方法超时了,因为distance是linear的,所以T还是\(O(N^2)\).
struct Solution {
vector<int> countSmaller(vector<int>& nums) {
int L=nums.size();
if(L==0) return {};
vector<int> r(L);
multiset<int> si={nums.back()};
for(int i=L-2; i>=0; --i){ // N
auto it=si.lower_bound(nums[i]);
r[i]=distance(si.begin(), it); // linear
si.insert(it, nums[i]);
}
return r;
}
};其实我只需要一个BST,现在干脆在vector上构建了:
struct Solution {
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, r(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i])); // LogN + Constant
r[i] = d;
t.insert(t.begin() + d, nums[i]);
}
return r;
}
};注意
distance()是linear complexity,但是如果是random accessible(ie. raw pointer), 就是constant time. Refer to: http://en.cppreference.com/w/cpp/iterator/distance Complexity: Linear. However, if InputIt additionally meets the requirements of RandomAccessIterator, complexity is constant.
http://bit.ly/2xaWt81, 非常好的讲解: http://bit.ly/2xaUKiO
下面是手写数据结构版本:
struct Solution {
struct Node {
int val, smaller;
Node *left, *right;
Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
};
int insert(Node *&root, int v) {
if (!root) return (root = new Node(v, 0)), 0; //comma operator!?
if (root->val > v) return root->smaller++, insert(root->left, v);
return insert(root->right, v) + root->smaller + (root->val < v ? 1 : 0);
}
vector<int> countSmaller(vector<int>& nums) {
vector<int> r(nums.size());
Node *root = NULL;
for (int i = nums.size() - 1; i >= 0; --i)
r[i] = insert(root, nums[i]);
return r;
}
};这道题还有BIT解法.
只有一道题,给两个vector,求对于第二个vector中每个元素,第一个vector中有多少个元素比它小? http://bit.ly/2xvYWtD
vector<int> function(vector<int>& l, vector<int>& r){ // O(NlogN)
sort(l.begin(), l.end());
vector<int> r;
for(int i: r)
r.push_back(lower_bound(l.begin(), l.end(), i) - l.begin());
return r;
}lower_bound:
http://bit.ly/2xwGH7u
http://en.cppreference.com/w/cpp/algorithm/lower_bound
Complexity: The number of comparisons performed is logarithmic in the distance between first and last (At most Log(last - first) + O(1) comparisons). However, for non-RandomAccessIterators, the number of iterator increments is linear.
10.3 166. Fraction to Recurring Decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".https://leetcode.com/problems/fraction-to-recurring-decimal/
class Solution {
public String fractionToDecimal(int n, int d) {
if(n==0) return "0";
StringBuilder r=new StringBuilder();
r.append((n>0)^(d>0)?"-":"");
long x=Math.abs((long)n);
long y=Math.abs((long)d);
r.append(x/y);
x%=y;
if(x==0) return r.toString(); // integer part
r.append("."); // fractional part
Map<Long,Integer> m=new HashMap<>();
m.put(x, r.length());
while(x!=0){
x*=10;
r.append(x/y);
x%=y;
if(m.containsKey(x)){
r.insert(m.get(x), "(");
r.append(')');
break;
}else{
m.put(x, r.length());
}
}
return r.toString();
}
}10.4 781. Rabbits in Forest
In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.
Return the minimum number of rabbits that could be in the forest.
Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered “1” could both be the same color, say red.
The rabbit than answered “2” can’t be red or the answers would be inconsistent.
Say the rabbit that answered “2” was blue.
Then there should be 2 other blue rabbits in the forest that didn’t answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn’t.
Input: answers = [10, 10, 10]
Output: 11
Note:
answers will have length at most 1000.
Each answers[i] will be an integer in the range [0, 999].10.5 249. Group Shifted Strings
Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:
“abc” -> “bcd” -> … -> “xyz”
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”], A solution is:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]https://leetcode.com/problems/group-shifted-strings/
http://www.cnblogs.com/grandyang/p/5204770.html
我们可以更加巧妙的利用偏移字符串的特点,那就是字符串的每个字母和首字符的相对距离都是相等的,比如abc和efg互为偏移,对于abc来说,b和a的距离是1,c和a的距离是2,对于efg来说,f和e的距离是1,g和e的距离是2.再来看一个例子,az和yx,z和a的距离是25,x和y的距离也是25(直接相减是-1,这就是要加26然后取余的原因),那么这样的话,所有互为偏移的字符串都有个unique的距离差,我们根据这个来建立映射就可以很好的进行单词分组了,这个思路真实太赞了,参见代码如下:
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
vector<vector<string> > res;
unordered_map<string, multiset<string>> m; ////
for (auto a : strings) {
string t = "";
for (char c : a) // Construct Key!
t += to_string((c + 26 - a[0]) % 26) + ","; ////
m[t].insert(a);
}
for (auto it = m.begin(); it != m.end(); ++it) {
res.push_back(vector<string>(it->second.begin(), it->second.end()));
}
return res;
}
};