My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

cheapest-flights-within-k-stops(medium)

Shortest path problem with an additional dimension to denote steps: dis[i][j] means shortest path from src to i, passing j nodes. It is an O(mk) solution, where m is number of edges.
Another brilliant way is floyd + fast power. However, it takes O(n^3logk) time, which is much larger than former solution.

• Time complexity: O(n^3logk) or O(mk).
• Space complexity: O(n^2) or O(nk).

continuous-subarray-sum(easy)

Because the subarray should contains at least two elements, we should apply delay insertion to map.

• Time complexity: O(n).
• Space complexity: O(n).

design-hashmap(medium)

Self-designed map.

• Time complexity: O(1) if no conflicts.
• Space complexity: it depends.

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

4sum(medium)

We can apply the same method of enumerating the first 2 positions as 3sum to this problem and the time complexity will be O(n^3).
Sum of four numbers is the sum of two pairs. Thus, another way is to use a map to save the sums of all pairs of numbers and use a set to store corresponding pairs.
To avoid duplications, we can stipulate that numbers in the first pair should not greater than numbers in the second pair.
And to avoid cases like [-1, -1, -1, -1], sum=4, we should check if the combination of two pairs is available.

• Time complexity: O(n^2logn) if using set, O(n^2) if using unordered_set(need to customize hash function).
• Space complexity: O(n^2logn) if using set.

all-oone-data-structure(hard)

I have mentioned that: inc/dec by 1 --> linked list before.

• Time complexity: O(1).
• Space complexity: O(n).

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

3sum-with-multiplicity(easy)

Similar to 3sum problem. Use map to count the multiplicity.

• Time complexity: O(n^2).
• Space complexity: O(100).

circular-array-loop(medium)

Bad description. [-2, 1, -1, -2, -2] returns false.
To be a loop, it must never change direction. In other words, the elements of the loop must all have the same sign, either all positive or all negative. If it reverses direction it is an oscillation rather than a loop.
Solution in O(1) space:
Mark nums[x] as (sign * size) when visiting.
Mark nums[x] as (2 * sign * size) after visiting.

• Time complexity: O(n).
• Space complexity: O(1).

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

asteroid-collision(medium)

Monotonous stack: each negative asteroid will make positive asteroids with less size explode until it meet a larger positive asteroid.

• Time complexity: O(n).
• Space complexity: O(n).

design-tic-tac-toe(easy)

There are only n + n + 2 ways to win the tic tac toe: n rows, n columns, and 2 diagonals.

• Time complexity: O(n).
• Space complexity: O(n).

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

add-digits(easy)

• Time complexity: It is hard to tell, I think it should be O(num_of_digits).
• Space complexity: O(1).

add-two-numbers-ii(medium)

It is easy if we can modify the structure of the linked lists: we can reverse and add these two linked lists and then reverse back.
Without changing the structure, we should first align these two linked lists and then concatenate the remaining part.
A trick is to ignore the carry numbers when adding two linked list and to handle carry numbers after concatenation.

• Time complexity: O(n).
• Space complexity: O(n).

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

backspace-string-compare(easy)

Stack.

binary-tree-right-side-view(medium)

DFS. First, compute the depth of all subtrees. Second, for each subtree, decide which layers of its left subtree and its right subtree should be displayed.

clone-graph(easy)

It will be easy if we can use map to check if we have visited a node.

convert-binary-search-tree-to-sorted-doubly-linked-list(medium)

Convert the tree to doubly linked list recursively.

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

exclusive-time-of-functions(medium)

DFS of partitions. Be clear about the return value you defined.

flatten-nested-list-iterator(hard)

Empty nested array makes it much more complicated because you could find no value when you go into the deeper dimension and then you should go back to shallower dimension.
Another key point is that NestedInteger and vector<NestedInteger> can mess us up.

k-empty-slots(medium)

It is quite a typical problem of reverse thinking.
We cannot find and insert a node to a linked list in O(1) time using common thinking. However, use reverse thinking, we can do it.

