2018-05-18

《算法》

跳跃游戏

1. 思路分析

最远的跳跃距离为i+s[i]
因为最远可以跳到i+s[i]，所以可以跳的位置可以表述为：i+1， i+2，i+3，.... ，i+s[i]
上述的这些位置中，从i位置跳到哪一个位置最合适？
假设跳的位置为j，那么j应该是上述位置中在该位置又能跳的最远

2. 举例如下：

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号位置为最合适的位置

3. 代码实现

    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;

    }

《机器学习》

朴素贝叶斯分类器

1. 公式推导

• 一条数据x，具有特征x₁，x₂，x₃ ...，该条数据属于某一个分类的概率为可表示成：

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(x_n|c)可以根据给定的数据集直接求出，方法见图3。

图3. 条件概率中每个值的计算

还需要求出P(x)的值才可以求得P(c|x)，但是由于我们要确定x属于哪个类别c，为此对于每一个类别来说P(x)都是相同的，为此可以不用求，就可以比较对于x属于不同的分类的时候P(x|c)的值的大小，根据贝叶斯决策理论，值最大的即为数据x的分类。