BeautyofProgramming.md

浓缩版编程之美（记录主要的推导思路）
# 游戏之乐——游戏中碰到的题目
### 1.1 让 CPU 占用率曲线听你指挥
在任务管理器的一个刷新周期内，CPU 忙（执行应用程序）的时间和刷新周期总时间的比率，就是 CPU 的占用率。给定一个程序，让它在任务管理器的刷新周期时间内一会儿忙，一会儿闲，然后调节忙／闲的比例，就可以控制 CPU 占用率。
* 进程忙可以通过执行空循环来实现；
* 进程空闲通过调用sleep()实现（进程空闲情况：等待用户输入、等待事件发生、或者主动进入休眠状态）；
# 数字之魅——数字中的技巧
## 2.1 求二进制数中 1 的个数
对于一个整数，求其二进制表示中“1”的个数，有下面几种方法：
1. 除、余操作（除以2余1则当前位置为1）；
2. 使用位操作代替除、余；
3. 每次取得`最右边的 1`（仔细思考 num & (num-1)的含义）；
4. 空间换时间（给出所有数对应1个数的数组，直接读取）。
下面为方法3的代码：
while(v){
v &= (v-1);
count ++;
}
## 2.2 不要被阶乘吓倒
两个与阶乘有关的题目：
> N 的阶乘(N!) 末尾有多少个 0；
问题转换为 `N! = K * 10^M` (K不能被10整除，N!末尾有M个0)。对 N! 进行`因式分解`， N! = 2^X * 3^Y * 5^Z ... 由于 10 ＝ 2*5，所以 M = min(X, Z)。因为能被2整除的数出现的频率比能被5整除的数高很多，所以 M=Z。计算 Z 有两种方法：

1. 计算 i（i=1,2,...,N）的因式分解中5的指数，然后求和；
2. Z ＝ `[N/5] + [N/5^2 ] + [ N/5^3 ] + ...`（公式中[N/5] 表示不大于N的数中 5 的倍数贡献一个5，[N/5^2 ]表示不大于N的数中 5^2 的倍数再共享一个5）。
第二种方法实现如下：
while(N){
count += N/5;
N /= 5;
}

> N 的阶乘(N!) 中的二进制表示中最低位 1 的位置；
判断一个二进制数最后一位是否为1：
* 最后一位为0，将此二进制数右移一位，即为除以2的值；
* 最后一位为1，此二进制数是奇数，无法被2整除；
所以这个问题等同于求可以将二进制数右移多少位使最后一位为1，也即 N! 中含有质因数 2 的个数。等于 [N/2] + [N/4] + [N/8] + ...
while(N){
N >>= 1;
count += N;
}
## 2.3 寻找发帖 “水王”
无序数组中某个数出现的次数超过一半，找出该数 K。
Boyer–Moore majority vote 算法：如果每次删除两个不同的数，那么剩下的数中，K出现的次数仍然超过总数的一半。
def majorityElement(self, nums):
majority_num = 0
count = 0
for num in nums:
if count == 0:
majority_num = num
if majority_num != num:
count -= 1
else:
count += 1
return majority_num
[Majority Element](https://leetcode.com/problems/majority-element/)
[Majority Element II](https://leetcode.com/problems/majority-element-ii/)
## 2.10 寻找数组中的最大值和最小值
在长度为 N 的无序数组中同时找出最大的数和最小的数，要尽可能减少比较次数。
有下面几种解法：
1. 寻找最大值和最小值看成是独立的问题，分别求解，需要 2*N 次；
2. 用Min，Max存储当前的最小值和最大值，每次读取数组中两个数，比较这两个数，将大的数与Max比较更新Max，将小的数与Min比较更新Min。比较次数变为 1.5 * N。
3. 分治的思想：分别求出前后 N/2 个数的 Min 和 Max，然后取较小的 Min 和 较大的 Max 即可。比较次数仍然为 1.5 * N
# 结构之法——字符串及链表的探索
## 3.6 编程判断两个链表是否相交
给出两个单向链表（不带环，如下图所示），判断这两个链表是否相交。
![][2]
如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的。因此，如果它们相交，那么最后一个节点一定是共有的。时间复杂度O(Length(h1) + Length(h2))，空间复杂度 O(1)。
# 数学之趣——数学游戏的乐趣
## 4.4 点是否在三角形内
> 如果在一个二纬坐标系中，已知三角形顶点的坐标，那么对于坐标系中的任意一点，如何判断该点是否在三角形内（三角形边线上也可以）？
假设三角形顶点坐标 ABC（逆时针顺序），给定点为D。
解法一：`面积法`
把D和其他的三个点 A、B、C 连接起来，然后比较三角形 ABC 的面积与三角形 ABD、ACD、BCD面积之和的大小来判断点是否在三角形内部。
解法二：`向量法`
由于三角形是凸的，如果 D 在三角形 ABC 内部，那么沿着三角形的边界逆时针走，点 D 一定保持在边界的左边，也就是说点 D 在边 AB、BC、CA 的左边。
已知点 C 与向量 **AB**，对于向量 **AC**，**AB**：
* 如果叉积为负，则 C 在向量 AB 的右边；
* 如果叉积为正，则 C 在向量 AB 的右边；
* 如果叉积为0，则 C 在向量 AB 所在的直线上。
如下图所示：
![][1]
[1]: https://cs-offer-1251736664.cos.ap-beijing.myqcloud.com/BeautyofProgramming_1.png
[2]: https://cs-offer-1251736664.cos.ap-beijing.myqcloud.com/BeautyofProgramming_2.jpg