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.

LeetCode 第一页题目

最近用一些碎片时间刷了LeetCode 第一页的题目 (https://leetcode.com),除了一些面试中曝光率较高的题目外,有几个题目挺有意思的,恰逢考试季挑出来给大家思考一下。 Median of Two Sorted Arrays 给定两个排序的整数数组,长度分别为m和n,求这两个数组所有数的中位数,要求时间复杂度为O(log(m+n))。 比如:nums1=[1, 2], nums2=[3, 4],中位数为 2.5 时间复杂度的要求,使得先合并数组再求中位数的O(m+n)方法并不可行。 Divide Two Integers 给两个32位有符号整数a和b,计算a/b取整,要求算法中 不使用乘法,除法和模运算 。 比如:a = 7, b = -3,结果为:-2 Substring with Concatenation of All Words 给一个字符串s,以及一个单词列表words,其中所有单词等长度。在s中找出所有的下标i,满足s[i]开始的子串是由words中的所有单词某种排列组成(所有单词有且出现出现一次)。 比如 s = "