My Blog

Work hard, play hard !

Home Offline CV About

All posts in one long list

GMM模型及代码实现

on ML

上一篇EM算法中提到了李航的统计学习方法，但是没有说明书中的公式推导和Andrew Ng的区别，本文先说明两者的异同点，再说明怎样计算GMM模型和参数计算。如果你看懂了EM算法的原理，GMM模型就很好理解。但是我菜，我不会矩阵求导，式子列出来了，我解不出来，看了半天资料，才勉强看懂。

EM算法(李航统计学习方法版本)

面对一个含有隐变量的概率模型，目标是极大化观测数据（不完全数据）Y关于参数$\theta$的对数似然函数，及最大化：

有人可能有疑问，为什么这个式子和Andrew Ng推导的式子不同。其实是一样的，只不过，他这里没将$Y$展开，$Y$代表整个样本集。接下来的推导思路就不同了。

因为我们要通过迭代逐步极大化，假设在第i次迭代后的估计值是，我们希望新的估计值能使增加，即，并逐步达到极大值，为此，我们考虑两者的差：

利用Jensen不等式得到其下界：

令：$$B(\theta, \theta^{(i)})=L(\theta^{(i)})+\sum_Z P(Z Y,\theta^{(i)})log \frac{P(Y Z,\theta)P(Z \theta)}{P(Z Y,\theta^{(i)})P(Y \theta^{(i)})} \tag{4}$$

则有：

即是的一个下界，而且由式知道。将替换成 ，将条件概率展开，就能知道分母和分子相同，也就是说这个式子等于1。

因此，任何可以使增大的，也可以式增大。也就是说选择使达到极大，即：

现在来求的表达式：

书中对函数的定义和Andrew Ng的定义有些不同。后者的定义是隐含变量的后验概率，它是后者函数的一部分。我参看华校专《python大战机器学习》中的定义，它的物理意义是：完全数据的对数似然函数关于某个分布的期望。该分布就是 的真实条件概率的一个近似，由给出。再来分析一下最后求解的表达式，将Andrew Ng的式子中分母的函数（因为确定，Q函数就确定了），两者就是相同的。最后，我给出算法流程：

Repeat until convergence{

(E-step)for dataset Y, set:

(M-step)Set:

}

总的来说，两个思路是差不多的，都是想办法极大化似然函数，巧妙的运用了Jensen不等式，不同就是函数的定义，我目前也不知道那种被公认，或者两者都是自己定义的，没有一个公认的说法。

GMM模型（高斯混合模型）

我们有训练集，现在需要对训练集聚类，聚类是无监督学习，因此不需要标签。我们假设训练集的数据服从联合高斯分布，这个假设是合理的，因为自然中的数据大多符合高斯分布。现在我们来建模：

其中代表高斯混合成分，即训练集由高斯分布组合而成，代表高斯分布的权重；代表高斯分布密度， ，即代表高斯分布均值和协方差。一维高斯分布到多维高斯分布的理解，参考jermmy。

我们来理解一下数据产生的过程，首先依概率选择第k个高斯分布分模型 ；然后依第k个分模型的概率分布生成观测数据。理解了数据产生过程后，我们要找出隐含变量，观测数据是已知的，但是观测数据来自哪个分模型是未知的，我们假设隐含变量为，定义如下：

是0-1随机变量，它为1的概率就是后验概率。接下来，我们来推导参数更新的式子，这里我按照Andrew Ng的算法流程来推导，因为我觉得他思路的比较清晰，先求隐变量的后验概率，再最大化似然函数，而李航的书中，是直接求似然函数，再最大化。

E步：

又有：

M步:

现在我们对上式求导，来解出，我们一步步求导(靠，这公式真的难敲)，建议先看一下长躯鬼侠的矩阵求导术，特别是例四例五。好了，我相信你看懂了，我就不求导了，太难了。我给出最后结果：

只需要对求导就可以了，需要引入拉格朗日乘子来解决，参考Andrew Ng。另外注意到， 式中是，它这里采用了贪心的策略来极大化似然函数。

如果你看过李航统计学习方法和Andrew Ng的资料的话，你看能会想和之间有什么区别，其实它们是一样的。先来看看它们各自的意义，前者是的期望，后者是属于第$k$个分模型的概率，由于是0-1分布，这个概率就是期望。

GMM模型的应用

这里我主要说一下，它在说话人识别中的应用，代码可参见github。对于语音材料，我们首先预处理，分帧、预加重，然后提取语音特征，常用的MFCC特征，一帧语音提取13维特征。对于每一个人，我们都有了大量的数据。然后，我们对每一个人训练一个GMM模型，有n个人，就有n个模型，模型的高斯混合成分由valid数据集确定。测试阶段，对于一个新的语音，我们将它代入每一个模型，都会得到一个后验概率，概率越大，表示这段语音属于这个人的概率越大。

其中不用求解，是均匀分布，因此先验概率的大小就代表了后验概率的大小。

总结

本篇博客，先说明了李航统计学习方法中EM算法，比较了两者的异同。后又利用EM算法求解GMM模型的参数。后续，我会用python写一套代码求解GMM模型，有兴趣的话可以先参考medium和huangyc

Reference

https://towardsdatascience.com/gaussian-mixture-modelling-gmm-833c88587c7f https://www.cnblogs.com/huangyc/p/10274881.html https://zhuanlan.zhihu.com/p/24709748 http://cs229.stanford.edu/notes-spring2019/cs229-notes8-2.pdf 李航：统计学习方法 华校专：python大战机器学习

EM算法

on ML

前几天，和一个老师线上面试，我说我用GMM做过相关项目，他就顺着这条线，问了我项目的pipeline，然后问我GMM中怎样确定高斯混合成分，我就说用train数据训练，test数据确定参数，他嗯了一声，我感觉不对，模型的超参选择怎么能依靠test呢？还好在老师的引导下，想起来valid数据的作用。之后，他又问我，GMM的输出是先验概率还是后验概率？我一脸懵逼，猜了后验概率，他顺着问我，那这个模型中什么是先验概率？额，我不知道，实在没弄清楚，他评价了一句，“你们概率论学了不用吗？”。之后，又问了我卷积与梯度的相关问题，就不多说了。电话面试虽然通过了，后续面试就难了，为了好好准备面试并且说明我不是调包程序员，我要认真学习机器学习的算法了。因为GMM模型是用EM算法迭代求解的，所以我首先学习EM算法。

EM算法初识

EM算法也称为期望极大算法。它是一种迭代算法，用于含有隐变量的概率模型参数估计。EM算法的每次迭代由两步组成：E步求期望；M步求极大。求什么期望？又极大化什么呢？我们慢慢看。

通常对于概率模型的参数估计，可以使用极大似然估计法或者贝叶斯估计法来估计模型参数。但是当模型含有隐变量时，这种方法就行不通了，可以看看这篇blog来理解隐变量的含义。

Jensen 不等式

设$ f $是定义域为实数的函数，如果对于所有的实数$x$，它的二阶导，则说明该函数为凸函数。当，则说明该函数为严格凸函数。

Jensen不等式：假设是凸函数，是随机变量，则有：，其中EX为随机变量X的期望，这里简写。

如果$f$是严格的凸函数，那么上述等式当且仅当X为常数的时候取等。用图来理解这个不等式：

