前言

数据结构和算法可以让程序员脱胎换骨，刷算法题可以帮助我们通过面试和笔试，找到梦寐以求的工作，进入一线大厂或者拿高薪。怎么刷题呢？LeetCode上有2000多道题目，难道要全部刷完？

国内的一线大厂在面试和笔试的时候会考察什么样的题目？

发现存在着很大的重复性，有些题目甚至所有的公司都有考察，比如LeetCode-206.反转链表。同时这些题目所属的类别包括了基础的数组、链表、排序，高阶的位运算、动态规划也有考察。从题目的难度来说，中等难度占了一半以上，困难的只有十分之一不到。

这就提示我们，刷题要刷，但不是盲目的刷，要有针对性，重点的去刷，一起对这些题目进行讲解。

复杂度分析

复杂度分析是在数据结构和算法我们经常听到的一个概念，因为数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。

算法的复杂度

任何程序的执行，都需要空间，比如内存空间和时间，所以只要讲到数据结构与算法，就一定离不开时间、空间复杂度分析。而这两者之中，我们更关注时

间复杂度，毕竟时间一去不回，而程序需要的执行空间可以靠增加内存等存储空间来解决。

事后统计法

把代码跑一遍，通过统计、监控，同样也可以得到算法执的时间和占用的内存大小。而且会更准确。这种评估算法执效率的方法叫事后统计法。但是，这种统计方法有非常大的局限性。

1、必须依据算法事先编制好程序，这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法，不是竹篮打水一场空吗?

2.测试结果非常依赖测试环境

测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用不同的CPU执行，速度肯定是不一样，甚至还可能出现两台机器完全相反的结果。

3.测试结果受数据性质或者规模的影响很大。后面我们会讲到排序算法，对同一个排序算法，待排序数据的有序度不一样，排序的执时间就会有很大的差别。极端情况下，如果数据已经是有序的，那排序算法需要做任何操作，执时间就会非常短。

除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。比如10个数字的排序，不管用什么算法，差异几乎是零。而如果有一百万个随机数字排序，那不同算法的差异就非常大了。比如，JDK中的排序，对于小规模的数据排序，Java反而采用的是较慢的插入排序而不是一般意义上更快的快速排序。

所以，我们需要一个不用具体的测试数据来测试，就可以粗地估计算法的执效率的方法。这就是时间、空间复杂度分析。

因为时间复杂度的重要性相对空间复杂度更高，所以我们主要分析时间复杂度，在必要的时候会分析空间复杂度。

大O表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下,估算一段代码的执行时间呢?

我们用求1,2,3…n的累加和 这个例子(例1)来说明。

 int cal(int n) {

 int sum = 0;        

  for (int i=1; i <= n; ++i) {

     sum = sum + i;

 }

 return sum;

 }

上述的代码中，尽管每行代码长度、实际执行的时间都不一样，但是在算法估计中，我们总是认为每行代码执行的时间都一样，我们假设这个时间为t。

这段代码的总执行时间是多少呢?

第int sum = 0;、return sum;行代码分别需要1个t的执行时间，for循环的两行代码都运行了n遍，所以需要2n*t的执行时间，所以这段代码总的执行时间就是(2n+2)*t。可以看出来，所有代码的执行时间T(n)与每行代码的执行次数成正比。

按照这个分析思路，我们再来看这段代码(例2)。

 int cal2(int n) {

int sum = 0;

for (int i=1; i <= n; ++i) {

for (int j=1; j <= n; ++j) {

     sum = sum + i * j;

}

}

}

int sum = 0行，需要1个t的执行时间，第一个for循环执行了n遍，需要n *t 的执行时间，第二个for循环两行代码在外层循环的每遍执行中都执行了n遍，所以总共执行了n²遍，所以需要n² *t的执行时间。所以，整段代码总的执行时间T(n)=(n²+n+1)*t。

尽管我们不知道t 的具体值，但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间T(n)与每行代码的执行次数n成正比。我们可以把这个规律总结成一个公式。

T(n)=O(f(n))

其中，T(n)表示代码执行的时间；n表示数据规模的大小；f(n)表示每行代码执行的次数总和，因为它是n的某个函数，所以用f(n)来表示。整个公式表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

所以，第一个例子中的T(n)= O(2n+2)，第二个例子中的T(n)= O(n²+n+1)。这就是大О时间复杂度表示法。大О时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

(LeetCode-70)爬楼梯

热度

《LeetCode热题HOT 100》专题

题目

假设你正在爬楼梯。需要n 阶你才能到达楼顶。

每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定n是一个正整数。

示例1：

输入：2

输出：2

解释：有两种方法可以爬到楼顶。

1.  1阶+ 1阶

2.  2阶

示例2：

输入：3

输出：3

解释：有三种方法可以爬到楼顶。

1.  1阶+ 1阶+ 1阶

2.  1阶+ 2阶

3.  2阶+ 1阶

分析和解答

方法1

我们仔细想下，实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶，另一类是第一步走了2个台阶。

所以n个台阶的走法的个数就等于先走1阶后剩下的n-1个台阶的走法个数再加上先走2阶后剩下的n-2个台阶的走法个数。用公式表示就是︰

