thumbnail for this post
翁雨键
翁雨键
explore the unknown..
Aug 28, 2019 1 min read

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 欢迎交流。

End

 

 

新建"智能汽车与互联网技术"群聊,欢迎添加群主微信 6080901 添加入群。