算法之回溯、动态规划、贪心、位运算

算法与数据操作也是面试时经常问到的题目。很多算法都有递归和循环的实现，同时查找和排序也是很基础的内容，除此之外，回溯法、贪心法、动态规划等针对一类问题的算法都是非常重要的。

回溯法

回溯法可以看作蛮力法的升级版，它从解决问题每一步的所有可能选项里系统地选出一个可行的解决方案。

回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选项。我们就这样重复选择，直至到达最终的状态。

一般可以用树状结构表示回溯法的搜索过程。若在某一步有 n 个可能选项，则有 n 个子节点，如果叶节点的状态满足题目约束，则找到了一个可行解。否则，尝试其他兄弟选项，若依旧没有可行解，则回溯到父节点。若所有节点均已遍历，仍无满足条件的终结状态，则该问题无解。

一般遇到二维数组或者网格运动相关的题目都可以用回溯法解决。

动态规划问题的特点：

贪婪算法每一步都能做出一个贪婪的选择，基于这个选择，我们可以得到问题的最优解，但是贪婪选择需要用数学方法证明其正确性。

位运算包括与（&）、或（|）、异或（^）、左移（<<）、右移（>>）这五种。

把一个整数减去 1 之后再和原来的整数做与运算（n & (n - 1)），得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制问题都可以用这种思路解决，比如判断是不是 2 的整数次方，比如整数 m 需要改变多少位才能得到整数 n（先用异或再统计 1 的个数）。