f(n) = f(n-1)+f(n-2)

这其实就是个递归公式，我们再来看下终止条件。当有一个台阶时，我们不需要再继续递归，就只有一种走法。所以f(1)=1。但是这个递归终止条件不够。

n=2时，f(2)=f(1)+f(0)。如果递归终止条件只有一个f(1)=1，那f(2)就无法求解了。所以除了f(⑴)=1这一个递归终止条件外，还要有f(0)=1，表示走0个台阶有一种走法，不过这样子有点滑稽。所以，我们可以把f(2)=2单独作为一种终止条件，表示走2个台阶，有两种走法，一步走完或者分两步来走。

所以，递归终止条件就是f(1)=1，f(2)=2。

综合在一起就是这样的:

 

这种方法的时间复杂度为O(n²)。

方法2

仔细分析我们上面的实现，最大的问题是什么？存在着大量的重复计算，我们以f(6)来分析一下：

可以看到在f(6)的求解过程中，f(3)和f(4)都被求解了多次，这个其实是没必要的，我们可以通过一个HashMap来保存已经求解过的f(k)。当递归调用到f(k)时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。

这种方法的时间复杂度为O(n)。

方法3

在这个题目中，递归的解法是自顶向下，由最开始的顶层数字一层层分解直到最底层的f(1和f(2)，再将结果又一层层累加上来。循环的解法则可以直接由底向上，从最底层的f(1和f(2)，直接累加上来即可，而且从图中可以看到，上一个循环中计算出来的值刚好可以在下一个循环中使用。

不过一般来说，循环取代递归的解法在代码上要复杂一些，也比较难以理解一点。

这种方法的时间复杂度为O(n)。

代码

ClimbingStairs_70.java

(剑指Offer 10) 斐波那契数列

热度

京东

题目

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下:

分析和解答

可以看到，这个斐波那契数列的公式几乎和上面的“(LeetCode-70)爬楼梯”一模一样，所以具体的解答和代码就作为作业留给大家自己思考和实现。

数组

(LeetCode-1)两数之和

热度

字节、美团、阿里巴巴、腾讯、百度、京东

《LeetCode热题HOT 100》专题

题目

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为nums[0] + nums[1] == 9，返回[0, 1]。

示例2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

分析和解答

方法1

暴力穷举，复杂度O(n²)。

对数组中每个元素，都去计算它和数组中其他元素的和sum是否等于目标值target，如果是则返回结果，不是则继续循环，直到将所有元素检查一遍。

方法2

 这道题最优的做法时间复杂度是O(n)。用一个哈希表，存储每个数对应的下标。具体做法是：顺序扫描数组，对每一个元素，在map中找能组合给定值的另一半数字，如果找到了，直接返回2个数字的下标即可。如果找不到，就把这个数字存入map中，等待扫到“另一半"数字的时候，再取出来返回结果。

当然，这个hash表中存入组合给定值的另一半数字也是可以的。

(LeetCode-88) 合并两个有序数组

热度

字节、美团、快手

《LeetCode热题HOT 100》专题

题目

给你两个按非递减顺序 排列的整数数组 nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。

请你合并nums2到nums1中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。

示例1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

解释：需要合并[1,2,3]和[2,5,6]。

合并结果是[1,2,2,3,5,6]，其中斜体加粗标注的为nums1中的元素。

示例2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0

输出：[1]

解释：需要合并[1]和[]。

合并结果是[1]。

示例3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1

输出：[1]

解释：需要合并的数组是[]和[1]。

合并结果是[1]。

注意，因为m = 0，所以nums1中没有元素。nums1中仅存的0仅仅是为了确保合并结果可以顺利存放到nums1中。

进阶：你可以设计实现一个时间复杂度为O(m + n)的算法解决此问题吗？

分析和解答

方法1

最容易想到的办法，把两个数组合并在一起后，再进行排序。这里的排序我们可以直接使用JDK中的sort方法，JDK中的排序在元素的数量小于47时，使用的插入排序，大于47时使用的快速排序，我们简单的以快速排序作为标准，这种方法的时间复杂度来为O((m+n)log(m+n))，空间复杂度为：O(log(m+n))。当然现在我们还不知道快速排序是个什么东西，我们后面会学到的并且会带大家去手写实现一个快速排序。

方法2

方法1的最大问题是什么，仔细观察题目我们其实可以发现，这个两个数组本身其实就是已经有序的了，这一点我们没有利用上，所以改进的办法就是利用“双指针”，每次从两个数组头部取出比较小的数字放到结果中。

这种方法的时间复杂度是多少呢？因为要把两个数组各循环一遍，所以时间复杂度是O(m+n)，在处理上因为需要一个额外的空白数组来存放两个数组的值，所以空间复杂度也是O(m+n)。

方法3

方法2中还需要一个长度为m+n的临时数组作为中转，能不能不要这个数组呢？因为题目中的整数数组 nums1的后面还有空位，完全可以利用上。所以改进方法就是，依然使用双指针，但是倒序处理。

这种情况下，时间复杂度是O(m+n)，空间复杂度则变为O(1)。

代码

MergeSortedArray_88.java

结论

#2022春招##学习路径#