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

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 = "barfoothefoobarman",  words = ["foo","bar"]

合法的下标为: 0 和 9

 

First Missing Positive

给一个无序的整数数组,找一个最小的未出现的正整数。要求:时间复杂度O(n) 且 仅使用 常量系数的额外内存

比如输入为:[3,4,-1,1],最小未出现的正整数为:2

 

Jump Game II

给一个非负整数数组,每个数组的元素表示你从该位置最多可以往前跳多少个位置,问从第一个位置跳到最后一个位置最少需要几跳?

比如输入为:[2,3,1,1,4] ,最小需要2跳到达最后一个位置。

该题存在多种不同时间复杂度的解法。

 

第一页的其他题目,除开一些考察编码能力比较直接的题目,有不少属于同类型题目,这样的题目在面试中通常会作为一个问题的延伸问题聊到,比如:

 

数组找几个数和为指定数的问题:"Two Sum", "3Sum", "3Sum Closest", "4Sum";

 

排列组合问题:

"Combination Sum", "Combination Sum II",

"Permutations", "Permutations II", "Next Permutation"

 

字符串模式匹配问题:"Regular Expression Matching", "Wildcard Matching"

 

二分查找问题:"Search in Rotated Sorted Array", "Find First and Last Position of Element in Sorted Aarray", "Search Insert Position"

 

括号序列问题:"Valid Parentheses", "Longest Valid Parentheses", "Generate Parentheses"

 

链表操作问题:"Remove Nth Node From End of List", "Merge Two Sorted Lists", "Swap Nodes in Pairs", "Reverse Nodes in k-Group"

 

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

 

End