All Posts

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.