LeetCode题解

最近开始刷LeetCode了,这里整理一下部分题解,方便自己复习。这篇Post会随着时间持续更新。

Two Sum

这题很简单,最naive的方法就是两层循环,O(n2)的时间复杂度,但是这显然不是最优解,所以这里用了一个HashMap来把查找的时间复杂度降到O(1),key为nums[i],value为数组下标i,所以只要遍历两次数组即可得到结果。

Longest Substring Without Repeating Characters

比较简单的动态规划,用一个HashMap记录每个字符上次出现的位置,用一个变量记录当前字符串的起点位置,每次往后一个字符,就去HashMap里查询是否出现过,如果出现位置在当前字符串起点位置之前,则不用管,如果在之后,就把start移到这个位置的后一个字符,继续按照上面的步骤遍历字符串,每一次得到的maxLength和之前的比较,O(n)时间内可以得到结果。

Median of Two Sorted Arrays

这题乍看思路很简单,两个有序数组,合并成一个,然后取中位数就好了,但是这样的时间复杂度就是O(m+n),题目要求是O(log(m+n)),看起来是要用二分查找了,但是我试了一下,用合并数组的方式,也能过,看来leetcode并没有卡时间,这里先贴一下合并数组的解决方案:

Longest Palindromic Substring

我这里用了一个比较naive的方案,时间复杂度是O(n2),先给每个字符两边加上#字符,这是为了消除字符串奇数和偶数个字符的差别,然后遍历字符串,比较以每个字符为中心的回文字符串长度,取最大值。
看了一下网上的解答,有一种时间复杂度为O(n)的Manacher算法,暂时没细看,二刷leetcode的时候再看。

Container With Most Water

这道题比较朴素,取两个指针,一个从数组最左边开始,一个从数组最右边开始相向移动。这里要求最大面积,所以整体思路是尽量把两条边中短的那一条换成更长的,这样才有可能总面积更大。结束条件是两个指针相遇。

Longest Common Prefix

最长公共前缀的问题,最开始想复杂了,觉得可能需要一个字典树。后来一想,有个更简单的办法,以第一个字符串作为基准,每次和下一个字符串比较,遍历完一遍数组,就可以得到最长公共前缀。

3Sum

本来以为这个问题跟Two Sum差不多,真自己做了一下后发现比Two Sum要复杂,主要是去重问题还有考虑各种边界条件。解法是,先对数组排序,嵌套循环的外层循环每次选一个元素,然后内层循环用两个指针分别从两端相向移动,如果三个数的和大于零,则把尾指针向中心移动,如果小于零,把头指针向中心移动。如果等于零,那么头尾指针分别向中心移动,但是要跳过重复元素。外层循环也需要跳过重复元素。

Valid Parentheses

这题比较简单,用一个栈来做匹配即可,但是要注意一些边界情况,比如"]"这种输入。

Merge Two Sorted Lists

简单的归并排序的问题,还是注意考虑边界情况。

Generate Parentheses

这种列出所有解的情况,大部分是递归问题,递归结束条件是,左括号和右括号数量都为0,如果出现右括号数比左括号数少的情况,那说明出现了)(这种非法组合,直接return

Merge k Sorted Lists

这题粗看也不难,最初我的想法是,每次把lists里的第一个元素拿出来比较,然后取最小的,放到结果链表的尾部,时间复杂度是O(m*n),但是这种解法只能过前129个用例,最后一个因为超时过不去,这道题LeetCode还是卡了运行时间的,下面贴一下这种解法:

后来看到一种时间复杂度更优的方法,但是要借助Java的PriorityQueue类,其实这是一种很取巧的办法,因为PriorityQueue本身就是会帮忙排序的,这种解法也贴一下,来自leetcode讨论区排第一的解法:

附录

以下都是不曾在LeetCode中出现过,但是我个人觉得对面试比较有帮助的知识点。

Longest Common Substring

最长公共子串,也是比较典型的动态规划问题,我们用一个二维数组来缓存每次比较的状态,然后找这个矩阵对角线最长的序列即可。但是遍历一个矩阵也比较麻烦,所以这里做了个变通,在要把矩阵当前元素设为1时检测左上角的元素,如果左上角元素大于0,那就把当前元素设为左上角元素加一。最后整个矩阵中最大的值就是最长公共子串的长度。时间复杂度为O(mn),空间复杂度也为O(mn)。