Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10
Solution 1: Monotonic Stack
Use a monotonic stack to maintain the higher bars’s indices in ascending order. When encounter a lower bar, pop the tallest bar and use it as the bottleneck to compute the area.
Given an array of integers arr and two integers k and threshold.
Return the number of sub-arrays of size k and average greater than or equal to threshold.
Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.
Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
Example 1:
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
Example 2:
Input: num = 8
Output: 4
Explanation:
Step 1) 8 is even; divide by 2 and obtain 4.
Step 2) 4 is even; divide by 2 and obtain 2.
Step 3) 2 is even; divide by 2 and obtain 1.
Step 4) 1 is odd; subtract 1 and obtain 0.
想不到吧，hashtable是在C++11才正式标准化的，虽然之前各编译器都有支持，但毕竟不是标准版。unordered_*提供了O(1)时间的查找、插入和删除。是一个非常高效的数据结构（C用户哭晕在厕所）。为什么叫unorderd_map这么奇怪的一个名字而不直接叫hash_map呢？只是为了告诉用户key是无序的吗？标准委员会给出的回答是：hash_map已经被各大vendor抢注了，同名容易造成冲突… 哎，谁让你这么晚才标准化呢！？域名抢注要趁早！ Java对应：HashMap，HashSet Python对应：dict, set
2. initializer_list C++11
initializer_list方便了（容器）对象的初始化
int a = 2; // Before, assignment int a{2}; // After, construction
vector<int> v; // Before v.push_back(1); v.push_back(2); v.push_back(3);
vector<int> v = {1,2,3}; // After, assignment vector<int> v{1,2,3}; // After, construction 对于vector<int> v{1,2,3}; 编译器做了两件事情： 1. 用{1,2,3}字面量创建 initializer_list<int> l 2. 调用vector<int>的拷贝构造函数，传入l 所以说使用initializer_list还是有一些些overhead的
pair<int, float> p{1, 3.14}; // After map<string, int> m{{“hello”, 1}, {“world”, 2}}; // After
vector<int> foo() { // Before set<int> s = … return vector<int>(begin(s), end(s)); } vector<int> foo() { // After set<int> s = … return {begin(s), end(s)}; }
Java对应：多种不同方法… Python对应：[], (), {}
3. auto 关键词 C++11
新增的auto关键词让人又爱又恨，编译器做了类型推断省去了冗长的类型名称的拼写，但需谨慎使用。
int a = 2; auto a = 2; // a is int
float a = 2; // implicit conversion auto a = 2; // a is int not float auto a = 2.0; // a is double not float auto a = 2.0f; // a is flot
auto v{1,2,3}; // does not compile auto v = {1,2,3}; // v is initializer_list not vector auto v = vector<int>{1,2,3,4}; // ok, but longer vector<int> v{1,2,3,4}; // best
std::unique_ptr<Foo> p = std::make_unique<Foo>(…); // Before auto p = std::make_unique<Foo>(…); // OK, shorter
有多少人是被iterator劝退的？ for (std::unordered_map<std::string, int>::const_iterator it = s.begin(); it != s.end(); ++it) // Before for (auto it = s.begin(); it != s.end(); ++it) // After
Java对应：var Java10 Python对应：傲娇地说：类型是神马？
4. Structured Binding C++17
有了类型推断和auto关键词之后我们就可以做结构化绑定了
// Before pair<int, float> p(1, 3.14); int x = p.first; float y = p.second;
// After auto [x, y] = p; // must use auto // x is int, x = 1; // y is float, y = 3.14
// Before set<int> s; auto kv = s.insert(x); auto it = kv.first; // iterator bool success = kv.second; // inserted or not
// After set<int> s; auto [it, success] = s.insert(x);
我们在下面还会看到结构化绑定的身影
Java 对应：null Python 对应：a, b = c, d
5. Range based for loop C++11
这也是一个非常好用的功能，配合上auto和structured binding简直了。
for (int i = 0; i < v.size(); ++i) cout << v[i] << endl; // Before for (int x : v) cout << x << endl; // After
for (std::unordered_map<std::string, int>::const_iterator it = s.begin(); it != s.end(); ++it) // Before for (auto it = s.begin(); it != s.end(); ++it) // w/ auto for (auto&& kv : s) cout << kv.first << “->” << kv.second << endl; // range based for loop for (auto&& [k, v] : s) cout << k << “->” << v << endl; // w/ structured binding
Java 对应 for (int x : v) Python 对应 for k, v in s.items()
6. Lambda Expressions C++11
我们可以用lambda表达式来捕获对象并创建closure（闭包）。
最简单的用法是创建function对象，你可以把它看做在函数里面定义函数。
1
2
auto sum=[](inta,intb){returna+b;};
ints=sum(2,3);// s = 5
也可以用来自定义排序
1
2
3
4
5
6
boolcomp(constFoo&a,constFoo&b){return...;}
voidBar(){
vector<Foo>v=...
sort(begin(v),end(v),comp);// Before
sort(begin(v),end(v),[](constauto&a,constauto&b){return...;});// After
