《编程之美》
《编程之美》之前有看过，不过看完之后不仅啥也没记住，反而是把自己绕得一团晕，重读《编程之美》也是想重新梳理一下算法中的逻辑，并试图找出那些所谓“美”的算法的共性，同时也希望能够结交一些有着共同爱好的童鞋。好了，废话到此，咱们开始吧。
1、题目：对于一个字节（8bit）的变量，求其二进制表示中 “1” 的个数，要求算法的执行效率尽可能高。
解法一、
思路：（输入）变量为125，其二进制表示为00111111，统计该二进制表示中“1”出现的个数，可（从低位到高位）依次统计每位上“1”出现情况。
计算：
1、计算（输入）变量二进制表示中最低位数字（num % 2），若为“1”则count加1；
2、计算（输入）变量二进制表示向右位移一位值（num / 2）；
3、迭代步骤1、步骤2，直到（输入）变量值为0；
4、返回count值。
代码：
public int countNumberOne( int inputNumber) {
int retCount = 0 ;
while (inputNumber != 0 ) {
if (1 == (inputNumber % 2 )) {
++ retCount;
}
inputNumber /= 2 ;
}
return retCount;
}
注：该算法时间复杂度为O（N），N为输入变量的二进制表示长度。
解法二、
思路：解法二是对解法一的改进，对于（输入）变量只需统计“1”的出现次数即可。我们知道num & num – 1的二进制运算，是对num最低“1”位计算为“0”，特别地，若num & num – 1 = 0，则表示num为2的幂次方。因此，可直接依次（从低位到高位）统计最低“1”位个数。
计算：
1、计算（输入）变量二进制表示是否为0，若不为0，则count加1；
2、计算（输入）变量二进制表示最低“1”位值变为“0”（num &= num –1）；
3、迭代步骤1、步骤2，直到（输入）变量值为0；
4、返回count值。
代码：
public int countNumberOne2( int inputNumber) {
int retCount = 0 ;
while (inputNumber != 0 ) {
retCount ++ ;
inputNumber &= (inputNumber - 1 );
}
return retCount;
}
注：该算法时间复杂度为O（M），M为输入变量的二进制表示中“1”的个数。
解法三、
思路：因为题目要求输入变量长度为8bit，即一个字节，其取值范围为0~255。因此，可直接建立0~255中每个数字所对应“1”出现个数的关系映射表，键值（key–value）关系可简单通过数组来表示：数组下标（i）表示关键字（key），即所要查找的数字；数组值（arr[i]）表示所要查找的结果，即“1”出现个数。
计算：
1、装载关系映射表（即0~255中每个数字所对应“1”个数的映射关系）；
2、以输入数字为键值（key），查找关系映射表中该键值对应的value值，并返回。
代码：
static int [] countTable = null ;
static void loadCountTable() {
countTable = new int [256 ];
for ( int i = 0; i < 256; i++ ) {
countTable[i] = countNumberOne(i);
}
}
public int countNumberOne3( int inputNumber) {
if (countTable == null ) {
loadCountTable();
}
return countTable[inputNumber];
}
注：该算法时间复杂度为O（1），空间复杂度为O（2 ^ n），n为输入变量最大长度。
另：该算法为典型的空间换时间案例，得益于存储开销远低于计算（cpu）开销，空间换时间在计算机领域中十分常见，如：搜索引擎中的倒排索引、网站中的降级处理（如某电子商务公司在价格战中会将部分动态页面静态化，以提高响应时间）等。如果大家有什么这方面的案例，希望能共同探讨，谢谢！
分类: 读书笔记
标签: 算法 , 编程之美
编程之美【02】_续
摘要: 2、题目：从很多无序的数中（姑且假定各不相等），选出其中最大的K个数。解法五、思路：1、采用快排的分治思想，首先取无序数中一随机数，将无序数分割成1、2两部分，其中第1部分数为小于该随机数集合，第2部分数为大于该随机数集合；2、若恰好第1部分的数（加该随机数）个数为K，则直接返回前K个数即为所求；若第1部分的数个数大于K，则递归对查找第1部分数中最大K个数；若第1部分数个数小于K，则递归查找第2部分数中最大的K – length个数，length为第1部分数个数；该算法时间复杂度为O（n * log n），同快排一样，该排序算法依赖于随机数的选取，具有不稳定性。计算：1、对整个数组进行分割算法 阅读全文
posted @ 2013-01-12 00:11 @小小鸟@ 阅读(524) | 评论 (0) 编辑
编程之美【02】
摘要: 2、题目：从很多无序的数中（姑且假定各不相等），选出其中最大的K个数。解法一、思路：最直接的办法是对无序数按大小进行排序，将无序数有序化后，依次取出前K个数值即可。如排序算法为快排，时间复杂度为O（N * log N + K）解法二、思路：构造K长度的有序数组，并依次遍历每个无序数，若遍历无序数的数值大于该有序数组重的最小数值，则将该无序数数值替换掉有序数组最小数值，并重新调整有序数组的有序性。该算法时间复杂度为O（K * N）计算：1、对无序数组的前K个数进行有序化（简单采用插入排序算法）；2、遍历无序数组的第K个数至最后一个数，若遍历数值大于第K – 1位数值，则需将该数插入至前K个的有序 阅读全文
posted @ 2013-01-05 22:57 @小小鸟@ 阅读(1079) | 评论 (2) 编辑
编程之美【01】
摘要: 《编程之美》之前有看过，不过看完之后不仅啥也没记住，反而是把自己绕得一团晕，重读《编程之美》也是想重新梳理一下算法中的逻辑，并试图找出那些所谓“美”的算法的共性，同时也希望能够结交一些有着共同爱好的童鞋。好了，废话到此，咱们开始吧。 1、题目：对于一个字节（8bit）的变量，求其二进制表示中 “1” 的个数，要求算法的执行效率尽可能高。 解法一、 思路：（输入）变量为125，其二进制表示为00111111，统计该二进制表示中“1”出现的个数，可（从低位到高位）依次统计每位上“1”出现情况。 计算： 1、计算（输入）变量二进制表示中最低位数字（num % 2），若为“1”则cou... 阅读全文
posted @ 2013-01-02 14:55 @小小鸟@ 阅读(1137) | 评论 (7) 编辑
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息