LeetCode solutions

You have solved 482/559 problems. 主要追求两个目标:代码简短,时间空间复杂度低。

注记

4-sum

使用了multimap,时间复杂度\(O(n^2\log{n})\),得到所有答案后不需要去重操作。

合法的四元组有三类:

  • a<=b<c<=d,枚举cd,判断是否存在和为target-c-d的二元组
  • a<=b=c<=d,枚举bd,判断是否存在target-b-b-d
  • a=b=c<=d,枚举a,判断是否存在target-a-a-a

分别统计,小心实现可以保证不会产生相同的候选解,从而无需去重。

Alien Dictionary

对于每一对单词,可以确定去除最长公共前缀后的下一对字母的大小关系。两个单词的最长公共前缀等于夹在其中的(所有相邻单词对的最长公共前缀)的最小值。根据相邻单词对的信息即可推得所有任意单词对的信息。因此只需根据相邻单词对求出拓扑关系。

Basic Calculator

这是operator-precedence grammar,可以用operator-precedence parser计算。这类算法的一个特例是shunting-yard algorithm,适用于本题。 为了方便,我假设字串开头和末尾都有隐含的’’字符。使用的文法如下:

1
2
3
4
5
S := %x00 E %x00
E := E "+" E
E := E "-" E
E := ( E )
E := 1*DIGIT

参考http://www.scribd.com/doc/51358638/16/Operator-Precedence-Relations

在比较两个操作符时,区分左手边和右手边,左手边用于先处理的操作符,右手边为新来的操作符。使用左手边操作符的in-stack precedence(isp)和右手边操作符的incoming precedence(icp)进行比较。立即数可以看作icp很大,因此shift后可以立刻reduce。

Best Time to Buy and Sell Stock IV

线性解法。见2015-03-27-leetcode-best-time-to-buy-and-sell-stock-iv

Closest Binary Search Tree Value II

题意:求BST中与目标值最接近的k个节点。 BST中关键字小于等于目标值的所有节点可以用若干(不带右孩子的子树)表示。这些(不带右孩子的子树)在一条链上,可以用栈维护,得到用于计算前驱的的迭代器。求出目标值的k个前驱的时间复杂度为\(O(depth+k)\)。 类似地,大于目标值的所有节点也可以组织成一个迭代器。 两个迭代器做合并操作,获得前k个最接近的值。

Contains Duplicate III

\(t+1\)为单位把元素分桶,若一个桶内包含两个元素,则它们的差一定小于等于\(t\);差小于等于\(t\)的数对还可能出现在相邻两个桶之间。对于\(vector\)的各个元素,计算当前元素应放置的桶的编号\(j\),检查三个桶\(j-1,j,j+1\),判断之前\(k-1\)个元素里是否有差值小于等于\(t\)的元素。

Course Schedule

拓扑排序。入度减为0的顶点即成为候选,可以把入度向量组织成单链表,从而无需使用额外的队列或栈存储候选顶点,减小空间占用。

Dungeon Game

动态规划,对于每个格子记录从它出发顺利到达终点需要的最小血量。从\((m-1,n-1)\)递推至\((0,0)\)

注意对于每个格子其实有进和出两个状态:进入该格子时(未考虑当前格子影响);和离开该格子后(已考虑当前格子影响)。这两种方法都行,考虑到程序的结构可能有三部分:初始化边界条件、状态转移、根据状态表示答案,需要仔细斟酌以追求代码简短。这里两种方式并无明显代码长度差异。

Expression Add Operators

2015-10-16-leetcode-expression-add-operators

Find Minimum in Rotated Sorted Array

方法是二分,如果要写短可以采用下面的思路: 子数组中如果有相邻两个元素a[i]>a[i+1],则a[i+1]是整个数组的最小值。 若子数组a[i..j]满足a[i]>a[j],则存在i<=k<j使得a[k]>a[k+1]。 对于子数组a[l..h]判断a[l]>a[m]a[m]>a[h]是否有一个成立,成立则可以去除一半候选元素,不然a[h]>a[l]为一个逆序对。

Find Minimum in Rotated Sorted Array II

留意几个特殊情形:[1,0,1,1,1][1,1,1,0,1]

对于子数组a[l..h],令m=floor(l+h)/2(注意m可能等于l)。判断a[l]>a[m]a[m]>a[h]是否有一个成立,成立则可以去除一半候选元素。 若两个条件均不满足则a[l]<=a[m]<=a[h],若a[h]>a[l]则说明a[l]最小,否则a[l]=a[m]=a[h],可以把范围缩小为a[l+1..h-1]