当$f$是凹函数的时候，不等式取反就可以了，即。

EM算法理论推导

这部分理论推导，我参照了Andrew Ng以及李航的统计学习方法，建议有能力者，直接看Andrew Ng的材料。

给定训练样本集，样本间彼此独立，我们假设隐变量为，则的密度函数为：

我们希望极大化对数似然函数，来得到参数的估计：

考虑隐变量z，式可以写成：

直接求上式的解析解是比较困难的，一是因为上式包含隐变量，二是上式涉及对数函数的求和，很难求导。在这样的背景下，EM算法给出了高效的方法来最大化对数似然函数，得到模型参数的近似解。为了后续描述方便，我们考虑一个样本的对数似然函数，整个样本集，只不过是对单一样本的求和。

我们假设是z的分布函数。即：

将式转化一下：

第一步等式转化好理解，分子分母同时乘一个，第二步不等式转化用到了前面所说的Jensen不等式。函数是凹函数，则有，将当作随机变量，当作随机变量的分布函数，就可以推导第二步的不等式。

如果我们知道,就可以直接求出。如果我们知道，就可以推导出。好了，现在和都不知道，怎么办？那就猜吧（这不是我们经常干的事嘛），我们先猜一个，也就是说，我们给模型的参数一个初始值，有了初始值后，我们想极大化对数似然函数，考虑上面我们已经推导了对数似然函数的下界，因此我们很自然的想到了水涨船高，于是极大化这个下界。不等式取等的时候，下界最大，考虑Jensen不等式取等的条件，随机变量为常数，即：

也就是说：，那么可以表示成：

也就是说当是确定时的后验概率分布，不等式取等。

为了方便，我们将式称作evidence lower bound(ELBO)，因此：

有了这个式子后，我们重写式:

EM算法就是交换的更新和。E步：在确定的情况下，根据式计算出。M步：固定，最大化，得到的更新值。回到E步。

前面的谈论都是基于一个样本的，现在考虑整个样本集：

根据式，得到：

下面给出算法：

我们怎么知道算法收敛呢？如果我们能证明，就能说明极大似然值单调递增，也就能确保收敛性了。

在第t+1次迭代E步时候，我们知道根据，确定(第i个样本Q的后验概率)，因为是根据等式取等推出来的，此时有：

在第t+1次迭代M步时候，我们知道固定，求，是ELBO极大化，则：

在第t+2次迭代的E步，有：

这就证明了算法的收敛性。

总结

我们回头看一下算法流程。我们的目的是极大化似然函数，但是由于隐变量和求和的存在导致很难直接极大化似然函数。因此，我们初始化模型参数，得到隐变量的后验概率，再固定隐变量后验概率，更新模型参数使似然函数极大化，然后根据更新的参数，再更新隐变量的后验概率。反复迭代，直到模型收敛。下一篇，我们会说明GMM模型，并用EM计算它的参数，如果有可能，我尝试撸一套纯python代码，不过，目前基本不可能，哈哈。

Reference

http://cs229.stanford.edu/notes-spring2019/cs229-notes8-2.pdf https://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html https://blog.csdn.net/liu1194397014/arti4cle/details/52766760 https://blog.csdn.net/zouxy09/article/details/8537620

排列组合问题

on summary

这一篇文章主要总结一下c++中排列组合函数，next_permutation、prev_permutation。

字典序

字典序，顾名思义就是按照字典顺序排列。例如字符串adcb，它的字典序就是abcd。

函数用法

parameters:first last（两个迭代器） return:bool类型，对于next_permutation,若存在下一个字典序（升序）排列，返回true，对于prev_permutation，若存在上一个字典序（降序）排列，返回true，否则为false。

具体细节参考它们官网。

算法分析

下面，我们分析下一个最大的数Ⅲ，来理解next_permutation的作用。 问题的分析参看链接，这里我直接给出代码。

使用next_permutation的解法：

class Solution {
public:
    int nextGreaterElement(int n) {
        if(n < 12) return -1;
        string str = to_string(n);
        next_permutation(str.begin(), str.end());
        long val = stol(str);
        if(val > INT_MAX || val <= n) return -1;
        return val;
    }
};

不使用next_permutation的解法：

class Solution {
public:
    int nextGreaterElement(int n) {
        if (n < 12){
            return -1;
        }
        string num = to_string(n);//将n转换为string型
        int numSize = num.size(), indexI = num.size() - 1, swapIndex;
        //第一步：从前往后扫描，定位到第一个降序的位置
        while (indexI > 0 && num[indexI] <= num[indexI - 1]){
            indexI -= 1;
        }
        //如果一直扫描到了首端，说明这个数已经是最大，比如“54321”
        if (indexI == 0){
            return -1;
        }
        //这里需要自减一，因为此时定位到的位置是寻找转换之前位置“12345643”第一个出现逆序的位置是字符'6'，下标需要前移一个单位定位到'5'
        indexI -= 1;
        //第二步：寻找到最小的且比num[indexI]大的元素，比如“12345643”中比'5'大的且在'5'后面的元素是'6'
        swapIndex = indexI + 1;
        while (swapIndex + 1 < numSize && num[swapIndex + 1] > num[indexI]){
            swapIndex += 1;
        }
        //第三步：将第一个逆序的元素与他后面最小的比他大的元素交换
        swap(num[indexI], num[swapIndex]);
        //第四步：将逆序位置之后的元素进行排序
        sort(num.begin() + indexI + 1, num.end());
        long long resNum = stol(num);//将结果转换为long型
        if (resNum > INT_MAX){//如果超过了int型的最大表示范围，返回-1
            return -1;
        }
        return resNum;
    }
};

感谢参考sinstar,hestyle

Reference

http://www.cplusplus.com/reference/algorithm/next_permutation/

http://www.cplusplus.com/reference/algorithm/prev_permutation/

https://leetcode-cn.com/problems/next-greater-element-iii/

https://blog.csdn.net/qq_41855420/article/details/89243466

检测单向链表上的环

on summary

算法综述

检测单链表上的环有个很经典的算法叫做”弗洛伊德判圈算法”, 也叫”龟兔算法”,时间复杂度是O(n+m),空间复杂度是O(1),其中m为环的长度。另外有一个更加高效的算法，叫做brent判圈算法。

检测单链表中的环，还可以用无序集合来解决，将节点push到集合中，检测下一个节点是否在集合中，若在，说明有环，否则无，时间复杂度和空间复杂度都为O(n)。还有一个就是标记visited，如果这个节点被访问了，就令visited为true，否则为false，若下一个节点的visited为true，则说明有环，这种方法，需要修改原始数据结构，不怎么方便，可以利用hash表存储结点的地址，判断地址是否已在hash表中，这样做和第二种方法差不多,时间复杂度为O(n)，空间复杂度为O(n)。

算法实例和代码参考：detect-loop-in-a-linked-list

龟兔算法的基本思路

原理

假设令龟、兔为指针，并且指向起点位置，兔子每次移动两个节点，乌龟每次移动一个节点。如果两者在起始节点外相遇，则说明有环。如果兔子在走到链表尾部还没有与乌龟相遇，说明无环。

环的长度

上述算法刚判断出存在环时, 龟和兔位于同一节点. 此时让兔不动, 而龟不断前进, 肯定又会相遇, 而这一次龟前进的步数显然就是环的长度length.

