MyMSDN

编程之美P117学习笔记

编程之美P117 -

1. 求二进制中1的个数（P119）
   1. 除以一个2，如果有余，则有一个1，如果没有余数，则有一个0；
   2. 位运算，循环右移，当前值&0x01，要么为0，要么为1，求和，即可得1的个数；
   3. 位运算，二进制-1，将会使最靠右的一个1消失，使其右边那个0（如果存在的话）变1，然后与原数做&运算，结果如果非0，则说明还有1存在；
   4. （低效）switch运算，直接给出答案0～255（可求8位二进制）；
   5. （神效）将结果放入int[256]中，直接查表即可，时间复杂度O(1)
2. 阶乘，给定一个整数N，那么N的阶乘N!末尾有多少个0呢？例如：N=10，N!=3628800，N!的末尾有两个。（P126）
   1. N!中0的个数就是10的个数，因为10 = 2×5，由于2可能出现的个数肯定比5要多很多倍，所以只要计算含有5的个数即可。所以方法1就是%5（对5取余数）；
   2. 原理同方法1，但是计算方式不同，一个数假设是250由几个5相乘呢？

      等价于

      因为5⁴ >250，也就是最后一个加号以后的数在计算机的整数除法中均为0，因此只有前三个有效。

      等价于

      它们分别可以解释为：

      1…5…10…15…25…30……250

      ：每间隔5，一共有多少个数，其结果也就是整除5的结果

      ：每间隔25，一共有多少个数，其结果也就是整除25的结果，因为之前这些数已经参与了含有5的计算，因此，现在整除25也就是整除5×5，则表示它有两个5相乘。

      依此类推，即可得出5的个数。

3. 求N!的二进制表示中最低位1的位置。
   1. 同上一题一样的方式解，把5换成2即可。题目的意思也就是类似，二进制的末尾0表示含有2的个数（类似上题含有5的个数）所以最后一个1的位置必然等于0的个数+1；更高效一点的就是上一题需用/5的做法，而这一题用>>=的做法就可以实现/2的效果了，而移位比除法要高效得多；
   2. N!含有质因数2的个数，还等于N减去N的二进制表示中1的数目。（具体分析见P128）
4. 1的数目

   给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有1的个数。

   1. 遍历每个数，求每个数含有1的个数，但效率低，时间复杂度为O(N*log₂N)
   2. P115
5. 数组int array[]中，最大的N个数。
   1. 排序？但是数字一大肯定不可以。
   2. 快速排序法，时间复杂度O(N*log₂K)，因为是求K个数，而快速排序一次可以将数分成两组，最佳状态是一次就将其分成两组{K}X{N-K}，其中X为参考数值。
   3. 二分搜索法
   4. 用容量为K的最小堆来做，使堆顶的元素是K个数中最小，然后其他数进行比较，如果比堆顶的大就替换最小的数，并重新排序堆，……，最后堆中的数据就是所要地数据了。
   5. （快，但是受限）将每个数出现的次数记录一下，假设有3、8、10，每个数出现的次数分别是2、7、3，那么假设K取5，则分别是{10、10、10、8、8}。
6. 最大公约数
   1. 辗转相除法
   2. 求差判定法，用减法代替方法1中的取模运算，但增加了迭代次数
   3. 根据f(x,y) = f(p*x1,y)=f(x1,y)，用移位的方式除2（>>=）

       

posted on 2009-05-03 20:47 volnet 阅读(261) 评论(0)  编辑 收藏 引用