multiply-strings(medium)

High-precision multiplication. Do it as how we calculate the multiplication manually.

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

3sum-closest(medium)

The same as the two pointers method of 3-sum.

add-binary(easy)

Same mechanism as high-precision calculation.

basic-calculator(hard)

It is a quite typical problem using two stacks. However, each time I tried to solve this problem, I cannot get it accepted at my first submission.
A trick to simplify the implementation is to define the priority of operators.
Another trick is how to handle negative numbers. It can be simplify our code if we combine the - with the following number rather than regard it as a operator.

1
2
3
4

wt['+'] = wt['-'] = 1;
wt['*'] = wt['/'] = 2;
wt['('] = -1;
wt[')'] = 0;

consecutive-numbers-sum(easy)

Math: formula for sum of arithmetic progression.

My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

integer-to-english-words(medium)

Divide the number into different parts according to the commas of writing a number.
The most difficult part of the problem is various corner cases, such as when should we output Zero.

alien-dictionary(medium)

Most sort algorithms are based on comparison, so we can exploit lexicographical order by comparing two contiguous words. Then we can represent the relationship using graph and use topological sort to check if there is a loop in the graph.

jewels-and-stones(easy)

license-key-formatting(easy)

meeting-rooms-ii(medium)

As usual, sort the intervals by the start time. Use current rooms as possible as we can. When there is no room available, we should add a new room.
So, the problem is how to judge if there is an available room. At first, I tried to use set and binary search. Then, add current interval to the searched room. Sure it is correct. However, we can find the room which ends earliest and add current interval to this room. It is corret because the following intervals start later then current interval and all available rooms for current interval are also available for the following intervals. Thus, we can add current interval to any one of the
available rooms.

[Review]LeetCode Top 100 Liked Questions(1)

所有代码可以在github上下载：https://github.com/proverbs/LTC
以下难易度评级为个人评级，非官方评级
个人认为比较有代表性的题目，标题将加粗

Hexo部署与备份

安装

参考官网教程

重要插件

• hexo-admin，管理本地post
• hexo-deployer-git，使用git进行部署

部署与备份

• hexo_gen_deploy文件夹（origin：proverbs.github.io仓库）：负责生成+部署
• hexo_backup文件夹（origin：HexoBackup仓库）：负责备份，其中备份脚本为：backup.sh（放在hexo_backup文件夹中）

DeepID学习笔记

参考文献

• Deep Learning Face Representation from Predicting 10,000 Classes（DeepID1）
• Deep Learning Face Representation by Joint Identification-Verification（DeepID2）
• Deeply learned face representations are sparse, selective, and robust（DeepID2+）
• DeepID3: Face Recognition with Very Deep Neural Networks（DeepID3）

DeepID1

0. Abstract

• 目标是提取Deep hidden IDentity features(DeepID)，这是在神经网络较高的一层所表示的特征，论文利用DeepID层提取的特征进行进行face verification（给两张人脸，判断是不是一个人）

1. Introduction

• 一般的，神经网络是使用二值verification信号（是或否）作为监督信号训练网络。但是本文使用identification信号（多分类，类别达10000）作为监督信号提取个体特征
• 模型的思想大概是：**将一张人脸切分成多个patch，然后每个patch训练一个网络产生多个网络。然后将多个网络的特征压缩到160维，作为整个人的特征。**具体的做法将在后面部分详述。
• 这160维的特征是high-level的（一般非深度学习提取的特征属于low-level的，如LBP），可以使用Joint Bayesian（联合贝叶斯）和NN（神经网络）等任意分类器对特征进行分类。后文也将给出联合贝叶斯和神经网络的比较
• 这种模型对于weakly aligned faces也可以达到很高的verification正确率

ResNet学习笔记

相关论文

• Deep Residual Learning for Image Recognition
• Identity Mappings in Deep Residual Networks

ResNet基础

1.Abstract

• 显示地使用了残差函数作为训练目标
• 残差函数易于优化；增加深度网络准确率更高

