编程之美简要笔记 day1¶

1.1 让cpu占有率曲线听你指挥

思路概括，在程序中设定两种状态，一种是忙，例如死循环，一种是闲，例如sleep。程序设定死循环，如果cpu占用率高于设定值，则闲，反之则忙，至于如何获得占有率，调用api–PerformanceCounter。

评价：这一节难度基本集中在api调用上，你以为他会讲什么深入内核的东西，然后他调用了一个你不了解的api用很简单的思路实现了，学不到什么算法思路上的东西。

2.1 求二进制数中1的个数对于一个8bit的无符号整形变量，求求二进制数中1的个数，要求执行效率尽可能高。

思路1：位操作比较

int Count(BYTE v) 
{ 
 int num = 0; 
 while(v) 
 { 
 num += v & 0x01; //最后一位如果为1则num++
 v >>= 1; 
 } 
 return num; 
}

思路2：查表经典以空间换时间

/* 预定义的结果表 */
int countTable[256] = 
{ 
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 
 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 
 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 
 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 
 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 
 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 
 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 
 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 
 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 
 7, 6, 7, 7, 8 
}; 
int Count(BYTE v)) 
{ 
 //check parameter 
 return countTable[v]; 
}

8bit一共就255中结果，全列出来，时间复杂度为 O(1)。

心得：值得学习的思路只有这两种。

2.3 寻找水王问题的实质是在一个数组中出现最多的那个值，这个值出现次数超过了数组的一半。

思路：每次在数组中删除两个不同的值，把问题分解成更小的问题。

Type Find(Type* ID, int N) 
{ 
 Type candidate; 
 int nTimes, i; 
 for(i = nTimes = 0; i < N; i++) 
 { 
 if(nTimes == 0) 
 { 
 candidate = ID[i], nTimes = 1; 
 } 
 else 
 { 
 if(candidate == ID[i]) 
 nTimes++; 
 else 
 nTimes--; 
 } 
 } 
 return candidate; 
}

心得：虽然思路看上去很简单，但每次删除两个不同的值如何实现呢，这就是这个算法奇妙和值得学习的地方，算法用两个变量记录遇到的第一个值和它的出现次数，向后遍历过程中，如果元素和它值相同，则出现次数加1，反之减1，这个遇到不同的值就减一的操作的意义就是删除了两个不同的值，很厉害。

2.5 寻找最大的K个数

在各不相等的一个数组中选出最大的K个数。

思路1，快排or堆排序，时间复杂度为O(N*logN)

思路2，半截快排，对数组划分后判断数组大小和K的关系，如果K>=len,则需要返回较大划分中的K个。如果K<len ，则需要返回较大划分和较小划分中的K-len个。

Kbig(S, k): 
 if(k <= 0): 
return [] // 返回空数组
 if(length S <= k): 
return S 
 (Sa, Sb) = Partition(S) 
 return Kbig(Sa, k).Append(Kbig(Sb, k – length Sa) 
Partition(S): 
 Sa = [] // 初始化为空数组
 Sb = [] // 初始化为空数组
 Swap(s[1], S[Random()%length S]) // 随机选择一个数作为分组标准，以
// 避免特殊数据下的算法退化，也可
// 以通过对整个数据进行洗牌预处理
// 实现这个目的
 p = S[1] 
 for i in [2: length S]: 
 S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i]) 
// 将 p 加入较小的组，可以避免分组失败，也使分组更均匀，提高效率

length Sa < length Sb ? Sa.Append(p) : Sb.Append(p) 
return (Sa, Sb)

思路3，一个很诡异的二分搜索，假设整数范围是0~2^(n-1),根据其二进制第n-1位的情况对数组进行划分，如果n-1位为1的数量>K,则在为1的数中向第n-2位划分，否则在为0的数中找第K-num大的数字(num为n-1位为1的数字数量)

评价：后面还提了一个假如数组很大的情形，其实就是外部排序，归并排序+败者树，故弄玄虚，但是我专业书籍都放在学校，这部分内容忘了，淦。

2.6 精确表达浮点数

问你一个有限小数或者无限循环小数怎么表达成分数。这里只摘取无限循环小数部分表达成分数的推导。另Y=0.(abababab…..) 10^n*Y=ababab.ababab… (10^n - 1)*Y=ababab Y=ababab…/10^n - 1

2.7 求最大公约数这里有几个数论里的定理，x和y的公约数与x和x-y相同，x和y的公约数与yy和x%y相同。思路1：辗转相除

int gcd(int x, int y) 
{ 
 return (!y)?x:gcd(yx%y) 
}

思路1强化：利用2分析x和y 各自为奇偶数的四种情况，利用移位运算和减法运算避开大整数除法。

BigInt gcd(BigInt x, BigInt y) 
{ 
 if(x < y) 
 return gcd(y, x); 
 if(y == 0) 
 return x; 
 else 
 return gcd(x - y, y); 
}

2.8 找符合条件的整数给定一个正整数N，求一个最小的正整数M(>1)，使N*M的十进制表示里面只含有1和0.

评价：和余数相关的数论和动态规划，后半夜看数论部分看的头痛。这部分没有完全理解，不再粘贴代码。

2.11寻找最近点对

思路：分治法，先水平方向x=m将点等分为left和right,结果只可能出现三种–最近点对在left，right，或者一个在l一个在r。由于我们已经知道l和r中的最近点对距离(递归出来的)，另MD=min(lmin,rmin)，则第三种情况的点只可能出现在x坐标在(m-MD,m+MD)之间的带状区域，根据Y坐标对带状区域点排序，如果有距离小于MD的点对，则它们一定在一个水平长度为2MD，竖直宽度MD的矩形区域内，且左右两个正方形内最多只能含有4个点(否则矛盾),所以一个矩形区域内最多有8个点。对于一个带状区域内的顶点，只需考察它与按Y坐标排序且紧接着的7个点之间的距离就可以。根据这个特点，可在O(n)时间内完成带状区域内查找(这一步可用归并排序),整个算法的时间复杂度为O(NlogN).

心得：这个题目让独立做很吃力，不愧是三星的题目，但跟着思路还是可以尽快掌握的。