环的起点

还是之前所说龟兔相遇的节点, 首先兔保持原位, 而把龟置回链表起点, 然后龟和兔同时走, 每次都走一步, 经过time_b步最终再次相遇, 则这次相遇的节点就是环的起点start.

龟兔算法证明

如图所示，令起始节点为h， 起始节点到环起点距离为m， 龟兔相遇节点为p， p节点与环起点距离为n； 当龟兔相遇时 乌龟所跑距离为 S = m + n + aC（C 为环长度), 兔子所跑距离为2S = m + n + bC（因为兔子速度为乌龟2倍） 故得S = (b - a)C = m + n + aC ==> (b - 2a)C = m + n, 由此可知，m + n 为环C长度整数倍. 那么令乌龟返回链表起始节点，兔子仍在相遇节点P，两者同时不断推进直至相遇，相遇节点为环起点。因为乌龟移动距离m, 则兔子也移动距离m， 原本p 节点距离环起点为n， 由于m + n 为环长整数倍，故兔子移动到了环起点，即相遇节点为环起点。

Brent判圈算法

原理

起始令乌龟兔子指向起始节点，让乌龟保持不动，兔子走2i2i 步， 即迭代一次，兔子走2步， 迭代2次，兔子走4步等等。在兔子走每一步后，判断龟兔是否相遇，如果没有相遇，则让乌龟的位置变成兔子所在的位置，否则如果乌龟不动，则乌龟永远无法进入环内，随后进入新的迭代。循环下去，直至相遇或到表尾。

环的长度

由于乌龟一直处于兔子更改步长上限时的位置，所以更改步长上线后，兔子走了几步与乌龟相遇，则环的长度就为多少。

环的起点

Flyod判圈算法利用了乌龟和兔子的距离是环长整数倍的性质求起点，所以可以让乌龟回到起点，兔子回到距离起点环长距离的节点，随后与Floyd算法一样。

bool hasCycleBrent(ListNode *head) {
   ListNode *p1 = head;
   ListNode *p2 = head;
   int steps = 0;
   int limit = 2;
   while (p1 != NULL && p2 != NULL) {
      p1 = p1->next;
      if (p1 == p2) {
          return true;}
      ++steps;
      if (steps == limit) {
        p2 = p1;
        steps = 0;
        limit *= 2;
       }
     }
    return false;
}

leetcode题目分析

直接参考这个题：寻找重复数

Reference

https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/ http://adam8157.info/blog/2015/08/why-does-tortoise-and-hare-algorithm-work/ https://blog.csdn.net/u011221820/article/details/78821464 http://zhengyhn.github.io/post/algorithm/brent.loop/

32.最长有效括号

on summary

为了提高对动态规划的理解，我专门做了LeetCode上一些动态规划的题目，记录一下他人的思路和代码。

题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

栈解法

感谢kevin的思路。

首先，看到这题需要判断合法的括号对，很直接就能想到用栈的数据结构去实现。扫描字符串，若当前字符是’(‘则进栈，是’)’就判断栈顶元素是否存在且为’)’，若不符合则该字符串非法。

但是，这道题问的是最长有效括号的长度，所以我们的栈元素就用pair<char, int>实现，char对应当前字符，int对应当前字符的索引。在每次出栈时，用(当前索引 - 出栈元素索引 + 1)即可计算长度。

上面这种解法能够解决诸如”()”, “(())”一类的案例，但是还不够。比方说，如果遇到了”()()”的情况就没有办法了。因为除了当前的合法括号对长度以外，我们还需要把前面连续的合法括号对长度也算进去啊，但是之前的合法括号对已经出栈了，应该怎么处理呢。

我们可以从这个案例”)()()”出发来考虑。假设这里的五个字符，对应的索引分别为1,2,3,4,5. 第1个字符没有和它配对的括号，因此不合法。接着，后续的4个字符依次进栈、出栈x2、进栈、出栈x2. 这时我们发现，最长有效括号长度正好就是(当前索引 - 栈顶元素索引) = 5 - 1 = 4，这不是巧合。由于前面连续的合法括号对都已经出栈了，所以此时的栈顶元素对应的索引恰恰就是当前最长有效子串的起始点，这就是解决该问题的关键之处。

解决了关键点，后面的设计就水到渠成了。我们固定栈底元素为可能的最长有效括号串的开头，初始化为pair(‘b’, 0).当遇到括号不合法的情况时（此时栈底元素正好也是栈顶元素），更新该栈底元素的索引为当前索引。其它的设计如上所述。

class Solution {
    public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int idx = 0;
        stack<pair<char, int>> sk;
        sk.push(make_pair<char, int>('b', 0));
        for (char c : s){
            idx++;
            if (c == '(')
                sk.push(make_pair(c, idx));
            else{
                pair<char, int> p = sk.top();
                if (p.first == '('){
                    sk.pop();
                    ans = max(ans, idx - sk.top().second); 
                }
                else{
                    // 修改栈低元素的seond为当前字符串开头
                    assert(p.first == 'b');
                    sk.top().second = idx;
                }
            }
        }
        return ans;
    }
};

动态规划解法

感谢powcai

我们用dp[i]表示以i结尾的最长有效括号,注意这里是以i结尾的，不是0到i最长有效括号。

  1. 当s[i]为(,dp[i]必然等于0,因为不可能组成有效的括号;

  2. 那么s[i] 为 )

    当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；

    当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；这是为了解决”(())”类情况。

时间复杂度：O(n)

class Solution {
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0: return 0
        dp = [0] * n
        res = 0
        for i in range(n):
            if i>0 and s[i] == ")":
                if  s[i - 1] == "(":
                    dp[i] = dp[i - 2] + 2
                elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                if dp[i] > res:
                    res = dp[i]
        return res

总结

栈解法循序渐进，从特殊到一般，渐渐找到题目的解法。动态规划，是要明白以i结尾，这一点与其它动态规划有一些区别，其次就是考虑到多种情况，给出相应的解决办法。

第143场周赛

on summary

本次周赛，两个简单题，一个中等题，一个难题。我花了四十多分钟做了两个简单题，就不会做了。

比赛链接：143周赛

1104.分糖果II

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

示例 1：

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

提示：

* 1 <= candies <= 10^9
* 1 <= num_people <= 1000

idea:

创建一个列表，表示每个人分到的糖果。糖果递增分配，直到糖果分配完。

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        ans = [0]*num_people
        i = 1
        while(i<=candies):
            ans[i%num_people - 1] += i
            candies-=i
            i += 1
        else:
            ans[i%num_people - 1] += candies
            
        return  ans

1103. 二叉树寻路

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

提示：

1 <= label <= 10^6

idea:

根据label，可以知道label的层数，通过奇偶判断label在从左到右第几个，从而知道父节点是从左到右第几个，一直类推，到根节点。

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        i = 0
        while(2**i-1<label):
            i += 1
        ans = []
        # temp变量存储label从左到右的位置
        if i%2==0:
            temp = 2**i - label
        else:
            temp = label - 2**(i-1) + 1
        temp = (temp+1)//2
        
        ans.append(label)
        
