Leetcode 第二、三页题目精选

做Leetcode的过程也是一个寻找趣味题目的过程。Leetcode的第二页及第三页这100题断断续续做了有段时间了，趁周末时间把它close掉了。几个有意思的题目挑出来给大家思考一下。

Sort Colors

给一个包含只有数字0, 1, 2的数组，问如何在仅使用一次遍历的过程，O(N)完成对这个数组的排序？

Maximal Rectangle

这是个比较经典的题目了。如下图，给一个0，1矩阵（n*m），求一个最大面积的子矩阵，满足子矩阵里数字全是1，输出最大的子矩阵面积。你的算法时间复杂度是多少？

Recover Binary Search Tree

给一个排序二叉树，其中有两个结点被错误的交换了，问如何在不改变二叉树结构的前提下，恢复排序二叉树（交换回来两个出错的结点）。

Single Number II

给一个整数数组，其中有一个数字仅出现1次，其他所有数字都出现了3次，如何在O(N)的时间复杂度下，O(1)的内存使用条件下找出这个仅出现1次的数字？

Candy

有N个小孩站一排，每个小孩有个分值，你需要给这些小孩发糖果，满足：

• 每个小孩至少有一个糖果；
• 如果一个小孩的分值比他邻居分值大，那么他应该比邻居拿到更多糖果；

问你最少需要多少个糖果？

Flatten Binary Tree to Linked List

给一个二叉树，如何in-place的把它按前序遍历的次序修改成一个链表（使用right指针）？

第三页开始可以明显感觉到比较多的二叉树相关题目，二叉树的题目一般可以利用其子树嵌套的特性，将问题分成左右子树的子问题递归解决。比如上面这个题目的一个C++实现代码如下。

Best Time to Buy and Sell Stock III

给一个数组表示某支股票每天的股票价格，你最多可以交易两次（买卖各两次），同一天只能做一次交易（买/卖一次）。问怎么买卖收益最大？输出最大收益。

考察算法的题目往往不限于一种解法，一个题目可能会有不同时间/空间复杂度的多种不同解法，有时候最优解的算法也可能存在多种，这样的题目也经常会在面试中使用以提高题目区分度。平时自己做完的题目再看看别人的解法经常会有不同收获。我把leetcode的150题代码放到了github：https://github.com/Jamesweng/leetcode 欢迎交流。