# Leetcode summary of 20190826-20190901

Posted by chunyang on September 1, 2019

### Summary

• 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

• Minimum Cost Tree From Leaf Values

• 变量初始化
• 子问题拆解

### Highlight

• 充分利用快速排序中的 partition 思想
• C++ 中的 priority_queueCompare 函数

#### Partition

• 选中每一轮的 pivot 元素
• 遍历一遍，结果是：小于 pivot 位于左边，大于 pivot 位于右边
• 递归遍历

• 选中每一轮的 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<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


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);