        for j in range(i-1):
            #由于是从下到上，j需要变一下。
            j = i - j -1
            if j%2==0:
                ans.append(2**j - temp)
            else:
                ans.append(2**(j-1) + temp - 1)
            temp = (temp+1)//2

        # 最后将ans反转得到结果
        return ans[::-1]

1105.填充书架

附近的家居城促销，你买回了一直心仪的可调节书架，打算把自己的书都整理到新的书架上。

你把要摆放的书 books 都整理好，叠成一摞：从上往下，第 i 本书的厚度为 books[i][0]，高度为 books[i][1]。

按顺序 将这些书摆放到总宽度为 shelf_width 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelf_width），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。

每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

示例：

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。

提示：

* 1 <= books.length <= 1000
* 1 <= books[i][0] <= shelf_width <= 1000
* 1 <= books[i][1] <= 1000

idea:

这是一个动态规划问题，最优解由最优子解构成。我们从顶层开始思考，只有有一本书是，最优解就是这本书的高度，两本书时，若两者宽度和满足宽度条件，则是两者的最大值，若不满足，则是两者之和，以此类推，假设有n本书，已经得到最优解，对于n+1本书，第n+1本书单独一行，第n+1本书与第n本书一行，与第n-1本书一行···直到不满足宽度条件。最优解是其中的一个。

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        dp=[books[0][1]];n=len(books)
        for i in range(1,n):
            now=1000000000;j=i;tot=0;mx=books[j][1]
            while j>=0:
                tot+=books[j][0]
                mx=max(mx,books[j][1])
                if tot>shelf_width:
                    break
                if j>0:
                    now=min(now,mx+dp[j-1])
                else:
                    now=min(now,mx)
                j-=1
            dp.append(now)
        return dp[n-1]

感谢kayroger的代码。

1106.解析布尔表达式

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

*　"t"，运算结果为 True
* "f"，运算结果为 False
* "!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
* "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
* "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）

示例 1：

输入：expression = "!(f)"
输出：true

示例 2：

输入：expression = "|(f,t)"
输出：true

示例 3：

输入：expression = "&(t,f)"
输出：false

示例 4：

输入：expression = "|(&(t,f,t),!(t))"
输出：false

提示：

* 1 <= expression.length <= 20000
* expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
* expression 是以上述形式给出的有效表达式，表示一个布尔值。

idea:

这个问题，用栈数据结构就很好的解决了，因为括号是最高优先级，我们先计算括号里面的内容。具体做法是，遍历表达式，若字符不是”)”，就入栈，否则，对栈进行弹出操作，直到遇到一个逻辑运算符，对出栈的字符进行逻辑运算，将结果压入栈。

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        ans = []
        for c in expression:
            if c!=')':
                ans.append(c)
            else:
                temp = []
                while(True):
                    _c = ans.pop()
                    if _c=='(':
                        break
                    else:
                        temp.append(_c)
                        
                logic = ans.pop()
                if logic=='!':
                    if temp[0]=='t':
                        ans.append('f')
                    else:
                        ans.append('t')
                elif logic=='|':
                    if 't' in temp:
                        ans.append('t')
                    else:
                        ans.append('f')
                elif logic=='&':
                    if 'f' in temp:
                        ans.append('f')
                    else:
                        ans.append('t')
        if ans[0]=='t':
            return True
        else:
            return False

总结

本次周赛，比上次简单，但我还是只做了两道题，动态规划还是不熟悉，第四题的思路一开始不明朗，琢磨半天，没想明白。后续加强，动态规划的训练。

AlexNet

on summay

这一篇论文对深度学习有重大意义。因为这一篇论文的成功，使得深度学习成为‘潮流’。它首先将卷积神经网络应用于Imagenet比赛，并获得当年该比赛第一名。

摘要

作者训练了一个深度卷积神经网络，去分类120万、1000类高分辨率图片。在测试数据上，取得了37.5%top-1错误率和17.0%top-5错误率（top-1错误率就是预测第一个结果错误的比例，top-5错误率就是预测前五个结果错误的比例），作者使用深度卷积神经网络包含6千万个参数、650000个神经元、五层卷积和池化、三层全连接。为了防止过拟合，作者在训练的时候使用了Dropout。

主要内容

The Architecture

论文中给出的网络结构设计。作者还说明了，他认为网络架构上比较新奇的特征，我会就这几点做详细说明。

ReLU Nonlinearity

传统的激活函数是,它是线性的，将输入映射到（-1,1）之间，而Relu是,它是非线性的，相比于tanh，它计算更简单。作者指出，在CIFAR上达到相同error情况下，Relu激活比tanh激活快六倍。

Training on Multiple GPUs

作者使用多个GPU训练模型，主要是提高训练效率，这一点是受限于当时算力的无奈之举。分布式训练的思路可以在网络架构中看出来。这一点不多说。

Local Response Normalization

前面提到过，tanh将输入映射到（-1,1），相当于一个归一化操作，这具有很好的性质（具体有什么，我现在还说不清楚），但是Relu激活没有这一性质，因此作者提出了LRN，局部响应规整，对Relu的输出做一些约束。公式如下：

表示第i个卷积核输出中点(x,y)的值，N为卷积核的总数，n代表使用多少层卷积核的输出来规整，k,,,为经验参数。现在来简单理解一下这个公式的意思，假设有一张图片，224*224*3经过5*5*64的卷积核处理，并使用paddding保持卷积处理后尺寸不变，那么得到224*224*64，此时N=64，若n=3,对于224*224*i层，使用224*224*(i-1)，224*224*i,224*224*(i+1)对224*224*i层中每一个(x,y)进行规整。为了防止越界，求和的上下限都使用max和min进行约束。这有一个很好理解的例子。

Overlapping Pooling

我认为池化一般用来降维，消除信息冗杂。阅读UFTDL(tutorial中关于静态性的解释，我不是很理解，大家有见解的可以私信给我)，可以了解池化这一操作以及原理，一般池化是不重叠的，作者在文中提出一个重叠的池化操作，降低了错误率，作者观察到这样做，模型更难过拟合。真的是这样吗？我觉得可能只是效果好而已。

Overall Architecture

作者在论文中说输入图片为224*224*3,经过11*11*48卷积处理后，输出55*55*48，根据，可知这个结果有问题，因此输入图片应该为227*227*3。模型由卷积、最大池化、全连接组成，特别是把网络分成两部分训练，充分利用GPU。

来算一下，网络的参数，第一层卷积参数(11*11*3*48+48)*2=34944,第二层卷积参数(5*5*128+128)*2=307456,第三层卷积参数(3*3*128*192+192)*4=885504,第四层卷积参数(3*3*192*192+192)*2=663936,第五层卷积核参数(3*3*192*128+128)*2=442624,第六层全连接(6*6*128*2048+1)*4=37748740,第七层全连接(2048*2048+2048)*4=16777220,第八层全连接(2048*1000+1000)*2=4096002,总共60963612，其中卷积核参数2331464，占总参数3.8%。因此想要减少参数，需要减少全连接的参数，这是后续研究的突破点。

最后，将结构图转化一下方便理解，但是参数计算，还是得按照原图，因为它两个分支不是互相连接的，只有第三层卷积是互相连接，其它都是彼此分开的。

Reducing Overfitting

Data Augmentation