2.Introduction

• 问题1：近来，有很多很深的神经网络模型取得了很好的效果。但是，单纯的增加层数就能训练出更好的网络吗？
• 增加层数会遇到非常烦人的问题：梯度消失、梯度下降。解决方法是：初始化正则化、正则化层
• 问题2：烦人的问题解决了，但是实验证明，当深度增加时，训练效果反而更差，而这个更差的效果并不是因为过拟合造成的。这就表示深层的网络并不是那么好优化的。
• 作者提出了一种优化深层网络的方案：deep residual learning framework。一般的网络模型输入与输出本质上是一种函数映射关系，即$H(\vec{x})$ 。我们训练权重就是为了逼近函数$H(\vec{x})$ 。而作者提出训练权重去逼近残差函数$F(\vec{x})-\vec{x}$ ，并提出假设：这种残差函数更容易逼近。
• deep residual learning framework的构块见Figure 2。右边跨越层的连接称为shortcut connect。当$F(\vec{x})$ 和 $\vec{x}$ 维度相同时，网络不加入新的参数；维度不同时只会增加一个线性映射带来的参数。

【算法】字符串：后缀自动机（SAM）

引言

首先，你需要知道什么是自动机。
通俗讲，就是状态转移图，可以接受字符串的所有后缀。
后缀自动机，是一个最简的确定状态自动机。
当然，从使用的角度考虑，管它什么机，知道能从中找到所有后缀、左右子串，有很多很吊的性质就行了。

SAM

准备

SAM我确实理解了很久，而且理解还不够，还需要看到SAM的实质。
看清实质需要在理解的基础上不断应用取探索，所以，现在我们先详细谈一谈如何理解这个吊炸天的SAM。
首先，请确保你看过clj的ppt讲稿（其中有几处错误），至少要明白其中符号的定义，然后再看我写的东西。

【数据结构】树链剖分

引言

我在之前写过的一片关于树状数组的文章中有一道题，是利用dfs的方法将一棵树“拍扁”，称为一维数组，并将树中的查询和修改转换成一维数组中的查询与修改。

之所以可以使用dfs这种简单的方法是因为题目中的查询是针对子树的查询，dfs序列可以很好的应用。

但是如果查询是针对树中一条路径的话，那么dfs这种简单的序列就不能使用了。

面对这种问题，我们的解决方法是：树链剖分。

树链剖分

核心思想

树链剖分实际上是将树划分成很多的链，并将这些链合在一起，用线段树维护。所以，自然支持区间操作和单点操作。

所以，关键其实是树的划分方法。

划分的核心思想是轻重链划分，这种划分方法有一个非常好的性质：从根到某一点的路径上，不超过logn条轻边，且不超过logn条重路径。

而这就是树链剖分(logn)^2时间复杂度的保证。

【数据结构】函数式（可持久化）线段树

引言

函数式线段树也叫主席树，恩，原因嘛，不知道！

函数式线段树非常之吊，可以支持历史版本的查询。

关键是写起来很简单！

函数式线段树

核心思想

函数式线段树本质上很多棵线段树，即有很多的根节点。

这些线段树之间，通过共用一些子树以节省空间开销和时间开销。

更具体的说，在现在的基础上每增加一棵树的开销是logn。

函数式线段树需要满足一定的条件才能使用：维护的数据必须具有区间可减性。

更详细的讲解请看：http://www.cnblogs.com/zyf0163/p/4749042.html

【数据结构】RMQ

引言

RMQ是对静态区间的一种查询结构，一般用于求区间最大或最小值。

RMQ需要nlogn时间预处理，查询O(1)。

空间复杂度较高，为nlogn，所以有些题可能没法开下这么大的数组，这时候就可以考虑写线段树了。

RMQ

思想

RMQ思想很简单，就是倍增思想。

设f[i][j]表示[i,..,i+2^j-1]区间中的最大值，那么f[i][j]就等于max(f[i][j-1],f[i+2^(j-1)][j-1])。