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

更多干货

• 停车场寻车难？蓝牙5.1提供的新思路

• 端与云的融合

• 特斯拉Model 3 Key Card里的黑科技

• 从AVB到TSN - 时效性网络来了

• 汽车电子架构，进化或改革？

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

关注我们 (http://weng.ai)

公众号：曲奇泡芙