文中用了两种形式的数据增强，第一种形式的数据增强包括生成图像平移和水平反射。原始图片尺寸为256*256,随机裁剪227*227构成新的图片，并通过水平反射生成新的图片，通过这两种方法使数据集扩大2048。在测试阶段，对测试图片的四个角和中央进行裁剪，得到五张图片，对这五张图片的预测结果进行平均。

第二种形式的数据增强是图像色彩强度变换，对于ImageNet中的图像，将每一个像素点视作三维向量，使用PCA提取主成分，然后得到一个3*3的协方差矩阵和为特征向量和特征值，然后对图片的每一个像素,加一个随机扰动，其中为(0,0.1)的正太分布,这样处理使错误率下降1%。这一点我不是很明白，我不知道PCA处理后的结果是什么，怎样得到协方差矩阵？你可以参看key-deep-learning-architectures-alexnet,理解一下。

Dropout

这是Hinton的另一篇文章中提到的方法，也是目前经常用于防止过拟合的办法。在训练阶段，随机’drop’部分神经元，如下图，这能防止，同时会使迭代次数变多。对于dropout，等后续读了Hinton的文章，会补充更详细的理论。

总结

这篇文章的网络结构比较简单，但是参数达到了六千万。这给后续工作提供了一些方向，一是更复杂的网络，二是更少的参数，后续总结会逐渐涉及。另外，这篇文章提供两个提高准确率的trick–数据增强和模型融合（这两个trick也许不是这篇文章先提出了），我觉得数据增强就是想办法扩大数据集，还有点意义。而模型融合我觉得就是为了刷榜，没啥意义，融一堆模型，效果是好，但是没办法应用，个人认为就应该规定单模型。

Reference

  1. ImageNet Classification with Deep Convolutional Neural Networks by Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton, 2012
  2. http://ufldl.stanford.edu/tutorial/
  3. https://www.learnopencv.com/understanding-alexnet/
  4. https://medium.com/@pechyonkin/key-deep-learning-architectures-alexnet-30bf607595f1

Review:Deep-learning

on summary

这段时间一直在读论文，会坚持写一下论文总结，以及自己的思考。 怎样读论文，参考Summarize-a-Journal-Article

简要概括

这篇文章是三个巨头写的综述，对深度学习的一个总结。文章首先概括了深度学习在语音识别、物体识别、物体检测以及药物发现等领域的应用，之后又讨论了卷积神经网络和循环神经网络的应用与发展，最后指出未来深度学习的发展方向-无监督学习。

主要观点

  • Deep-learning methods are representation-learning methods with multiple levels of representation, obtained by composing simple but non-linear modules that each transform the representation at one level (starting with the raw input) into a representation at a higher, slightly more abstract level. With the composition of enough such transformations, very complex functions can be learned.

    作者认为深度学习就是表征学习，组合多层非线性模型来表达高层抽象的特征，层数足够的情况下，非常复杂的函数都可以学习到。

  • The conventional option is to hand design good feature extractors, which requires a considerable amount of engineering skill and domain expertise. But this can all be avoided if good features can be learned automatically using a general-purpose learning procedure. This is the key advantage of deep learning.

    这是深度学习在监督学习中如此成功的主要原因。传统的机器学习是要手工设计特征，这需要领域知识和工程技能，深度学习能自动学习特征，从而避免繁杂的特征工程。

  • Recent theoretical and empirical results strongly suggest that local minima are not a serious issue in general. Instead, the landscape is packed with a combinatorially large number of saddle points where the gradient is zero, and the surface curves up in most dimensions and curves down in the remainder. The analysis seems to show that saddle points with only a few downward curving directions are present in very large numbers, but almost all of them have very similar values of the objective function. Hence, it does not much matter which of these saddle points the algorithm gets stuck at.

    作者指出目前反向传播的困境–鞍点。梯度在鞍点处为零，这使得反向传播不能优化参数。研究表明，只有少数向下弯曲方向的鞍点非常多，但几乎所有鞍点都具有非常相似的目标函数值。因此，目标函数困在哪一个鞍点并不重要。

  • There are four key ideas behind ConvNets that take advantage of the properties of natural signals: local connections, shared weights, pooling and the use of many layers。

    First, in array data such as images, local groups of values are often highly correlated, forming distinctive local motifs that are easily detected. Second, the local statistics of images and other signals are invariant to location.

    Although the role of the convolutional layer is to detect local conjunctions of features from the previous layer, the role of the pooling layer is to merge semantically similar features into one

    这里指出，卷积神经网络的四个特点，局部连接、共享权重、池化、多层。后面一句话，给出了局部连接和共享权重的原因，最后一句话指出卷积和池化的区别。

  • A recent stunning demonstration combines ConvNets and recurrent net modules for the generation of image captions.

    卷积神经网络和循环神经网络的结合应用。

  • Deep-learning theory shows that deep nets have two different exponential advantages over classic learning algorithms that do not use distributed representations. Both of thhse advantages arise from the power of composition and depend on the underlying data-generating distribution having an appropriate componential structure. First,learning distributed representations enable generalization to new combinations of the values of learned features beyond those seen during training. Second, composing layers of representation ina deep net brings the potential for another exponential advantage.

    作者指出深度学习分布式表达的优点。

总结

  1. We expect unsupervised learning to become far more important in the longer term.
  2. We expect much of the future progress in vision to come from systems that are trained end-to- end and combine ConvNets with RNNs that use reinforcement learning to decide where to look.
  3. We expect systems that use RNNs to understand sentences or whole documents will become much better when they learn strategies for selectively attending to one part at a time.
  4. Ultimately, major progress in artificial intelligence will come about through systems that combine representation learning with complex reasoning. Although deep learning and simple reasoning have been used for speech and handwriting recognition for a long time, new paradigms are needed to replace rule-based manipulation of symbolic expressions by operations on large vectors.

作者指出，未来的重点是无监督学习、端到端学习、组合学习、注意力机制、表征学习和复杂推理结合。这些都是未来值得探索的方向，也许我也会贡献我的力量。

Reference

[1]LeCun, Yann, Yoshua Bengio, and Geoffrey Hinton. “Deep learning.” Nature 521.7553 (2015): 436-444. pdf (Three Giants’ Survey)

第136场周赛

on summary

很久没有时间写总结，拖到七月份才写，实在是懒。

1041. 困于环中的机器人

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。机器人可以接受下列三条指令之一：

“G”：直走 1 个单位 “L”：左转 90 度 “R”：右转 90 度 机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

示例 1：

输入："GGLLGG"
输出：true
解释：
机器人从 (0,0) 移动到 (0,2)，转 180 度，然后回到 (0,0)。
重复这些指令，机器人将保持在以原点为中心，2 为半径的环中进行移动。

示例 2：

输入："GG"
输出：false
解释：
机器人无限向北移动。

示例 3：

输入："GL"
输出：true
解释：
机器人按 (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ... 进行移动。

idea: 题目意思是机器人反复执行指令，判断它是否困在环中。题目中只有左转和右转，假设一次指令只有一个转向，那么要回到初始状态，要执行四次指令(360=904)。因此，我们对原始指令4，如果能回到初始状态，那么就困在环中，不是就没有困在环中。

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # 重复多次能回到起点
        instruct = instructions*4
        d = 0
        point = [0,0]
        for i in instruct:
            if i=='G':
                if d==0:
                    point[1]+=1
                elif d==1:
                    point[0]-=1
                elif d==2:
                    point[1]-=1
                elif d==3:
                    point[0]+=1
            elif i=='L':
                d = (d+1)%4
            elif i=='R':
                d = (d-1)%4
                
        if point==[0,0]:
            return True
        else:
            return False

1042. 不邻接植花

有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。

示例 1：

输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]

