Leetcode summary of 20190826-20190901

Posted by chunyang on September 1, 2019

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_queueCompare 函数

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

本文完。


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.