掌握了这些算法技巧，可以少刷一半的Leetcodee ！

今天我们来聊聊在做算法题时常用的一些技巧。对于平时没有接触过这些技巧的人，不妨试着在实际问题中应用看看，或许能帮助你优化解法、提升效率。

数组的下标本身就是一个非常有用的工具，特别是在统计数字或者判断某个整数是否出现过时非常高效。例如，给你一串字母，让你统计这一串字母中每个字母出现的次数，我们就可以把这些字母的 ASCII 值作为下标，这样在遍历到字母 a 时，执行 arr['a']++，这样我们就无需针对每个字母进行逐个判断。

再看一个例子：给你一个长度为 n 的无序整数数组 arr，并且这些整数的取值范围都在0-20之间，要求你在时间复杂度为 O(n) 的前提下，将这 n 个数按从小到大的顺序打印出来。

对于这道题，如果你是先把这 n 个数先排序，再打印，是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标，如果这个数出现过，则数组对应位置上的元素加1。

代码如下：

public void f(int arr) { int temp = new int[21]; for (int i = 0; i

有时候我们在遍历数组的时候，会进行越界判断，如果下标差不多要越界了，我们就把它置为0重新遍历。特别是在一些环形的数组中，例如用数组实现的队列。往往会写出这样的代码：

for (int i = 0; i

实际上我们可以通过取余的方法来简化代码

for (int i = 0; i

对于双指针，在做关于单链表的题是特别有用，比如:

对于这类问题，我们就可以使用双指针了，会方便很多。我顺便说下这三个问题怎么用双指针解决吧。

例如对于第 1 个问题：我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。

对于第 2 个问题：一样是设置一个快指针和慢指针。在遍历链表的时候，慢指针每次走一步，快指针每次走两步，当快指针遍历完成时，慢指针正好位于链表中间。

对于第 3 个问题：设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。

可以看到，双指针的使用不仅逻辑清晰，而且代码实现也简洁高效。所以以后在处理与链表相关的一些问题的时候，不妨优先考虑使用双指针技巧。

在进行除法或乘法运算时，尤其是除以或乘以 2、4、8 这样的数字时，我们可以使用位移运算来替代，执行效率会更高。

例如:

n / 2 等价于 n >> 1n / 4 等价于 n >> 2n / 8 等价于 n >> 3。

使用移位运算不仅可以提升执行速度，还显得你对底层优化很有研究（哈哈）。

此外，还有一些按位运算（如 & 与、| 或）也可以提升效率。例如，判断一个数是否是奇数，很多人会写：

if(n % 2 == 1){ dosomething;}

不过我们用按位与或运算的话会快很多。例如判断是否是奇数，我们就可以把n和1相与了，如果结果为1，则是奇数，否则就不会。即

if(n & 1 == 1){ dosomething;)

具体的一些运算技巧，还得需要你们多在实践中尝试着去使用，这样用久后就会比较熟练了。

在处理链表问题时，我们经常会设置一个“头指针”，这个头指针是不存任何有效数据的，只是为了简化操作逻辑，这个头指针我们就可以称之为哨兵位了。

例如我们要删除链表的第一个节点时，如果没有哨兵，就需要特殊处理；但是我们设置了哨兵，无论是删除第一个节点还是中间的节点，操作方式就完全一致了，无需额外判断。同样，在插入节点时也会简化逻辑。

有时候我们在操作数组的时候，也是可以设置一个哨兵的，把arr[0]作为哨兵。例如，要判断两个相邻的元素是否相等时，设置了哨兵就不怕越界等问题了，可以直接arr[i] == arr[i-1]了。不用怕i = 0时出现越界。

当然我这只是举一个例子，具体的应用还有很多，例如插入排序，环形链表等。

当我们使用递归来解决一个问题的时候，容易产生重复去算同一个子问题，这个时候我们要考虑状态保存以防止重复计算。例如随便举一个例子：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法，则有f(n) = f(n-1) + f(n - 2)。

递归的结束条件是当0

public int f(int n) { if (n

不过这个写法存在大量重复计算，例如 f(8) 会多次计算 f(3)、f(4) 等。

这个时候我们要考虑状态保存。将已经计算过的结果存下来（使用数组或 HashMap），代码如下：

//数组的大小根据具体情况来，由于int数组元素的的默认值是0 //因此我们不用初始化int arr = newint[1000];public int f(int n) { if (n

这样，可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。

考虑自底向上

递归通常是自顶向下的做法，需要不断深入函数调用，直到满足终止条件后再逐层返回。如果 n 很大，比如 n = 10000，那么需要递归 10000 层，很可能导致栈溢出。

对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道

f(1) = 1;f(2) = 2;

那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此，我们可以考虑使用自底向上的方法来做。

代码如下：

public int f(int n) { if(n

这种方式不需要递归，也就不存在栈溢出的问题。我们通常称之为“递推”。