另外一种方法是只判断a[m]与a[h]`的大小关系。

Find Peak Element

二分查找,把区间缩小为仍包含候选值的子区间。对于相邻两个元素\(a\)\(b\),若\(a>b\)\(a\)及左边部分存在peak,否则\(b\)及右边部分存在peak。不关心\(a\)\(b\)是否满足peak条件,将区间折半。

1
2
3
4
5
6
7
int l = 0, h = a.size();
while (l < h-1) {
int m = l+h >> 1;
if (a[m-1] > a[m]) h = m;
else l = m;
}
return l;

或者检查中间元素是否满足要求,可以提前退出循环。

1
2
3
4
5
6
7
8
int l = 0, h = a.size();
while (l < h-1) {
int m = l+h >> 1;
if (a[m-1] > a[m]) h = m;
else if (m+1 == h || a[m] > a[m+1]) l = h = m;
else l = m+1;
}
return l;

First Missing Possitive

空间复杂度\(O(1)\)

Fraction to Recurring Decimal

注意INT_MIN/(-1)会溢出。

Graph Valid Tree

\(n\)个节点的树的判定方式:

  • \(n-1\)条边且没有simple circle。可以用union-find algorithm判断。
  • 联通且无simple circle。可以用graph traversal。

Guess Number Higher or Lower II

动态规划优化,\(O(n^2)\)。见张昆玮的分析:http://artofproblemsolving.com/community/c296841h1273742s3_leetcode_guess_number_higher_or_lower_ii

Invert Binary Tree

选择一种binary tree traversal算法,节点访问改成交换左右孩子即可。 如果要O(1)空间的话,得借鉴Morris pre/in-order traversal的思路,该算法的核心是通过左子树最右节点的右孩子是否指向当前节点来判断当前节点被访问到的次数,从而决定当前应该进行的操作(探索左子树或访问当前节点)。但交换子树操作会弄乱左子树最右节点的位置,因此pre-order和in-order都行不通,但post-order可行。Morris post-order traversal(这个叫法也许不恰当)可以参考https://www.quora.com/What-is-a-good-way-to-implement-stackless-recursion-less-post-order-traversal-for-a-non-threaded-binary-tree-using-Morris-method的描述,pre/in-order的访问是针对一个节点进行的,但post-order则需要对当前节点左子树的右链进行,并且需要翻转两次以达到按post-order输出的效果。但这里只需要保证每个节点都被访问一次,不需要严格的post-order顺序,因此无需翻转操作。

Jump Game

空间复杂度\(O(1)\)

Jump Game II

使用output-restricted queue优化的动态规划,注意到动态规划值的单增性可以用类似BFS的方式,空间复杂度\(O(1)\)

Lexicographical Numbers

在trie中找1~n,存在迭代解法。

Linked List Cycle II

单链表找圈。Brent’s cycle detection algorithm或Floyd’s cycle detection algorithm。

如果只需要判断是否有圈,而不用指出圈的起点,可以使用pointer reversal。访问链表的过程中翻转链表,倘若访问到NULL,则说明无圈;若回到了起点,则说明有圈。如果有圈的话,算法执行完毕后,圈的方向会被反转,可以再执行一次翻转过程还原。下面是这个方法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
// return true if a cycle is detected
bool pointerReversal(ListNode *head) {
if (! head) return false;
ListNode *x = head->next, *y, *z = head;
while (x && x != head) {
y = x->next;
x->next = z;
z = x;
x = y;
}
return x == head;
}

Longest Palindromic Substring

线性时间求出以每个位置为中心的最长回文子串的Manacher’s algorithm。http://www.csie.ntnu.edu.tw/~u91029/Palindrome.html提供的描述感觉最清晰。但实现我更喜欢我从某本stringology书上看到的。

Majority Element

Boyer-Moore majority vote algorithm http://www.cs.utexas.edu/~moore/best-ideas/mjrty/,思路是每次找到两个不同的元素并丢弃,这样做不会丢失解。容器里只剩下一种元素时,它就是majority。

Majority Element II

Boyer-Moore majority vote algorithm的扩展,找出所有出现次数大于\(\lfloor N/K \rfloor\)的元素。方法是每次找出\(K\)个互不相同的元素丢掉,最后剩下的元素是候选解。时间复杂度\(O(N*K)\)

Maximum Gap

平均数原理,求出极差\(d\)后,根据桶大小\(\lceil \frac{d}{n-1}\rceil\)分成若干个桶,答案必为不同桶的两个元素之差。

Maximum Subarray

Kadane’s algorithm

Meeting Rooms II

题意中两条线段冲突当且仅当它们的公共部分长度大于0。 这是interval graph,所求的是chromatic number,interval graph包含与perfect graph,因此chromatic number等于maximum clique顶点数,即最大线段相交数,可以把所有端点排序计算。 或者按起始端点排序后用贪心算法:维护若干线段集合,按起始端点总从小到大考虑每个线段,任选一个不冲突的集合加入,若无不冲突的集合则自成一个新集合。最后,集合数即为答案。实现时,每个集合用最大右端点值表示,所有集合组织为一个小根binary heap,若当前考虑线段的起始点小于根则压入一个新元素,否则修改根的值。

Merge k Sorted Lists

Tournament sort,可以用priority_queue实现。

Min Stack

使用两个栈,原栈S存放各个元素。每当新元素小于等于当前最小值时,就把新元素复制一份压入另一个栈S'。弹出时,若元素在S'中出现,则也从S'中弹出。

另一种方法是记录新元素与当前最小值的差值,每个元素需要多记录1个bit。可惜C++会Memory Limit Exceeded,感觉不合理。

Minimum Window Substring

尺取法

Missing Number

从左到右考虑每个元素,若不等于它的位置则把它交换到正确的位置并重复此过程。

N Queen

bitmask存储列,正反斜线控制的格子。

Number of 1 Bits

求popcount。__builtin_popcount()或者网上查找各种bit twiddling hacks。

One Edit Distance

编辑距离为1有三种可能:S比T多一个字符、T比S多一个字符、S与T长度相同且有一个位置不同。除去最长公共前缀和最长公共后缀,三种可能的检查方式可以统一为判断较长的串长度是否为1。

Palindrome Partitioning

f[i][j] = calc(f[ii][jj] : i <= ii <= jj <= j)形式的动态规划可以采用如下计算方式。

1
2
3
4
for (int i = n; --i >= 0; )
for (int j = i; j < n; j++) {
// calc [i,j]
}

Palindrome Partitioning II

求原串的最少回文串划分。O(n^2)时间,可以优化到O(n)空间。

我没能找到比O(n^2)快的算法。相关的问题有检测一个串是否分割成k个回文串。k小于等于4时均有线性算法,参见Text Algorithms一书Theorem 8.17。k大于4时不确定。

Perfect Rectangle

使用unordered_map\(O(n)\)解法:判断除了四个极点,每个小矩形的角是否被两个或四个矩形共享。

或者判断所有小矩形面积和等于四个极点围成的矩形的面积,并且小矩形没有重叠(用sweep line判断)。

Perfect Squares

https://leetcode.com/discuss/57477/sqrt-applying-fermats-theorm-brahmagupta-fibonacci-identity

由Lagrange’s four-square theorem知答案为1~4,由Legendre’s three-square theorem检查答案是否为4。若小于4,则再\(O(\sqrt{n})\)尺取法检查是否是perfect square或能表示为两个perfect squares之和,若不是则答案为3。

另有期望\(O((\log n)^2)\)的算法,参见M. O. Rabin, J. O. Shallit, Randomized Algorithms in Number Theory, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256. doi:10.1002/cpa.3160390713

Reconstruct Itinerary

题目即lexicographically smallest Eulerian path。Eulerian path最简单的算法是Hierholzer’s algorithm,有向图中仅有一个顶点出度=入度+1,记为源;一个顶点入度=出度+1,记为汇。任求一条源到汇的路径,之后把各个圈合并到路径上即可。本题要求字典序最小,对Hierholzer’s algorithm稍加变形即可。

从源开始,贪心地选择序号最小的下一个顶点,删除这条边,重复此过程,即得到一条源到汇的路径。需要把圈添加到该路径上。若一个圈只包含路径上的一个顶点,那么在该顶点处添加圈即可。若一个圈包含路径上的多个顶点,那么应该把它放在离汇最近的顶点上,这样能保证字典序最小。

Recover Binary Search Tree

使用Morris in-order traversal找到邻接失序对。

如果交换的元素相邻,则有一个邻接失序对(如0 1 2 3 4 ->0 1 3 2 4),否则有两个邻接失序对(如0 1 2 3 4 5 -> 0 4 2 3 1 5)。

Remove Nth Node From End of List

http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions

使用pointers-to-pointers很多时候能简化实现。

Regular Expression Matching

P为模式串,T为文本, f[i][j]表示P的前i个字符能否匹配T的前j个字符。 根据f[i-1][*]计算f[i][*]。 这个方法也可以看作构建了精简表示的Thompson’s automaton,时间复杂度\(O(|P|\cdot |T|)\)

Remove Element

原地修改数组,我喜欢把这种操作称作deflate。

Remove Invalid Parentheses

最少移除个数很容易计算,把可以配对的左右括号全部抵消,剩余括号数即是(形如:)))...((()。难点在于输出所有不同答案,多数解法使用DFS枚举要删除哪些括号,枚举量大于答案个数。 有一个枚举量固定为答案个数的方法,找到残余串)))...(((中右括号与左括号的分割点。DFS分割点左半部分,保证到达残余串第\(i\)个右括号时,至少有\(i\)个右括号(原串的)被删除。分割点右半部分也如法炮制,两边合并即为答案。

Repeated DNA Sequences

可以用类似Rabin-Karp的rolling hash方法,求出所有长为10的子串的hash值,判断是否有重复。只有四个字符,长度为10,故可以使用polynomial hash code。 另外也可以用suffix tree/suffix array等方法,找longest common prefix大于等于10的两个后缀。注意不能重复输出字串。

Reverse Bits

Hacker’s Delight (2nd) 7.1 Reversing Bits and Bytes。

Rotate Array

经典的三次reverse,或者拆成gcd(k,n)个置换群循环右移一格。

Same Tree

类似于same fringe problem,可以试验generator、co-routine、lazy evaluation、continuation等。如果要O(1)的空间复杂度可以用Morris in-order traversal等方法。

Set Matrix Zeroes

\(O(1)\)空间复杂度。使用两个标志表示第0行或第0列是否需要清零,之后用第0行表示各列是否需要清零,第0列表示各行是否需要清零。

Search For a Range

设序列用区间表示为[begin,end)。使用C++ STL风格的lower_bound、upper_bound。有几点好处:

  • 循环内只有一次比较
  • 循环退出后两个指针相等,且落在[begin,end],都是迭代器的合法取值。某些binary search写法返回值可能为begin-1,某些容器不合法
  • [lower_bound(a[],x), upper_bound(a[],x)给出了元素x所在的子区间

Search Insert Position

C++ <algorithm>lower_bound

Serialize and Deserialize Binary Tree

把NULL视作叶子,则pre/in/post-order traversal可以用于编码。若使用Morris traversal则额外空间为\(O(1)\)。解码时使用类似Schorr-Waite graph marking algorithm的edge crawling技巧即可做到额外空间\(O(1)\)

Shortest Palindrome

找出原串的最长回文前缀,用Manacher’s algorithm求解,把剩下部分复制一份、翻转后、接到左边,就得到了最短的回文串。求最长回文前缀的另一种方法是把原串以及翻转用特殊字符隔开,用Morris-Pratt algorithm求border,该值即为最长回文前缀长度。

Single Number III

所有数的xor等于两个出现一次的数的xor,不妨设为k,则k & -k为二进制表示上某个为1的数位。根据这个数位把所有元素划分成两份,每份只有一个出现一次的数。

Smallest Good Base

\(n=1+k+k^2+\ldots+k^m\),由\(n>k^m\)\(k<n^{1/m}\),由\((1+k)^m>n\)\(k+1>n^{1/m}\),因此\(n^{1/m}-1<k<n^{1/m}\)。枚举\(m\)\(k\)唯一可能取值为\(floor(n^{1/m})\),判断是否成立。

Sort Colors

Dutch national flag problem。如果不要求000111222,允许111000222111,那么有交换次数更少的Bentley-McIlroy算法http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-flag-problem-3/

Sqrt(x)

Hacker’s Delight (2nd) 11.1.1。 牛顿迭代法。46340 = floor(sqrt(INT_MAX))

Scramble String

我用了\(O(n^3)\)的空间和\(O(n^4)\)的时间,应该有更好的算法。但查阅了一些文献还没有找到。

Sort List

我用了较麻烦的natural merge sort。Quicksort实现会简单很多。

Strobogrammatic Number III

定义一个函数,用于计算小于给定数的strobogrammatic number个数,则用减法即可得到题目所求。下面考虑如何计算这个函数。 小于给定数high的strobogrammatic number分为两类:

  • 位数不够的,可看作有若干前导0。容易求得。
  • 位数相同。可以枚举与high的公共前缀的长度,再计算下一个数位小于high中对应数位的strobogrammatic number个数。由于位数为\(n\)的strobogrammatic number只有\(ceil(n/2)\)个数位是独立的,枚举的公共前缀长度得小于\(\lceil n/2\rfrac\)

Sudoku Solver

转化为exact cover problem,使用dancing links + Algorithm X求解。

Trapping Rain Water

两个指针夹逼,空间\(O(1)\)

Unique Binary Search Trees II

类似动态规划的思想,子树可以复用。

Wiggle Sort

从左到右考虑每一对相邻元素,如果不满足大小关系则交换,交换不会影响之前一对元素的大小关系。

Word Ladder

基本方法是BFS或bidirectional BFS,相邻关系的确定有两种思路:枚举所有其他顶点判断是否相邻、枚举顶点的变异判断是否为顶点。对于第一种思路,还可以利用一个技巧:把所有字串都分为左右两半,若两个字串hamming distance为1,则左半部分相同或右半部分相同。

Verify Preorder Sequence in Binary Search Tree

对于前序序列中的递减连续段,它们形成了BST的某个左孩子链。

Maximal Rectangle

秋叶拓哉(iwi)、岩田阳一(wata)和北川宜稔(kita_masa)所著,巫泽俊(watashi)、庄俊元(navi)和李津羽(itsuhane)翻译的《挑战程序设计竞赛》

逐行扫描棋盘,对于每一行\(i\)记录三个值:

  • \(h_j\)表示第\(j\)列上方连续为1的行数:h[j] = a[i][j] == 0 ? 0 : h[j]+1;
  • \(a_{i,j}=1\),令\(l_j\)\(min(k : h_{k+1\ldots j}\ge h_j)\);若\(a_{i,j}=0\)则设为\(j\)
  • \(a_{i,j}=1\),令\(r_j\)\(max(k : h_{j\ldots k-1}\ge h_j)\);若\(a_{i,j}=0\)则设为\(j\)

\(l\)的计算方式是:

1
2
3
4
5
6
7
if a[i][j] == 0:
l[j] = j
elif h[j] == 1:
l[j] = j-(a[i][j]及左边连续的1的个数)+1
else
# 下式中右边的l[j]是第i-1行计算得到的l[j]
l[j] = min(l[j], j-(a[i][j]及左边连续的1的个数)+1)

\(r\)的计算类似。对于每一列\(j\)\((r_j-l_j+1)\times h_j\)是一个候选解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
class Solution {
public:
int maximalRectangle(vector<vector<char> > &a) {
if (a.empty()) return 0;
int m = a.size(), n = a[0].size(), ans = 0;
vector<int> h(n), l(n), r(n, n-1);
REP(i, m) {
int ll = -1;
REP(j, n) {
h[j] = a[i][j] == '1' ? h[j]+1 : 0;
if (a[i][j] == '0') ll = j;
l[j] = h[j] ? max(h[j] == 1 ? 0 : l[j], ll+1) : j;
}
int rr = n;
ROF(j, 0, n) {
if (a[i][j] == '0') rr = j;
r[j] = h[j] ? min(h[j] == 1 ? n-1 : r[j], rr-1) : j;
ans = max(ans, (r[j]-l[j]+1)*h[j]);
}
}
return ans;
}
};

潘宇超 2008

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
class Solution {
public:
int maximalRectangle(vector<vector<char> > &a) {
if (a.empty()) return 0;
int m = a.size(), n = a[0].size(), ans = 0;
vector<int> h(n), l(n), r(n, n-1);
REP(i, m) {
REP(j, n) {
h[j] = a[i][j] == '1' ? h[j]+1 : 0;
l[j] = j;
while (l[j] && h[l[j]-1] >= h[j])
l[j] = l[l[j]-1];
}
ROF(j, 0, n) {
r[j] = j;
while (r[j]+1 < n && h[j] <= h[r[j]+1])
r[j] = r[r[j]+1];
ans = max(ans, (r[j]-l[j]+1)*h[j]);
}
}
return ans;
}
};

ACRush某TopCoder SRM

逐行扫描棋盘,对于每一行记录\(h_j\):第\(j\)列上方连续为1的行数。

对于每一行\(i\),从大到小排序\(h\),并计算候选解:

1
2
3
4
x = [0,0,...,0]
foreach j, h[j]: # 从大到小遍历h[j]
x[j] = 1
ans = max(ans, (max(k : x[j..k]都为1) - min(k : x[k..j]都为1)) * h[j])

上面伪代码可以在\(O(n)\)时间内求出。方法是把\(x\)中设置为1的元素看成若干集合,相邻元素在同一个集合中。每次把某个\(x\)中元素设为1可以看成新建了一个集合,若左边或右边的集合存在则合并。

不相交集合可以用union-find算法,但针对这种特殊情形存在\(O(n)\)的算法:每个集合(即某个1的连续段)左端和右端互指,其他元素的指针任意。新建集合时若左边或右边的集合存在,则更新它们两端的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)
class Solution {
public:
int maximalRectangle(vector<vector<char> > &a) {
if (a.empty()) return 0;
int m = a.size(), n = a[0].size(), ans = 0;
vector<int> h(n), p(n), b(m+1), s(n);
REP(i, m) {
REP(j, n)
h[j] = a[i][j] == '1' ? h[j]+1 : 0;
fill(b.begin(), b.end(), 0);
REP(j, n)
b[h[j]]++;
REP1(j, m)
b[j] += b[j-1];
REP(j, n)
s[--b[h[j]]] = j;
fill(p.begin(), p.end(), -1);
ROF(j, 0, n) {
int x = s[j], l = x, r = x;
p[x] = x;
if (x && p[x-1] != -1) {
l = p[x-1];
p[l] = x;
p[x] = l;
}
if (x+1 < n && p[x+1] != -1) {
l = p[x];
r = p[x+1];
p[l] = r;
p[r] = l;
}
ans = max(ans, (r-l+1)*h[x]);
}
}
return ans;
}
};

栈维护histogram

逐行扫描棋盘,对于每一行记录\(h_j\):第\(j\)列上方连续为1的行数。

对于每一行\(i\),维护一个以\(h\)值为元素的栈,满足从栈底到栈顶\(h\)值递增。从左到右枚举各列\(j\),在插入\(h_j\)前维持栈性质,弹出元素后栈顶代表\(j\)往左能“看到”的最远位置,插入\(h_j\)

其他方法 

枚举两列,求出夹在两列间的最大1子矩形。\(O(n^3)\)

\(s_{i,j}\)表示以原矩形最上角和\((i,j)\)两个端点的矩形内1的数目,枚举所有子矩形\(((i,j),(ii,jj))\),用\(s_{ii,jj}-s_{ii,j-1}-s_{i-1,jj}+s_{i-1,j-1}\)求出这个子矩形内1的数目,判断是否合法。\(O(n^4)\)

把0看成障碍点,求不包含障碍点的最大子矩形。 把障碍点按横座标排序。枚举障碍点作为候选子矩形的左端,向右扫描各个障碍点,维护纵座标和枚举点最近的上下个一个障碍点。枚举点、扫描线和上下障碍点确定了候选子矩形的边界。 若0的数目为,\(O(m^2)\),最坏\(O(n^4)\)

代码索引

# Title Solution
635 Design Log Storage System design-log-storage-system.cc
634 Find the Derangement of An Array find-the-derangement-of-an-array.cc
633 Sum of Square Numbers sum-of-square-numbers.cc
631 Design Excel Sum Formula design-excel-sum-formula.cc
630 Course Schedule III course-schedule-iii.cc
629 K Inverse Pairs Array k-inverse-pairs-array.cc
628 Maximum Product of Three Numbers maximum-product-of-three-numbers.cc
617 Merge Two Binary Trees merge-two-binary-trees.cc
616 Add Bold Tag in String add-bold-tag-in-string.cc
611 Valid Triangle Number valid-triangle-number.cc
604 Design Compressed String Iterator design-compressed-string-iterator.cc
600 Non-negative Integers without Consecutive Ones non-negative-integers-without-consecutive-ones.cc
599 Minimum Index Sum of Two Lists minimum-index-sum-of-two-lists.cc
598 Range Addition II range-addition-ii.cc
594 Longest Harmonious Subsequence longest-harmonious-subsequence.cc
593 Valid Square valid-square.cc
592 Fraction Addition and Subtraction fraction-addition-and-subtraction.cc
588 Design In-Memory File System design-in-memory-file-system.cc
587 Erect the Fence erect-the-fence.cc
583 Delete Operation for Two Strings delete-operation-for-two-strings.cc
582 Kill Process kill-process.cc
581 Shortest Unsorted Continuous Subarray shortest-unsorted-continuous-subarray.cc
575 Distribute Candies distribute-candies.cc
565 Array Nesting array-nesting.cc
556 Next Greater Element III next-greater-element-iii.cc
553 Optimal Division optimal-division.cc
552 Student Attendance Record II student-attendance-record-ii.cc
533 Lonely Pixel II lonely-pixel-ii.cc
531 Lonely Pixel I lonely-pixel-i.cc
514 Freedom Trail freedom-trail.cc
508 Most Frequent Subtree Sum most-frequent-subtree-sum.cc
507 Perfect Number perfect-number.cc
504 Base 7 base-7.cc
502 IPO ipo.cc
501 Find Mode in Binary Search Tree find-mode-in-binary-search-tree.cc
500 Keyboard Row keyboard-row.cc
495 Teemo Attacking teemo-attacking.cc
494 Target Sum target-sum.cc
491 Increasing Subsequences increasing-subsequences.cc
490 The Maze the-maze.cc
485 Max Consecutive Ones max-consecutive-ones.cc
483 Smallest Good Base smallest-good-base.cc
482 License Key Formatting license-key-formatting.cc
481 Magical String magical-string.cc
480 Sliding Window Median sliding-window-median.cc
477 Total Hamming Distance total-hamming-distance.cc
476 Number Complement number-complement.cc
475 Heaters heaters.cc
474 Ones and Zeroes ones-and-zeroes.cc
473 Matchsticks to Square matchsticks-to-square.cc
472 Concatenated Words concatenated-words.cc
469 Convex Polygon convex-polygon.cc
468 Validate IP Address validate-ip-address.cc
467 Unique Substrings in Wraparound String unique-substrings-in-wraparound-string.cc
466 Count The Repetitions count-the-repetitions.cc
465 Optimal Account Balancing optimal-account-balancing.cc
464 Can I Win can-i-win.cc
463 Island Perimeter island-perimeter.cc
462 Minimum Moves to Equal Array Elements II minimum-moves-to-equal-array-elements-ii.cc
461 Hamming Distance hamming-distance.cc
459 Repeated Substring Pattern repeated-substring-pattern.cc
456 132 Pattern 132-pattern.cc
455 Assign Cookies assign-cookies.cc
454 4Sum II 4sum-ii.cc
453 Minimum Moves to Equal Array Elements minimum-moves-to-equal-array-elements.cc
452 Minimum Number of Arrows to Burst Balloons minimum-number-of-arrows-to-burst-balloons.cc
447 Number of Boomerangs number-of-boomerangs.cc
446 Arithmetic Slices II - Subsequence arithmetic-slices-ii-subsequence.cc
444 Sequence Reconstruction sequence-reconstruction.cc
441 Arranging Coins arranging-coins.cc
440 K-th Smallest in Lexicographical Order k-th-smallest-in-lexicographical-order.cc
439 Ternary Expression Parser ternary-expression-parser.cc
438 Find All Anagrams in a String find-all-anagrams-in-a-string.cc
437 Path Sum III path-sum-iii.cc
436 Find Right Interval find-right-interval.cc
435 Non-overlapping Intervals non-overlapping-intervals.cc
434 Number of Segments in a String number-of-segments-in-a-string.cc
432 All O`one Data Structure all-oone-data-structure.cc
424 Longest Repeating Character Replacement longest-repeating-character-replacement.cc
423 Reconstruct Original Digits from English reconstruct-original-digits-from-english.cc
422 Valid Word Square valid-word-square.cc
421 Maximum XOR of Two Numbers in an Array maximum-xor-of-two-numbers-in-an-array.cc
420 Strong Password Checker strong-password-checker.cc
419 Battleships in a Board battleships-in-a-board.cc
417 Pacific Atlantic Water Flow pacific-atlantic-water-flow.cc
416 Partition Equal Subset Sum partition-equal-subset-sum.cc
415 Add Strings add-strings.cc
414 Third Maximum Number third-maximum-number.cc
413 Arithmetic Slices arithmetic-slices.cc
412 Fizz Buzz fizz-buzz.cc
410 Split Array Largest Sum split-array-largest-sum.cc
409 Longest Palindrome longest-palindrome.cc
408 Valid Word Abbreviation valid-word-abbreviation.cc
407 Trapping Rain Water II trapping-rain-water-ii.cc
406 Queue Reconstruction by Height queue-reconstruction-by-height.cc
405 Convert a Number to Hexadecimal convert-a-number-to-hexadecimal.cc
404 Sum of Left Leaves sum-of-left-leaves.cc
403 Frog Jump frog-jump.cc
402 Remove K Digits remove-k-digits.cc
401 Binary Watch binary-watch.cc
400 Nth Digit nth-digit.cc
399 Evaluate Division evaluate-division.cc
398 Random Pick Index random-pick-index.cc
397 Integer Replacement integer-replacement.cc
396 Rotate Function rotate-function.cc
395 Longest Substring with At Least K Repeating Characters longest-substring-with-at-least-k-repeating-characters.cc
394 Decode String decode-string.cc
393 UTF-8 Validation utf-8-validation.cc
392 Is Subsequence is-subsequence.cc
391 Perfect Rectangle perfect-rectangle.cc
390 Elimination Game elimination-game.cc
389 Find the Difference find-the-difference.cc
388 Longest Absolute File Path longest-absolute-file-path.cc
387 First Unique Character in a String first-unique-character-in-a-string.cc
386 Lexicographical Numbers lexicographical-numbers.cc
385 Mini Parser mini-parser.cc
384 Shuffle an Array shuffle-an-array.cc
383 Ransom Note ransom-note.cc
382 Linked List Random Node linked-list-random-node.cc
381 Insert Delete GetRandom O(1) - Duplicates allowed insert-delete-getrandom-o1-duplicates-allowed.cc
380 Insert Delete GetRandom O(1) insert-delete-getrandom-o1.cc
379 Design Phone Directory design-phone-directory.cc
378 Kth Smallest Element in a Sorted Matrix kth-smallest-element-in-a-sorted-matrix.cc
377 Combination Sum IV combination-sum-iv.cc
376 Wiggle Subsequence wiggle-subsequence.cc
375 Guess Number Higher or Lower II guess-number-higher-or-lower-ii.cc
374 Guess Number Higher or Lower guess-number-higher-or-lower.cc
373 Find K Pairs with Smallest Sums find-k-pairs-with-smallest-sums.cc
372 Super Pow super-pow.cc
371 Sum of Two Integers sum-of-two-integers.cc
370 Range Addition range-addition.cc
369 Plus One Linked List plus-one-linked-list.cc
368 Largest Divisible Subset largest-divisible-subset.cc
367 Valid Perfect Square valid-perfect-square.cc
366 Find Leaves of Binary Tree find-leaves-of-binary-tree.cc
365 Water and Jug Problem water-and-jug-problem.cc
364 Nested List Weight Sum II nested-list-weight-sum-ii.cc
363 Max Sum of Rectangle No Larger Than K max-sum-of-sub-matrix-no-larger-than-k.cc
362 Design Hit Counter design-hit-counter.cc
361 Bomb Enemy bomb-enemy.cc
360 Sort Transformed Array sort-transformed-array.cc
359 Logger Rate Limiter logger-rate-limiter.cc
358 Rearrange String k Distance Apart rearrange-string-k-distance-apart.cc
357 Count Numbers with Unique Digits count-numbers-with-unique-digits.cc
356 Line Reflection line-reflection.cc
355 Design Twitter design-twitter.cc
354 Russian Doll Envelopes russian-doll-envelopes.cc
353 Design Snake Game design-snake-game.cc
352 Data Stream as Disjoint Intervals data-stream-as-disjoint-intervals.cc
351 Android Unlock Patterns android-unlock-patterns.cc
350 Intersection of Two Arrays II intersection-of-two-arrays-ii.cc
349 Intersection of Two Arrays intersection-of-two-arrays.cc
348 Design Tic-Tac-Toe design-tic-tac-toe.cc
347 Top K Frequent Elements top-k-frequent-elements.cc
346 Moving Average from Data Stream moving-average-from-data-stream.cc
345 Reverse Vowels of a String reverse-vowels-of-a-string.cc
344 Reverse String reverse-string.cc
343 Integer Break integer-break.cc
342 Power of Four power-of-four.cc
341 Flatten Nested List Iterator flatten-nested-list-iterator.cc
340 Longest Substring with At Most K Distinct Characters longest-substring-with-at-most-k-distinct-characters.cc
339 Nested List Weight Sum nested-list-weight-sum.cc
338 Counting Bits counting-bits.cc
337 House Robber III house-robber-iii.cc
336 Palindrome Pairs palindrome-pairs.cc
335 Self Crossing self-crossing.cc
334 Increasing Triplet Subsequence increasing-triplet-subsequence.cc
333 Largest BST Subtree largest-bst-subtree.cc
332 Reconstruct Itinerary reconstruct-itinerary.cc
331 Verify Preorder Serialization of a Binary Tree verify-preorder-serialization-of-a-binary-tree.cc
330 Patching Array patching-array.cc
329 Longest Increasing Path in a Matrix longest-increasing-path-in-a-matrix.cc
328 Odd Even Linked List odd-even-linked-list.cc
327 Count of Range Sum count-of-range-sum.cc
326 Power of Three power-of-three.cc
325 Maximum Size Subarray Sum Equals k maximum-size-subarray-sum-equals-k.cc
324 Wiggle Sort II wiggle-sort-ii.cc
323 Number of Connected Components in an Undirected Graph number-of-connected-components-in-an-undirected-graph.cc
322 Coin Change coin-change.cc
321 Create Maximum Number create-maximum-number.cc
320 Generalized Abbreviation generalized-abbreviation.cc
319 Bulb Switcher bulb-switcher.cc
318 Maximum Product of Word Lengths maximum-product-of-word-lengths.cc
317 Shortest Distance from All Buildings shortest-distance-from-all-buildings.cc
316 Remove Duplicate Letters remove-duplicate-letters.cc
315 Count of Smaller Numbers After Self count-of-smaller-numbers-after-self.cc
314 Binary Tree Vertical Order Traversal binary-tree-vertical-order-traversal.cc
313 Super Ugly Number super-ugly-number.cc
312 Burst Balloons burst-balloons.cc
311 Sparse Matrix Multiplication sparse-matrix-multiplication.cc
310 Minimum Height Trees minimum-height-trees.cc
309 Best Time to Buy and Sell Stock with Cooldown best-time-to-buy-and-sell-stock-with-cooldown.cc
308 Range Sum Query 2D - Mutable range-sum-query-2d-mutable.cc
307 Range Sum Query - Mutable range-sum-query-mutable.cc
306 Additive Number additive-number.cc
305 Number of Islands II number-of-islands-ii.cc
304 Range Sum Query 2D - Immutable range-sum-query-2d-immutable.cc
303 Range Sum Query - Immutable range-sum-query-immutable.cc
302 Smallest Rectangle Enclosing Black Pixels smallest-rectangle-enclosing-black-pixels.cc
301 Remove Invalid Parentheses remove-invalid-parentheses.cc
300 Longest Increasing Subsequence longest-increasing-subsequence.cc
299 Bulls and Cows bulls-and-cows.cc
298 Binary Tree Longest Consecutive Sequence binary-tree-longest-consecutive-sequence.cc
297 Serialize and Deserialize Binary Tree serialize-and-deserialize-binary-tree.cc
296 Best Meeting Point best-meeting-point.cc
295 Find Median from Data Stream find-median-from-data-stream.cc
294 Flip Game II flip-game-ii.cc
293 Flip Game flip-game.cc
292 Nim Game nim-game.cc
291 Word Pattern II word-pattern-ii.cc
290 Word Pattern word-pattern.cc
289 Game of Life game-of-life.cc
288 Unique Word Abbreviation unique-word-abbreviation.cc
287 Find the Duplicate Number find-the-duplicate-number.cc
286 Walls and Gates walls-and-gates.cc
285 Inorder Successor in BST inorder-successor-in-bst.cc
284 Peeking Iterator peeking-iterator.cc
283 Move Zeroes move-zeroes.cc
282 Expression Add Operators expression-add-operators.cc
281 Zigzag Iterator zigzag-iterator.cc
280 Wiggle Sort wiggle-sort.cc
279 Perfect Squares perfect-squares.cc
278 First Bad Version first-bad-version.cc
277 Find the Celebrity find-the-celebrity.cc
276 Paint Fence paint-fence.cc
275 H-Index II h-index-ii.cc
274 H-Index h-index.cc
273 Integer to English Words integer-to-english-words.cc
272 Closest Binary Search Tree Value II closest-binary-search-tree-value-ii.cc
271 Encode and Decode Strings encode-and-decode-strings.cc
270 Closest Binary Search Tree Value closest-binary-search-tree-value.cc
269 Alien Dictionary alien-dictionary.cc
268 Missing Number missing-number.cc
267 Palindrome Permutation II palindrome-permutation-ii.cc
266 Palindrome Permutation palindrome-permutation.cc
265 Paint House II paint-house-ii.cc
264 Ugly Number II ugly-number-ii.cc
263 Ugly Number ugly-number.cc
261 Graph Valid Tree graph-valid-tree.cc
260 Single Number III single-number-iii.cc
259 3Sum Smaller 3sum-smaller.cc
258 Add Digits add-digits.cc
257 Binary Tree Paths binary-tree-paths.cc
256 Paint House paint-house.cc
255 Verify Preorder Sequence in Binary Search Tree verify-preorder-sequence-in-binary-search-tree.cc
254 Factor Combinations factor-combinations.cc
253 Meeting Rooms II meeting-rooms-ii.cc
252 Meeting Rooms meeting-rooms.cc
251 Flatten 2D Vector flatten-2d-vector.cc
250 Count Univalue Subtrees count-univalue-subtrees.cc
249 Group Shifted Strings group-shifted-strings.cc
248 Strobogrammatic Number III strobogrammatic-number-iii.cc
247 Strobogrammatic Number II strobogrammatic-number-ii.cc
246 Strobogrammatic Number strobogrammatic-number.cc
245 Shortest Word Distance III shortest-word-distance-iii.cc
244 Shortest Word Distance II shortest-word-distance-ii.cc
243 Shortest Word Distance shortest-word-distance.cc
242 Valid Anagram valid-anagram.cc
241 Different Ways to Add Parentheses different-ways-to-add-parentheses.cc
240 Search a 2D Matrix II search-a-2d-matrix-ii.cc
239 Sliding Window Maximum sliding-window-maximum.cc
238 Product of Array Except Self product-of-array-except-self.cc
237 Delete Node in a Linked List delete-node-in-a-linked-list.cc
236 Lowest Common Ancestor of a Binary Tree lowest-common-ancestor-of-a-binary-tree.cc
235 Lowest Common Ancestor of a Binary Search Tree lowest-common-ancestor-of-a-binary-search-tree.cc
234 Palindrome Linked List palindrome-linked-list.cc
233 Number of Digit One number-of-digit-one.cc
232 Implement Queue using Stacks implement-queue-using-stacks.cc
231 Power of Two power-of-two.cc
230 Kth Smallest Element in a BST kth-smallest-element-in-a-bst.cc
229 Majority Element II majority-element-ii.cc
228 Summary Ranges summary-ranges.cc
227 Basic Calculator II basic-calculator-ii.cc
226 Invert Binary Tree invert-binary-tree.cc
225 Implement Stack using Queues implement-stack-using-queues.cc
224 Basic Calculator basic-calculator.cc
223 Rectangle Area rectangle-area.cc
222 Count Complete Tree Nodes count-complete-tree-nodes.cc
221 Maximal Square maximal-square.cc
220 Contains Duplicate III contains-duplicate-iii.cc
219 Contains Duplicate II contains-duplicate-ii.cc
218 The Skyline Problem the-skyline-problem.cc
217 Contains Duplicate contains-duplicate.cc
216 Combination Sum III combination-sum-iii.cc
215 Kth Largest Element in an Array kth-largest-element-in-an-array.cc
214 Shortest Palindrome shortest-palindrome.cc
213 House Robber II house-robber-ii.cc
212 Word Search II word-search-ii.cc
211 Add and Search Word - Data structure design add-and-search-word-data-structure-design.cc
210 Course Schedule II course-schedule-ii.cc
209 Minimum Size Subarray Sum minimum-size-subarray-sum.cc
208 Implement Trie (Prefix Tree) implement-trie-prefix-tree.cc
207 Course Schedule course-schedule.cc
206 Reverse Linked List reverse-linked-list.cc
205 Isomorphic Strings isomorphic-strings.cc
204 Count Primes count-primes.cc
203 Remove Linked List Elements remove-linked-list-elements.cc
202 Happy Number happy-number.cc
201 Bitwise AND of Numbers Range bitwise-and-of-numbers-range.cc
200 Number of Islands number-of-islands.cc
199 Binary Tree Right Side View binary-tree-right-side-view.cc
198 House Robber house-robber.cc
191 Number of 1 Bits number-of-1-bits.cc
190 Reverse Bits reverse-bits.cc
189 Rotate Array rotate-array.cc
188 Best Time to Buy and Sell Stock IV best-time-to-buy-and-sell-stock-iv.cc
187 Repeated DNA Sequences repeated-dna-sequences.cc
186 Reverse Words in a String II reverse-words-in-a-string-ii.cc
179 Largest Number largest-number.cc
174 Dungeon Game dungeon-game.cc
173 Binary Search Tree Iterator binary-search-tree-iterator.cc
172 Factorial Trailing Zeroes factorial-trailing-zeroes.cc
171 Excel Sheet Column Number excel-sheet-column-number.cc
170 Two Sum III - Data structure design two-sum-iii-data-structure-design.cc
169 Majority Element majority-element.cc
168 Excel Sheet Column Title excel-sheet-column-title.cc
167 Two Sum II - Input array is sorted two-sum-ii-input-array-is-sorted.cc
166 Fraction to Recurring Decimal fraction-to-recurring-decimal.cc
165 Compare Version Numbers compare-version-numbers.cc
164 Maximum Gap maximum-gap.cc
163 Missing Ranges missing-ranges.cc
162 Find Peak Element find-peak-element.cc
161 One Edit Distance one-edit-distance.cc
160 Intersection of Two Linked Lists intersection-of-two-linked-lists.cc
159 Longest Substring with At Most Two Distinct Characters longest-substring-with-at-most-two-distinct-characters.cc
158 Read N Characters Given Read4 II - Call multiple times read-n-characters-given-read4-ii-call-multiple-times.cc
157 Read N Characters Given Read4 read-n-characters-given-read4.cc
156 Binary Tree Upside Down binary-tree-upside-down.cc
155 Min Stack min-stack.cc
154 Find Minimum in Rotated Sorted Array II find-minimum-in-rotated-sorted-array-ii.cc
153 Find Minimum in Rotated Sorted Array find-minimum-in-rotated-sorted-array.cc
152 Maximum Product Subarray maximum-product-subarray.cc
151 Reverse Words in a String reverse-words-in-a-string.cc
150 Evaluate Reverse Polish Notation evaluate-reverse-polish-notation.cc
149 Max Points on a Line max-points-on-a-line.cc
148 Sort List sort-list.cc
147 Insertion Sort List insertion-sort-list.cc
146 LRU Cache lru-cache.cc
145 Binary Tree Postorder Traversal binary-tree-postorder-traversal.cc
144 Binary Tree Preorder Traversal binary-tree-preorder-traversal.cc
143 Reorder List reorder-list.cc
142 Linked List Cycle II linked-list-cycle-ii.cc
141 Linked List Cycle linked-list-cycle.cc
140 Word Break II word-break-ii.cc
139 Word Break word-break.cc
138 Copy List with Random Pointer copy-list-with-random-pointer.cc
137 Single Number II single-number-ii.cc
136 Single Number single-number.cc
135 Candy candy.cc
134 Gas Station gas-station.cc
133 Clone Graph clone-graph.cc
132 Palindrome Partitioning II palindrome-partitioning-ii.cc
131 Palindrome Partitioning palindrome-partitioning.cc
130 Surrounded Regions surrounded-regions.cc
129 Sum Root to Leaf Numbers sum-root-to-leaf-numbers.cc
128 Longest Consecutive Sequence longest-consecutive-sequence.cc
127 Word Ladder word-ladder.cc
126 Word Ladder II word-ladder-ii.cc
125 Valid Palindrome valid-palindrome.cc
124 Binary Tree Maximum Path Sum binary-tree-maximum-path-sum.cc
123 Best Time to Buy and Sell Stock III best-time-to-buy-and-sell-stock-iii.cc
122 Best Time to Buy and Sell Stock II best-time-to-buy-and-sell-stock-ii.cc
121 Best Time to Buy and Sell Stock best-time-to-buy-and-sell-stock.cc
120 Triangle triangle.cc
119 Pascal’s Triangle II pascals-triangle-ii.cc
118 Pascal’s Triangle pascals-triangle.cc
117 Populating Next Right Pointers in Each Node II populating-next-right-pointers-in-each-node-ii.cc
116 Populating Next Right Pointers in Each Node populating-next-right-pointers-in-each-node.cc
115 Distinct Subsequences distinct-subsequences.cc
114 Flatten Binary Tree to Linked List flatten-binary-tree-to-linked-list.cc
113 Path Sum II path-sum-ii.cc
112 Path Sum path-sum.cc
111 Minimum Depth of Binary Tree minimum-depth-of-binary-tree.cc
110 Balanced Binary Tree balanced-binary-tree.cc
109 Convert Sorted List to Binary Search Tree convert-sorted-list-to-binary-search-tree.cc
108 Convert Sorted Array to Binary Search Tree convert-sorted-array-to-binary-search-tree.cc
107 Binary Tree Level Order Traversal II binary-tree-level-order-traversal-ii.cc
106 Construct Binary Tree from Inorder and Postorder Traversal construct-binary-tree-from-inorder-and-postorder-traversal.cc
105 Construct Binary Tree from Preorder and Inorder Traversal construct-binary-tree-from-preorder-and-inorder-traversal.cc
104 Maximum Depth of Binary Tree maximum-depth-of-binary-tree.cc
103 Binary Tree Zigzag Level Order Traversal binary-tree-zigzag-level-order-traversal.cc
102 Binary Tree Level Order Traversal binary-tree-level-order-traversal.cc
101 Symmetric Tree symmetric-tree.cc
100 Same Tree same-tree.cc
99 Recover Binary Search Tree recover-binary-search-tree.cc
98 Validate Binary Search Tree validate-binary-search-tree.cc
97 Interleaving String interleaving-string.cc
96 Unique Binary Search Trees unique-binary-search-trees.cc
95 Unique Binary Search Trees II unique-binary-search-trees-ii.cc
94 Binary Tree Inorder Traversal binary-tree-inorder-traversal.cc
93 Restore IP Addresses restore-ip-addresses.cc
92 Reverse Linked List II reverse-linked-list-ii.cc
91 Decode Ways decode-ways.cc
90 Subsets II subsets-ii.cc
89 Gray Code gray-code.cc
88 Merge Sorted Array merge-sorted-array.cc
87 Scramble String scramble-string.cc
86 Partition List partition-list.cc
85 Maximal Rectangle maximal-rectangle.cc
84 Largest Rectangle in Histogram largest-rectangle-in-histogram.cc
83 Remove Duplicates from Sorted List remove-duplicates-from-sorted-list.cc
82 Remove Duplicates from Sorted List II remove-duplicates-from-sorted-list-ii.cc
81 Search in Rotated Sorted Array II search-in-rotated-sorted-array-ii.cc
80 Remove Duplicates from Sorted Array II remove-duplicates-from-sorted-array-ii.cc
79 Word Search word-search.cc
78 Subsets subsets.cc
77 Combinations combinations.cc
76 Minimum Window Substring minimum-window-substring.cc
75 Sort Colors sort-colors.cc
74 Search a 2D Matrix search-a-2d-matrix.cc
73 Set Matrix Zeroes set-matrix-zeroes.cc
72 Edit Distance edit-distance.cc
71 Simplify Path simplify-path.cc
70 Climbing Stairs climbing-stairs.cc
69 Sqrt(x) sqrtx.cc
68 Text Justification text-justification.cc
67 Add Binary add-binary.cc
66 Plus One plus-one.cc
65 Valid Number valid-number.cc
64 Minimum Path Sum minimum-path-sum.cc
63 Unique Paths II unique-paths-ii.cc
62 Unique Paths unique-paths.cc
61 Rotate List rotate-list.cc
60 Permutation Sequence permutation-sequence.cc
59 Spiral Matrix II spiral-matrix-ii.cc
58 Length of Last Word length-of-last-word.cc
57 Insert Interval insert-interval.cc
56 Merge Intervals merge-intervals.cc
55 Jump Game jump-game.cc
54 Spiral Matrix spiral-matrix.cc
53 Maximum Subarray maximum-subarray.cc
52 N-Queens II n-queens-ii.cc
51 N-Queens n-queens.cc
50 Pow(x, n) powx-n.cc
48 Rotate Image rotate-image.cc
47 Permutations II permutations-ii.cc
46 Permutations permutations.cc
45 Jump Game II jump-game-ii.cc
44 Wildcard Matching wildcard-matching.cc
43 Multiply Strings multiply-strings.cc
42 Trapping Rain Water trapping-rain-water.cc
41 First Missing Positive first-missing-positive.cc
40 Combination Sum II combination-sum-ii.cc
39 Combination Sum combination-sum.cc
38 Count and Say count-and-say.cc
37 Sudoku Solver sudoku-solver.cc
36 Valid Sudoku valid-sudoku.cc
35 Search Insert Position search-insert-position.cc
34 Search for a Range search-for-a-range.cc
33 Search in Rotated Sorted Array search-in-rotated-sorted-array.cc
32 Longest Valid Parentheses longest-valid-parentheses.cc
31 Next Permutation next-permutation.cc
30 Substring with Concatenation of All Words substring-with-concatenation-of-all-words.cc
29 Divide Two Integers divide-two-integers.cc
28 Implement strStr() implement-strstr.cc
27 Remove Element remove-element.cc
26 Remove Duplicates from Sorted Array remove-duplicates-from-sorted-array.cc
25 Reverse Nodes in k-Group reverse-nodes-in-k-group.cc
24 Swap Nodes in Pairs swap-nodes-in-pairs.cc
23 Merge k Sorted Lists merge-k-sorted-lists.cc
22 Generate Parentheses generate-parentheses.cc
21 Merge Two Sorted Lists merge-two-sorted-lists.cc
20 Valid Parentheses valid-parentheses.cc
19 Remove Nth Node From End of List remove-nth-node-from-end-of-list.cc
18 4Sum 4sum.cc
17 Letter Combinations of a Phone Number letter-combinations-of-a-phone-number.cc
16 3Sum Closest 3sum-closest.cc
15 3Sum 3sum.cc
14 Longest Common Prefix longest-common-prefix.cc
13 Roman to Integer roman-to-integer.cc
12 Integer to Roman integer-to-roman.cc
11 Container With Most Water container-with-most-water.cc
10 Regular Expression Matching regular-expression-matching.cc
9 Palindrome Number palindrome-number.cc
8 String to Integer (atoi) string-to-integer-atoi.cc
7 Reverse Integer reverse-integer.cc
6 ZigZag Conversion zigzag-conversion.cc
5 Longest Palindromic Substring longest-palindromic-substring.cc
4 Median of Two Sorted Arrays median-of-two-sorted-arrays.cc
3 Longest Substring Without Repeating Characters longest-substring-without-repeating-characters.cc
2 Add Two Numbers add-two-numbers.cc
1 Two Sum two-sum.cc
1
2
3
4
5
6
copy($('td:has(.ac) ~ td:nth-child(3) a').map(function(_,e){
var id = $(e).parent().prev().text();
var h=e.href.replace(/htt.*problems/,'/leetcode');h=h.substr(0,h.length-1);
var title=e.textContent, href=e.href, name=h.replace(/.*\//,'');
return '|'+id+'|['+title+']('+href+')|['+name+'.cc]('+name+'.cc)|'
}).toArray().join('\n'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
require 'mechanize'
agent = Mechanize.new
page = agent.get 'https://leetcode.com/accounts/login/'
doc = page.form_with {|form|
form['login'] = 'MaskRay'
form['password'] = getpass
}.submit.parser
total = doc.css('td:nth-child(3)').size
solved = doc.css('td:has(.ac)').size
puts "You have solved #{solved}/#{total} problems."
for a in doc.css('td:nth-child(3) a')
id = a.parent.previous_element.text
href = a['href']
name = href.sub(/\/problems\/(.*)\//, '\1')
title = a.text
puts "|#{id}|[#{title}](#{href})|[#{name}.cc](#{name}.cc)|"
end