今天和大家讲讲，在做算法题时常用的一些技巧。对于平时没用过这些技巧的人，或许你可以考虑试着去看看在实践中能否用的上这些技巧来优化问题的解。
1. 巧用取余
有时候我们在遍历阵列的时候，会进行越界判断，如果下标差不多要越界了，我们就把它置为0重新遍历。特别是在一些环形的阵列中，例如用阵列实现的伫列。往往会写出这样的程式码：
for (int i = 0; i if (pos //没有越界
// 使用阵列arr[pos]
else {
pos = 0;//置为0再使用阵列
//使用arr[pos]
}
pos++;
}
实际上我们可以通过取余的方法来简化程式码
for (int i = 0; i //使用阵列arr[pos] (我们假设刚开始的时候pos pos = (pos + 1) % N;
}
2. 巧用阵列下标
阵列的下标是一个隐含的很有用的阵列，特别是在统计一些数字，或者判断一些整型数是否出现过的时候。例如，给你一串字母，让你判断这些字母出现的次数时，我们就可以把这些字母作为下标，在遍历的时候，如果字母a遍历到，则arr[a]就可以加1了，即 arr[a]++;
通过这种巧用下标的方法，我们不需要逐个字母去判断。
我再举个例子：
问题：给你n个无序的int整型阵列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 temp[arr[i]]++;
}
//顺序打印
for (int i = 0; i for (int j = 0; j System.out.println(i);
}
}
}
利用阵列下标的应用还有很多，大家以后在遇到某些题的时候可以考虑是否可以巧用阵列下标来优化。
3. 巧用双指标
对于双指标，在做关于单链表的题是特别有用，比如“判断单链表是否有环”、“如何一次遍历就找到连结串列中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题，我们就可以使用双指标了，会方便很多。我顺便说下这三个问题怎么用双指标解决吧。
例如对于第一个问题
我们就可以设定一个慢指标和一个快指标来遍历这个连结串列。慢指标一次移动一个节点，而快指标一次移动两个节点，如果该连结串列没有环，则快指标会先遍历完这个表，如果有环，则快指标会在第二次遍历时和慢指标相遇。
对于第二个问题
一样是设定一个快指标和慢指标。慢的一次移动一个节点，而快的两个。在遍历连结串列的时候，当快指标遍历完成时，慢指标刚好达到中点。
对于第三个问题
设定两个指标，其中一个指标先移动k个节点。之后两个指标以相同速度移动。当那个先移动的指标遍历完成的时候，第二个指标正好处于倒数第k个节点。
你看，采用双指标方便多了吧。所以以后在处理与连结串列相关的一些问题的时候，可以考虑双指标哦。
4. 设定哨兵位
在连结串列的相关问题中，我们经常会设定一个头指标，而且这个头指标是不存任何有效资料的，只是为了操作方便，这个头指标我们就可以称之为哨兵位了。
例如我们要删除头第一个节点是时候，如果没有设定一个哨兵位，那么在操作上，它会与删除第二个节点的操作有所不同。但是我们设定了哨兵，那么删除第一个节点和删除第二个节点那么在操作上就一样了，不用做额外的判断。当然，插入节点的时候也一样。
有时候我们在算子组的时候，也是可以设定一个哨兵的，把arr[0]作为哨兵。例如，要判断两个相邻的元素是否相等时，设定了哨兵就不怕越界等问题了，可以直接arr[i] == arr[i-1]?了。不用怕i = 0时出现越界。
当然我这只是举一个例子，具体的应用还有很多，例如插入排序，环形连结串列等。
5. 巧用移位运算。
有时候我们在进行除数或乘数运算的时候，例如n / 2，n / 4, n / 8这些运算的时候，我们就可以用移位的方法来运算了，这样会快很多。
例如:
n / 2 等价于 n >> 1
n / 4 等价于 n >> 2
n / 8 等价于 n >> 3。
这样通过移位的运算在执行速度上是会比较快的，也可以显的你很厉害的样子，哈哈。
还有一些 &(与)、|(或)的运算，也可以加快运算的速度。例如判断一个数是否是奇数，你可能会这样做
if(n % 2 == 1){
dosomething();
}
不过我们用与或运算的话会快很多。例如判断是否是奇数，我们就可以把n和1相与了，如果结果为1，则是奇数，否则就不会。即
if(n & 1 == 1){
dosomething();
)
具体的一些运算技巧，还得需要你们多在实践中尝试着去使用，这样用久后就会比较熟练了。
6. 与递回有关的一些优化
（1）.对于可以递回的问题考虑状态储存
当我们使用递回来解决一个问题的时候，容易产生重复去算同一个子问题，这个时候我们要考虑状态储存以防止重复计算。例如我随便举一个之前举过的问题
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
这个问题用递回很好解决。假设 f(n) 表示n级台阶的总跳数法，则有
f(n) = f(n-1) + f(n - 2)。
递回的结束条件是当0
public int f(int n) {
if (n return n;
} else {
return f(n - 1) + f(n - 2);
}
}
不过对于可以使用递回解决的问题，我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递回，是有很多重复计算的。如
就有很多重复计算了。这个时候我们要考虑状态储存。例如用hashMap来进行储存，当然用一个数组也是可以的，这个时候就像我们上面说的巧用阵列下标了。可以当arr[n] = 0时，表示n还没计算过，当arr[n] != 0时，表示f(n)已经计算过，这时就可以把计算过的值直接返回回去了。因此我们考虑用状态储存的做法程式码如下：
//阵列的大小根据具体情况来，由于int阵列元素的的预设值是0
//因此我们不用初始化
int[] arr = new int[1000];
public int f(int n) {
if (n return n;
} else {
if (arr[n] != 0) {
return arr[n];//已经计算过，直接返回
} else {
arr[n] = f(n-1) + f(n-2);
return arr[n];
}
}
}
这样，可以极大著提高算法的效率。也有人把这种状态储存称之为备忘录法。
(2).考虑自底向上
对于递回的问题，我们一般都是从上往下递回的，直到递回到最底，再一层一层著把值返回。
不过，有时候当n比较大的时候，例如当 n = 10000时，那么必须要往下递回10000层直到 n
对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道
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 return n;
int f1 = 1;
int f2 = 2;
int sum = 0;
for (int i = 3; i sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}
我们也把这种自底向上的做法称之为递推。
总结一下
当你在使用递回解决问题的时候，要考虑以下两个问题
(1). 是否有状态重复计算的，可不可以使用备忘录法来优化。
(2). 是否可以采取递推的方法来自底向上做，减少一味递回的开销。
更多算法技巧，可以关注我的头条号，每日推送原创文章，专注于写资料结构与算法，辅写计算机网络、计算机基础、Java，期待各位的关注，保证让你有所收获。不信你试试
