編程之美P117學習筆記

編程之美P117 -

1. 求二進制中1的個數(shù)（P119）
   1. 除以一個2，如果有余，則有一個1，如果沒有余數(shù)，則有一個0；
   2. 位運算，循環(huán)右移，當前值&0x01，要么為0，要么為1，求和，即可得1的個數(shù)；
   3. 位運算，二進制-1，將會使最靠右的一個1消失，使其右邊那個0（如果存在的話）變1，然后與原數(shù)做&運算，結(jié)果如果非0，則說明還有1存在；
   4. （低效）switch運算，直接給出答案0～255（可求8位二進制）；
   5. （神效）將結(jié)果放入int[256]中，直接查表即可，時間復(fù)雜度O(1)
2. 階乘，給定一個整數(shù)N，那么N的階乘N!末尾有多少個0呢？例如：N=10，N!=3628800，N!的末尾有兩個。（P126）
   1. N!中0的個數(shù)就是10的個數(shù)，因為10 = 2×5，由于2可能出現(xiàn)的個數(shù)肯定比5要多很多倍，所以只要計算含有5的個數(shù)即可。所以方法1就是%5（對5取余數(shù)）；
   2. 原理同方法1，但是計算方式不同，一個數(shù)假設(shè)是250由幾個5相乘呢？

      等價于

      因為5⁴ >250，也就是最后一個加號以后的數(shù)在計算機的整數(shù)除法中均為0，因此只有前三個有效。

      等價于

      它們分別可以解釋為：

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

      ：每間隔5，一共有多少個數(shù)，其結(jié)果也就是整除5的結(jié)果

      ：每間隔25，一共有多少個數(shù)，其結(jié)果也就是整除25的結(jié)果，因為之前這些數(shù)已經(jīng)參與了含有5的計算，因此，現(xiàn)在整除25也就是整除5×5，則表示它有兩個5相乘。

      依此類推，即可得出5的個數(shù)。

3. 求N!的二進制表示中最低位1的位置。
   1. 同上一題一樣的方式解，把5換成2即可。題目的意思也就是類似，二進制的末尾0表示含有2的個數(shù)（類似上題含有5的個數(shù)）所以最后一個1的位置必然等于0的個數(shù)+1；更高效一點的就是上一題需用/5的做法，而這一題用>>=的做法就可以實現(xiàn)/2的效果了，而移位比除法要高效得多；
   2. N!含有質(zhì)因數(shù)2的個數(shù)，還等于N減去N的二進制表示中1的數(shù)目。（具體分析見P128）
4. 1的數(shù)目

   給定一個十進制正整數(shù)N，寫下從1開始，到N的所有整數(shù)，然后數(shù)一下其中出現(xiàn)的所有1的個數(shù)。

   1. 遍歷每個數(shù)，求每個數(shù)含有1的個數(shù)，但效率低，時間復(fù)雜度為O(N*log₂N)
   2. P115
5. 數(shù)組int array[]中，最大的N個數(shù)。
   1. 排序？但是數(shù)字一大肯定不可以。
   2. 快速排序法，時間復(fù)雜度O(N*log₂K)，因為是求K個數(shù)，而快速排序一次可以將數(shù)分成兩組，最佳狀態(tài)是一次就將其分成兩組{K}X{N-K}，其中X為參考數(shù)值。
   3. 二分搜索法
   4. 用容量為K的最小堆來做，使堆頂?shù)脑厥荎個數(shù)中最小，然后其他數(shù)進行比較，如果比堆頂?shù)拇缶吞鎿Q最小的數(shù)，并重新排序堆，……，最后堆中的數(shù)據(jù)就是所要地數(shù)據(jù)了。
   5. （快，但是受限）將每個數(shù)出現(xiàn)的次數(shù)記錄一下，假設(shè)有3、8、10，每個數(shù)出現(xiàn)的次數(shù)分別是2、7、3，那么假設(shè)K取5，則分別是{10、10、10、8、8}。
6. 最大公約數(shù)
   1. 輾轉(zhuǎn)相除法
   2. 求差判定法，用減法代替方法1中的取模運算，但增加了迭代次數(shù)
   3. 根據(jù)f(x,y) = f(p*x1,y)=f(x1,y)，用移位的方式除2（>>=）

      ?

posted on 2009-05-03 20:47 volnet 閱讀(276) 評論(0)  編輯 收藏 引用