示例 2：

输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]

示例 3：

输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]

提示：

  • 1 <= N <= 10000
  • 0 <= paths.size <= 20000
  • 不存在花园有 4 条或者更多路径可以进入或离开。
  • 保证存在答案。

idea： 这个题比较简单，因为题目中已经说明，不存在四条或者更多路径可以进入或离开，只需要提供一个可行的方案，不用求总共有多少种方案。

  • 首先，将paths转化为字典，key是花园的序号，value是花园的路径。
  • 遍历每一个花园，查看该花园的序号是否在字典中：
    • 不在字典中，说明该花园没有路径通向其它花园，就任意种花。
    • 在字典中，遍历该花园的路径，排除已经种植的花，种上未种植的花。
class Solution:
    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
        if paths==[]:
            ans = [1 for i in range(N)]
            return ans
        
        ans = [0 for i in range(N)]
        d = {}
        for path in paths:
            if path[0] not in d:
                d[path[0]] = []
            d[path[0]].append(path[1])
            if path[1] not in d:
                d[path[1]] = []
            d[path[1]].append(path[0])
        del paths
        
        for i in range(N):
            tmp = [1,2,3,4]
            
            if i+1 not in d:
                ans[i] = 1
                continue
                
            for p in d[i+1]:
                if ans[p-1]!=0 and ans[p-1] in tmp:
                    tmp.remove(ans[p-1])
            
            ans[i] = tmp[0]
            
        return ans

1043. 分隔数组以得到最大和

给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。

返回给定数组完成分隔后的最大和。

示例：

输入：A = [1,15,7,9,2,5,10], K = 3
输出：84
解释：A 变为 [15,15,15,9,10,10,10]

提示：

  • 1 <= K <= A.length <= 500
  • 0 <= A[i] <= 10^6

idea: 这个题，就动态规划来解决。对于dp[0]，最大的就是A[0]，对于dp[1]，最大的是max(A[0].A[1])2…对于dp[i]，我们已经知道i之前数组完成分割后的最大和，考虑第i个元素独立，求dp[i-1]+A[i]，然后再考虑第i-1和i元素一组，求dp[i-2]+max(A[i],A[i-1])2，直到第K个元素。将其中的最大值赋给dp[i]。

动态规划问题，要弄清楚最优解和最优子结构，这个题的最优子结构，就是dp[i-k]是最优的。

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        if n<=K:
            return max(A)*n
        dp = [0]*n
        
        for i in range(K):
            dp[i] = max(A[:i+1])*(i+1)
        
        for i in range(K, n):
            temp = float('-inf')
            for j in range(K):
                temp = dp[i-j-1] + max(A[i-j:i+1])*(j+1)
                dp[i] = max(temp, dp[i])
        
        return dp[-1]

1044. 最长重复子串

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ““。）

示例 1：

输入："banana"
输出："ana"

示例 2：

输入："abcd"
输出：""

提示：

  • 2 <= S.length <= 10^5
  • S 由小写英文字母组成。

idea: 这题超出我理解了。我只有一个暴力解法，先两层循环，产生可能重复的字符串，然后将这个字符串去匹配，返回匹配成功的次数，这种方法，复杂度O(n^4)，所以不可取。参看JOHNKRAM

class Solution {
public:
    typedef long long ll;
    int P=998244353,P1=1000000007,base=233,base1=666;
    int h[100005],h1[100005],p[100005],p1[100005];
    set<pair<int,int>> s;
    string longestDupSubstring(string S) {
        int n=S.size(),i,j,k,l,r,mid;
        pair<int,int> o;
        for(i=h[0]=0;i<n;i++)h[i+1]=((ll)h[i]*base+S[i])%P;
        for(i=h1[0]=0;i<n;i++)h1[i+1]=((ll)h1[i]*base1+S[i])%P1;
        for(i=p[0]=1;i<=n;i++)p[i]=(ll)p[i-1]*base%P;
        for(i=p1[0]=1;i<=n;i++)p1[i]=(ll)p1[i-1]*base1%P1;
        l=0;
        r=n;
        while(l+1<r)
        {
            mid=l+r>>1;
            s.clear();
            for(i=mid;i<=n;i++)
            {
                j=(h[i]+(ll)(P-h[i-mid])*p[mid])%P;
                k=(h1[i]+(ll)(P1-h1[i-mid])*p1[mid])%P1;
                o=make_pair(j,k);
                if(s.find(o)==s.end())s.insert(o);
                else break;
            }
            if(i>n)r=mid;
            else l=mid;
        }
        s.clear();
        for(i=l;i<=n;i++)
        {
            j=(h[i]+(ll)(P-h[i-l])*p[l])%P;
            k=(h1[i]+(ll)(P1-h1[i-l])*p1[l])%P1;
            o=make_pair(j,k);
            if(s.find(o)==s.end())s.insert(o);
            else break;
        }
        string ans="";
        for(j=i-l;j<i;j++)ans+=S[j];
        return ans;
    }
};

更多解答，参看rank。

第135场周赛

on summary

前言

比赛链接：url，这是我第二次参加这个比赛，第一次做了一个题，第二个题没做出来。这一次终于看见第三个题，下次就能看见第四个题了。争取每次比赛都能总结，并从中学习。

总结

第一题

名字很高大上，三个点不在一条线上，就解决了，因此利用斜率就可以。

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        return (points[2][1]-points[1][1])*(points[1][0]-points[0][0])!=(points[2][0]-points[1][0])*(points[1][1]-points[0][1])

第二题

这个题，就是树的遍历，先遍历右节点，在根节点，最后左节点。并维护一个全局变量，表示节点的数字和。

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        global res
        res = 0
        
        def search(node):
            global res
            if node==None:
                return 
            search(node.right)
            res += node.val
            node.val = res
            search(node.left)
            
        search(root)
        return root

第三题

尝试了很久，没做出来。参考大佬的代码，学到了很多。大佬们的代码基本都是这个思路，动态规划。 1. 创建一个二维列表，dp，存储i到j三角剖分后可以得到的最低分。 2. 从2到n，遍历step 3. 从1到n，遍历i 4. 从i到j遍历，p 5. 求解从i到j，三角剖分后可以得到的最低分。

class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        n = len(A)
        dp = [[0 for i in range(n)] for j in range(n)]
        
        for step in range(2,n):
            for i in range(n):
                j = (i+step)%n
                dp[i][j]=float('inf')
                for p in range(i+1, i+step):
                    k = p%n
                    tmp = dp[i][k] + dp[k][j] + A[i]*A[j]*A[k]
                    if tmp < dp[i][j]:
                        dp[i][j] = tmp
                        
        ans = float("inf")                
        for i in range(n):
            j = (i+n-1)%n
            if ans>dp[i][j]:
                ans = dp[i][j]
                
        return ans

第四题

