笔试面试算法学习笔记
时间复杂度
-
$n\le 20$ ，这一类题目的数据范围较小，可以直接使用DFS算法，来枚举所有的情况，例如DFS专题中的二进制枚举，对应的复杂度为$O(2^n)$或者$O(n\times 2^n)$在当前给定数据范围内，$O(n\times 2^n)$的最坏执行次数为$$O(20\times 2^{20})\approx O(20\times 10^6)=O(2\times 10^7)$$ 其中$2^{10}=1024\approx 10^3$ -
$n\le 100$ ，这一类题目可以使用$O(n^3)$以内复杂度的算法求解，这一类题型可能会涉及到二维前缀和、动态规划等算法。 -
$n\le 10^5$ ，这一类题目可以使用$O(n)$或者$O(nlogn)$复杂度的算法求解，这一类题型可能涉及到堆（优先队列）、排序、动态规划、树状数组、堆优化版dijkstra、二分查找、二分答案、质数筛等。 -
$n\le 10^9$ ，这一类题目可以使用$O(\sqrt{n})$或者$O(logn)$复杂度的算法求解，这一类题型可能涉及到判断质数、因子个数计算、二分答案、快速幂、最大公约数等。 -
$n\le 10^{1000}$ ，这一类题目可以使用$O(logn)$或者$O((logn)^2)$复杂度的算法求解，这一类题型很大概率是数位DP。
空间复杂度
空间复杂度的概念和时间复杂度很类似，时间复杂度是反映程序执行的效率，空间复杂度是反映程序执行所需存储空间的大小，例如，输入数据量为n，你申请了一个长度为n的一维数组，那么对应的空间复杂度为$O(n)$，如果申请的是二维数组，那么对应的空间复杂度为$O(n^2)$
一般题目给定的空间内存要求为64MB，$$64MB=2^6\times 1MB=2^6\times 2^{10} B=2^6\times 2^{10}\times 2^{10} Byte=2^{26}Byte$$ 如果申请的是int型的数组，每个元素占用4个字节（$Byte$），因此可以申请$2^{24}$长度的空间，也就是近似$10^7$左右的范围。 一般对于给定的题目来说，申请一维数组的长度尽量不要超过$5\times 10^6$，申请二维数组的长度尽量不要超过$3\times 10^3$，大家当结论记就行。
基础算法之一，也是笔试中比较常考的一个算法，双指针题型以及变型有很多，这里面主要列举两大类
一类是在两个数组中使用两个指针分别指向这两个数组，这一类问题中，最经典的就是判断子序列的问题
另一类则是在一个数组中使用两个指针指向这一个数组，这类问题又称为同向双指针问题，也称为滑动窗口问题，这类问题的又可以细分为两类，第一类比较简单，可以称为定长滑动窗口，就是窗口大小是固定的，例如，给定窗口长度为$k$，需要计算在这个长度为$k$的窗口中的最大值/最小值/最大和等。
第二类则是笔试和面试都考察比较多的问题，也就是不定长滑动窗口，这一类题目一般是要求满足题目某个条件下的最大值/最小值/最大长度/最小长度/区间最大和/区间最小和/方案数。这一类题目，大家如果学习完动态规划这一章节之后，会发现他其实是有一种动态规划的思想在，例如给定l和r两个双指针，很多问题其实就变为以r结尾的最大值/最小值，这类问题是需要满足单调性的：当[l,r]区间不满足条件时，l指针需要左移，直到[l,r]区间满足条件为止，且当l=r时，都可以满足条件，很多时候，如果数组的数值可以取负数，是不能使用双指针来求最优解的，就是因为不满足单调性，这种题目其实比较难的是一种抽象问题的能力，有的题目需要把问题做一个转化，首先需要判断是否满足单调性，如果满足，就需要把问题转化为一个可以使用双指针去解决的一个滑动窗口问题。
- 最长上升/下降子数组