《算法》
跳跃游戏
- 思路分析
最远的跳跃距离为i+s[i]
因为最远可以跳到i+s[i]，所以可以跳的位置可以表述为：i+1， i+2，i+3，.... ，i+s[i]
上述的这些位置中，从i位置跳到哪一个位置最合适？
假设跳的位置为j，那么j应该是上述位置中在该位置又能跳的最远
- 举例如下：
s = [2, 3, 1, 1, 4, ...]
s中的每个位置能跳的最远位置为f
f = [2, 4, 3, 4, 8, ...]
在i=0位置能跳到1和2两个位置:
* 如果跳到1号位置在1号位置最远可跳4个位置；
* 如果跳到2号位置，在2号位置最远可跳3个位置
* 4 > 3所以跳到1号位置为最合适的位置
- 代码实现
bool canJump(std::vector<int> &num)
{
// 构建能到达的最远的位置的数组
std::vector<int> index;
for (int i = 0; i < num.size(); i++) {
index.push_back(num[i] + i);
}
int jump = 0;
int max_index = index[0];
while (jump < index.size() && jump <= max_index) {
if (max_index < index[jump]) {
max_index = index[jump];
}
jump++;
}
if (jump == index.size()) // 如果jump到达数组末尾，则返回true
return true;
else
return false;
}
《机器学习》
朴素贝叶斯分类器
- 公式推导
- 一条数据x，具有特征x1，x2，x3 ...，该条数据属于某一个分类的概率为可表示成：
P(c|x) = P(c,x)/P(x) (1）
上式即为要求的目标
根据贝叶斯定理，上式可以转换成下式：
P(x|c) = P(c, x)/P(c) （2）
可以推导出：
P(c, x) = P(x|c) * P(c) (3)
将(3)带入式子(1)中，可以得到：
P(c|x) = P(x|c)*P(c)/P(x) (4)
其中：P(c)为先验概率，P(x|c)为条件概率，称为“似然”，P(c|x)称为后验概率。
-
如何求(4)式中的P(x|c)和P(c)？
先验概率P(c)可以根据训练数据集直接求出来，方法见图1。
图1. 先验概率计算
条件概率P(x|c)怎么求？朴素贝叶斯假设各个特征之间相互独立，为此根据全概率公式可以得到：
图2. 条件概率计算
在该式子中，P(xn|c)可以根据给定的数据集直接求出，方法见图3。
图3. 条件概率中每个值的计算
还需要求出P(x)的值才可以求得P(c|x)，但是由于我们要确定x属于哪个类别c，为此对于每一个类别来说P(x)都是相同的，为此可以不用求，就可以比较对于x属于不同的分类的时候P(x|c)的值的大小，根据贝叶斯决策理论，值最大的即为数据x的分类。