看了一遍，一个大佬的代码，自己做了一遍，没做出来，靠。下面解释，大佬简介的代码。 先来理解一下题目，就是移动石头，使石头连续，求解最大最小移动次数，此外，有一个限制条件，移动一个端点石头之后，该石头不能还是端点，这一点限制，后续会提到。

  • 最大移动次数：倒数第一个数与第二个数的差和倒数第二个数与第一个数差最大值，减去n-1个数的最小距离。
  • 最小移动次数：遍历i，选取一个j，使得i和j之间的差刚好小于n，将i与j之外的石头移动到，i和j之内，每个石头移动一次，就是最小的。此外要注意，特殊情况，也就是题目中的限制，用一个判断来解决，这一点很巧妙。 
    class Solution:
  def numMovesStones rt()
      n = len(stones)
      high = max(stones[-1] - stones[1], stones[-2] - stones[0]) - (n-2)
      low = float("inf")
        
      for i in range(n):
          j = i
          while(j+1 < n and stones[j+1]-stones[i] < n):
              j += 1
          now = n - (j-i+1)
          if stones[j]-stones[i]==j-i and j-i==n-2:
              now += 1
          low = min(low, now)
            
      return [low, high]

DCIC2019-消费者画像

on 原创

写在前面：这是第一次数据比赛进前排，还只身去了北京参加答辩，这对于我来说是一个起点，是一个重大转折。在北京的时候，去北大听了一节课，也有些感受，后续会提到。这篇博客，主要总结比赛经验与比赛收获。

赛题说明

赛题链接,看完后，应该知道这是一个回归问题，利用移动用户的数据来回归用户的信用分。这个问题意义在哪呢？训练集中的信用分是哪来的？其实中国移动有一套信用分评分体系，所有的信用分都是按照这个体系得到的，那我们建模的意义何在？这个问题我在北京答辩的时候得到了答案，后续会给出。

数据探索

数据探索这里不会详细讲，参考我的repo。由于数据太多了，我将数据可视化分成了几个部分，一个个来探索它们之间的关系，在这里我做的不对的就是没有按照官方的几个维度来探索，而是自己分的，这一点以后要注意。而且，数据探索应该放在查资料的后面，先查一下相关资料，对特征有一个大致了解。

特征工程

这个题的特征工程真是奇怪，怎么做都不上分。具体参考文档,以及repo答辩材料的ppt。

比赛总结

我最想写的部分就是比赛总结了。在答辩的前一天晚上，我们和福建移动的负责人聊了聊，我问了一个问题，我们这个赛题有什么意义。为什么要给出训练集的信用分，让我们去预测测试集？为什么不直接让我们建立数学模型，来给用户评分？他说：“你问了一个很好的问题，实际当中，是直接建立数学模型来给用户评分，但是这样做，我们就很难评判谁的模型好，没有一个衡量的标准。因此我们给出一个标准，这个标准实际意义不大，不是说谁拟合的好，谁的模型就好，但是比赛有比赛的规矩，我们也不能完全抛开比赛的规矩，分数高的，优势自然也大。”我想了想，他说的确实有道理，标准存在的意义就是约束我们的模型，毕竟他们的标准用了这么久，肯定是有很大意义的，所以我们要在标准的基础上，做出我们的思考与创新，后来他提到，他们有两千多维数据，而且不断的有流水更新，给我们的只是其中30维，这是方便我们处理。这么一说，我觉得这个题没啥意义，数据的维度增多，思维也应该转变，不能再像小数据那样思考问题了，而且在实际业务中，还要考虑更多问题。

再来总结一下一些技术收获：

  1. 数据分布的处理：对于不是正态分布的数据，对其做对数变换，从而转变成近似正太分布。变换后，需不需要取整还需要进一步验证。
  2. 特征交叉：对于bool类型特征，几个特征交叉，产生新的特征。
  3. 模型融合：stacking策略有时候不如线性组合。
  4. 五折交叉：五折交叉时，随机抽样与分层抽样的区别。

旅途感想

这次出行，感谢女朋友的鼓舞，让我有勇气上台答辩，也感谢朋友的招待，让我在北京的玩了几天，感谢骆高，让我有机会去北大听课。在北大听了一节算法分析与设计的课，刚好老师讲的线性规划，我暑假学过，但是还是没怎么听懂，知识不记得了，不得不说，这个老师也是念ppt，和武大一些老师一样，下面的学生也有玩游戏的，也有睡觉的（其他人我不知道，反正我睡了十几分钟）。这么一看，武大和北大课堂除了北大教室特别新以外没什么区别，那么他们为什么如此厉害？

我想有几点：

  1. 学生优秀，自主学习能力强。
  2. 环境压力大，科研氛围浓烈。举个例子，食堂有几块显示屏，播放学校一些实验室的牛人。
  3. 实验室对本科生比较好，只要你愿意，就可以来实验室，进项目组，项目组也会投入精力到你身上。
  4. 他们的食堂好吃，吃好了才能好好学习。（这是玩笑，哈哈）

回程的前几个小时，我还去了中关村，去看了看微软大厦（对它念念不忘）:

进了一号楼，去问了前台能不能参观，她说不能，我就打道回府了。

微软亚洲研究院，我会回来了，明日之星，我会来的。丹棱街，等着我

奉上相册

python语音处理

on 原创

这是一篇python语音处理基础指南，旨在安装python以及一些语音包。

python安装

python安装，推荐使用anaconda,它与matlab十分相似，对matlab使用者很友好。此外，anaconda预装了很多库，例如科学计算需要的numpy、pandas，机器学习需要的scikit-learn，对初学者很友好，深度学习库需要自己安装，十分简单，后续会介绍。

安装过程中，它会提示你是否安装vscode，建议安装，这个开发环境十分的简洁，后续python熟练后，就可以抛弃anaconda自带开发环境spyder，转向vscode，另外也可以转向pycharm，后者强烈推荐。

安装完成后，它会安装四个东西，如下图：

anaconda navigator:图像化环境管理工具，可以通过这个安装库，比较方便，可以批量安装，缺点就是很多库没有，因为它是通过Anaconda Cloud搜索库的，本篇blog不使用这个。

anaconda prompt:一个终端，类似于windows的cmd。这里用这个安装库，先打开它，不输入任何命令，后续使用。

spyder：anaconda自带的集成开发环境。

jupyter-notebook：十分强大的工具，网上很多代码教程使用这个。它可以让你在浏览器中写代码，对于数据挖掘来说，要学会使用它，能极大的帮助完成数据可视化任务。这里不介绍

pip 与 conda介绍

在安装库之前，先来介绍一下pip与conda，不多说，上链接，点我.

语音库

这里使用pip安装，conda安装也差不多。具体安装：pyAudio,pyAudioAnalysis，DTW. 先到pypi,搜索需要安装的包，例如搜索pyAudioAnalysis:

点击search，就能得到搜索结果，在结果中选择你需要的库，点击进去：

注意：右边latest version要留意，有时候不是最新版，需要自己点击一下，这个作者有点懒，没有给文档。一般这些库，都会在github上放源码，注意左下角的Homepage。

复制pip install xxxx 这行代码，前面打开了anaconda prompt，直接将代码复制执行即可。 如果成功了，那就可以调用试试了，没有成功的话，两种解决办法。

  1. 百度谷歌找解决方案，要相信不是你一个人踩坑。
  2. 点击Homepage，到它的官网看一下说明，有时候他会要求一些依赖库，按照它的说明，安装依赖。

