最近用一些碎片时间刷了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
更多干货