Summary
给自己定了一个目标，每天晚上刷一道 leetcode 题目。刚看了下手机，已经最长连续打卡 28 天。希望自己 可以坚持下去。
本周还是做了不少题目，具体如下
- Camelcase Matching
- Complete Binary Tree Inserter
- Arithmetic Slices
- Find Duplicate File in System
- Top K Frequent Elements
- Single Number III
- Smallest Subtree with all the Deepest Nodes
- Single Element in a Sorted Array
- Longest Common Subsequence
- Max Area of Island
- Minimum Cost Tree From Leaf Values
- Minimum Falling Path Sum
- Binary String With Substrings Representing 1 To N
在做题时发现细心很重要。就像现实中编程有些人会多提倡一些防御性编程，corner case 太多，我们没法 避免，但是事先需要细心分析 case。对于在面试中我们是白板写代码，这种情况更需要注意。
本周没有独立解决的问题是：
- Minimum Cost Tree From Leaf Values
这道题的其中一个解法是动态规划，自己的一个薄弱项就是动态规划。虽然知道动态规划就是把解拆分为子问题 的最优解，很多时候下面两个问题不知道从哪下手：
- 变量初始化
- 子问题拆解
Highlight
本周主要有两个比较有意思的点：
- 充分利用快速排序中的
partition思想 - C++ 中的
priority_queue的Compare函数
Partition
快速排序思想大致如下：
- 选中每一轮的 pivot 元素
- 遍历一遍，结果是：小于 pivot 位于左边，大于 pivot 位于右边
- 递归遍历
经典的算法在元素中有大量重复元素时效率会退化为 O(n^2)。一个优化方法如下：
假设数组为 nums, pivot 每次选为当前序列的 start
- 选中每一轮的 pivot, i = j = start, k = end (inclusive)
- partition
- nums[j] == nums[i] ++j
- nums[j] < nums[i]: swap(nums[i], nums[j]); ++i, ++j;
- nums[j] > nums[i]: swap(nums[j], nums[end]); –end;
- 递归调用：[start, i-1], [j, end]
本周如下题目可以这么解：
- Single Number III
- Single Element in a Sorted Array
Compare in priority_queue
经典的 priority_queue 我们是不用提供 Compare 类的。默认是最大堆。
priority<Type, vector<Type>, std::less<Type>>
当我们需要自定义优先级队列的比较函数时，有两种方法：
- 使用
class，定义其bool operator()(const Type& l, const Type& r) - 使用
lambda函数
// Return true means going down, leaving the top
class Compare {
bool operator()(const int& a, const int& b) {
return a < b;
}
};
priority_queue<int, vector<int>, Compare> pq
当我们的比较函数比较简单时，可以直接利用 lambda 函数：
auto func = [](const int& a, const int& b) {
return a < b;
};
priority_queue<int, vector<int>, std::function<bool(const int&, const int&)>> pq(func);
// a shorter version
priority_queue<int, vector<int>, decltype(func)> pq(func);
本文完。