遇到bug，按照上述两种方法解决。

安装过程中，会出现hmmlearn不能编译，参考这个安装hmmlearn 安装,注意修改你安装的hmmlearn版本，就可以。

深度学习库（可选）

前面提到深度学习库，这里就安装一下，目前深度学习有几个流行的库，tensorflow、pytorch等等，这里以tensorflow为例。 安装tensorflow之前，先到它的官网瞅瞅，点这里,好了，你自己看官网安装吧，哈哈。 之前看到过，说用conda安装tensorflow会好些，点这里。

怎样使用Jekyll Writer

on 原创

用markdown写blog不方便管理，每次写完都要再次提交，有点麻烦，Jekyll Writer解决了这个问题。

下载Jekyll Writer

点击这里,或者自行百度。

使用

下载完后，就来使用它。

解压文件，点击文件里面Jekyll Writer.exe。点击Account，会看到github的图标。

点击github

上一步完成后，会出现一个token，点击create token，会自动链接到你的github，按照下图创建创建一个token。

将生成的token复制粘贴到Jekyll Writer。就会出现你的账户，扫描你的repo，会自动找到你的网站repo，现在就可以在Jekyll Writer中写文章，并直接上传到自己的网站了。

梅尔倒谱系数

on 原创

Mel Frequency Cepstral Coefficient (MFCC)

这是我写的第二篇博客，这篇博客主要介绍MFCC，也是总结目前所学的《语音信号处理》知识。

很多语音自动识别系统（ASR）中，第一步就是提取语音特征，提取特征是为了提取语音中具有分辨性的信息，去除情绪、噪声等。

为了理解语音模型，我们先来理解一下声道模型。

MFCC特征在语音识别系统中广泛使用。它由Davis和Mermelstein在二十世纪九十年代引入，并成为state-of-art，当然，后续的深度学习是另话了。在MFCC此之前，还有LPCC特征，下一篇文章将介绍LPCC。

什么是MFCC，怎样计算它?

首先，给出MFCC的计算过程，后续会具体说明每一步。

  1. 将信号分帧，这是所有语音处理的第一步.

  2. 每一帧做DFT变换，得到离散频谱.

  3. 计算梅尔滤波器组，对信号滤波，并计算每个滤波器滤波之后的能量总和.

  4. 对所有的能量总和取对数.

  5. 对上述的对数能量做DCT变换.

  6. 保留DCT变换后，前12-13个系数，即为梅尔系数.

得到梅尔系数后，通常会取一阶差分和二阶差分作为动态特征，一帧的总能量也会作为特征。

具体步骤

信号分帧

第一步，对信号分帧（分帧是为了方便处理）。通常一帧20-40ms（标准的是25ms),对于16k采样率来说，也就是320-640个采样点，每一帧10ms,步长也就是160个采样点。

离散傅里叶变换

第二步，对每一帧信号做N点离散傅里叶变换，N=512,取前257个系数。

其中h(n)是N个点的窗，比如汉明窗、矩形窗等,K是DFT的长度。然后计算每一个频率的能量，并归一化：

设计梅尔滤波器组

第三步，计算梅尔滤波器组。通常设计20-40个三角滤波器（一般设置26个），假设设计$m=26$个三角滤波器，也就是说得到（26，257）的矩阵，将滤波器矩阵装置，与信号的能量相乘，就会得到26个系数。这26个系数表示信号通过每个滤波器之后，剩余的能量。下图为梅尔滤波器组：

下面具体说明，怎样得到梅尔滤波器组。先说明什么是梅尔频率，梅尔频率是基于人类听觉实验的。实验表明，相较于高频，人类的听觉对低频变化比较敏感，它与频率的转换关系如下：

将梅尔频率转换成频率：

要设计梅尔滤波器组，首先确定高频上限和低频下限，对于采样率为16K的语音信号而言，上限为$f_h=8000HZ$，下限设为$f_l=300HZ$即可（上限频率为采样率1/2）。得到上下限后，利用梅尔频率转换公式，将上下限频率转换成梅尔频率，$f_{mh}=2834.99 Mels, f_{ml}=401.25 Mels$, 再计算梅尔频率间隔，$\Delta = \frac{f_{mh} - f_{ml}}{m}$，这里m为滤波器的个数，为了方便，这里$m=10$，便得到：

m(i)=401.25, 622.50, 843.75, 1065.00, 1286.25, 1507.50, 1728.74, 1949.99, 2171.24, 2392.49, 2613.74, 2834.99

利用频率转换公式，将上述梅尔频率转换成频率：

h(i) = 300, 517.33, 781.90, 1103.97, 1496.04, 1973.32, 2554.33, 3261.62, 4122.63, 5170.76, 6446.70, 8000

然而，并没有按照上述的精确频率设计滤波器，而是将这些频率映射到最近的DFT频率。映射如下：

其中K为DFT的点数,samplerate为采样率， floor为向下取整。得到：

f(i) = 9,16,25,35,47,63,81,104,132,165,206,256

最后我们根据$f(i)$设计滤波器组，第一个滤波器从第一个点开始，在第二点达到峰值，在第三个点回到零。

这就是梅尔滤波器组。

对数变换

第四步，对第三步的26个系数取对数，为什么要取对数呢？这里面涉及到同态语音信号处理，目前不了解，后续涉及到会单独总结。

离散余弦变换

第五步，对第四步的结果做离散余弦变换DCT，得到倒谱系数。对于ASR来说，只有前12-13个系数被保留，这个系数就叫做梅尔倒谱系数。

参考

guide-mel-frequency-cepstral-coefficients-mfccs

利用github创建博客网站

on 原创

我们为什么要写博客？一直以来，我都是看着别人的博客，学习新的知识，现在我想记录我学的知识，利用博客的形式，将知识总结归纳一下，为了自己也为了他人。当然，我写博客，也为了装逼，大佬都写博客，我怎么能落后呢？玩笑归玩笑，说点正经的。我既然写博客，就会认真写，会对我所涉及的知识负责，对他人的版权负责，这一点我会恪守。

利用github创建博客网站

现在有很多可以创建博客的网站，CSDN、简书、博客园等等，不是我说，CSDN是真的乱，简书还不错。不过，我这里用github创建，比较简单。

注册github账号

这一点不多说，当代大学生必备技能。

创建一个repo

这里创建的repo名字有些讲究，一定要与你的github账户同名，格式：账户名.github.io。创建完了之后，就先不管这个repo。

寻找你喜欢的主题

jekyllthemes上寻找你喜欢的主题， 然后有好几种方法将这个主题为你所用：

  1. 将它download下来，然后上传到你的github。

  2. 找到这个主题的github地址，然后fork到你的repo

  3. 就是下载github客户端，将你的项目clone下来，将整个主题文件放在你的repo目录下，上传即可.

修改主题

主题里面需要修改一些东西，主要是配置文件的修改，每个主题的修改各不相同。所以这一块就得靠自己去找找主题的说明，一般都在样例博客里面会有说明，照着他修改就好，到这，就搭建成功，来访问我的blog吧！

参考

  1. 手把手教你在Github上建立自己的个人博客网站

  2. 我是如何利用Github Pages搭建起我的博客，细数一路的坑