前面的文章介绍了数组，哈希表，字符串，链表，树等常见数据结构。本小结补充一些其他的小技巧
二进制运算
面试题15：二进制中1的个数
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9，则该函数输出2.
常规的思想，可以判断此数是否是奇数，如果是奇数，则1的个数增加，此数右移一位，循环判断，直到右移后的结果为0。但实际上，这里有个小陷阱，因为右移的操作有时会有额外的问题，比如一个负数-1在右移后，还是-1，这样循环就无法结束了。另一个思路，是做一个flag标志位，初始化为1，和原数做&，如果为1，则1的个数增加，最后将flag左移，用来判断下一位。
这里，主要是想给大家介绍一个新的思路，利用了二进制位运算特征，我们可以很巧妙的解决这个问题。
这里需要理解的特征就是0&0=0,0&1=0,1&0=0,1&1=1，即0&x=0,1&x=x，这里x为0或1，假如说有一个二进制数0b00100000，其中有一位是1，我们不妨让这个数减1，则数变成了0b00011111，这两个数&一下，就变成了0b0。我们可以发现一个规律，如果一个数为n，则n & (n - 1)可以消去数中最右面的1。
有了上面的思路，我们可以设计出新的解决方案，不断的消除数中最后一个1，并统计个数，直到这个数变为0。
斐波那契数列
另一类比较典型的问题就是斐波那契数列的问题了
面试题10：斐波那契数列
题目一：求斐波那契数列的第n项
写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下：
f(0)=0,
f(1)=1,
f(n)=f(n-1)+f(n-2),n>1
实际上，斐波那契数列，是一个典型的递归题。比如，我要计算f(10)的值，则可以递归到f(8)+f(9)，而f(8)和f(9)都可以分别递归，直到f(0)或f(1)。这种思路显然是可以解决这个问题的。但是，这种简单的处理，计算量是非常庞大，而且有很多不必要的重复的。
为什么这么说呢？我们看看下面的推导：
f(10) = f(8) + f(9)
f(9) = f(7) + f(8)
f(8) = f(6) + f(7)
f(7) = f(5) + f(6)
f(6) = f(4) + f(5)
f(5) = f(3) + f(4)
f(4) = f(2) + f(3)
f(3) = f(1) + f(2)
f(2) = f(0) + f(1)
f(1) = 1
f(0) = 0
从中我们可以看出，中间，有大量的重复项，我们在计算的时候，如果每一项都是采用递归的方案，显然会多计算很多。比如在计算f(10)的时候，需要首先计算f(8)的值，而计算f(9)的时候，也需要计算f(8)的值，这样，f(8)实际上被计算了两次，但实际上这是没有必要的。
我们在解决递归相关的问题时，往往分析的时候，是自上而下的，比如刚才的分析，就是为了计算f(10)，我们首先需要计算f(8)和f(9)，为了计算f(8)，首先需要计算f(6)和f(7)等等。这些都是自上而下的分析。但是如果在实际计算的时候，也采用自上而下的方案，就会产生不必要的浪费。因此在计算的时候，我们采用自下而上的方案，也就是说从f(0)和f(1)推导出f(2)，由f(1)和f(2)推到出f(3)等等。这个推导的过程是自下而上的，这样做的好处是，可以利用历史的计算信息，这样，就不会产生同一个值被计算两次的情况了，从而化简了计算复杂度。
小结
本章介绍了一些其他技巧，比如在计算二进制中1的个数的时候，我们可以利用n & (n - 1)可以消掉最右边1的特征，进行分析计算。还有在分析递归类型问题时，我们采用自上而下的方案，而在具体计算的时候，我们采用自下而上的方案，这样，可以使用历史计算数据，从而减少不必要的计算。
至此，算法题小结这一系列就到此结束了。后面如果还有新的心得，我再在后面做补充。
网友评论