归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void merge(int a[], int n, int b[], int m, int c[]) {
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m) {  
        if (a[i] < b[j]) c[k++] = a[i++];  
        else c[k++] = b[j++];   
    }  
    while (i < n) c[k++] = a[i++];  
    while (j < m) c[k++] = b[j++];  
}  

可以发现合并有序数列的效率是非常高的,有O(N)此时N = len(a)+len(b)。

加上一点分治的想法:
mergesort1

从而对于一个数组,我们可以如下的方式二分分治:
mergesort2

如上图所示,最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次… Read the rest

题目

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

Note:题目没有说明,但是边界条件 size num.size() or size <= 0,都需要直接返回空的vector。

四种解法

  1. 暴力,时间复杂度O(n*size)
  2. 线段树,时间复杂度O(nlogn+nlogn)
  3. 用两个优先队列,一个容纳size中的元素pq1,一个容纳已滑动删除的元素pq2。每次滑动时,看当前元素t和pq1.top()的大小,如果相等,则弹出,否则加入pq2。时间复杂度为O(n logn)
  4. 维护一个单调队列,单调队列模板题,维护滑动区间的区间最值。时间复杂度O(n)

不会单调队… Read the rest

前言

欧几里德算法作为有着非常简短的实现的算法,可能很多初学者(包括当时的我)都不求甚解。本文给出了GCD、LCM的性质,以及欧几里德算法的实现、证明和时间复杂度推导。

什么是欧几里得算法

最大公约数问题是最早被研究的算法问题之一了,并且是ACM竞赛中能涉及到的很多数论内容,比如模线性方程,模线性方程组的基础。

欧几里得算法 (Euclidean algorithm) ,即大部分选手所知的“辗转相除法”,其核心在于不断将两数规模变小,最后实现对数时间内求解两个数的最大公约数。

其核心是:\[gcd(a,b) = gcd(b, a \% b)\]

名词解释

  1. 最大公约数:即最大公因子,能够同时整除a和b的最大因子,记作gcd(a, b),或gcd
  2. 最小公倍数:能够被a和b整除的最小数,记作lcm(a, b),或lcm。
  3. %:指的是取余运算(取模运算),用例: a % b
  4. |:指的是整除运算,a | b表明a可以整除b,即a是b的因子

GCD和LCM的一些性质

  1. a, b都能分解为有限个素数的积
  2. gcd(a, b)中只含a,b的全部公共素因子
  3. lcm(a, b)中含有a,b的所有素因子
  4. \(gcd\%lcm=0\)
  5. \(gcd
Read the rest

什么是哈夫曼树

给定n个权值,作为n个叶结点,构造一棵二叉树,而这棵树的特点是,有n个叶节点,叶节点的值为给定的权值。而内部节点的值为子树的权值和。

这样的二叉树有很多,但树的带权路径和达到最小,则这棵树被称为哈夫曼树。
huffman tree 1

Note:带权路径和指的是所有叶节点的权值*深度和,即\(\Sigma value∗deep=100+2∗50+3∗20+3∗10\)

而我们不妨让内部节点的值为子树的权值和,我们可以发现,实际上一棵树的带权路径和=这棵树的所有节点值之和-根节点的值。(显然)

哈夫曼树有什么用

哈夫曼树主要应用在文本编码上。我们考虑如何将文本中出现的单词编码为二进制数(01串),让文本的总长度最小。

对于文本{1, 1, 2, 2, 3, 3, 3, 5},我们可以将单词1、2、3、5出现的频率作为叶节点的权值,为{2, 2, 3, 1}。那么上述最短编码问题等价于寻找一棵树,其带权路径和最小,也就是找对应的哈夫曼树。

唯一可译码

如果我们直接将单词按照频率的从高到低排序,不就得到了一个编码了吗?

但这样的编码不是一个“唯一可译码”,即对于10001010100101,我们不… Read the rest

CodeForces 1009 div2 ABCD / Educational Codeforces Round 47 div2 ABCD

A Game Shopping

一眼题,随便以一个文本作为基础,扫描另外一个即可

/**
 * @Date:   16-Jul-2018
 * @Email:  zengsw_study@qq.com
 * @Filename: A.cpp
 * @Last modified time: 17-Jul-2018
 * @Copyright: Copr. 2018 EndlessLethe. All rights reserved.
 * @Description:
 */

#include <stdlib.h>
#include <iostream>
using namespace std;

const int MAXN = 1000;
int a[MAXN], b[MAXN];

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> b[i];
    }
    int j = 0, i = 0;
    for (i = 0; i 
Read the rest

前言

Bellman-Ford算法,限于资料匮乏和时间复杂度比Dijkstra算法高,包括白书在内的很多资料,都没说得太明白。对于优化后的SPFA算法也没有提及。
而且最短路问题通常是作为图论的入门问题,学习者通常没有图论基础,不知道图论的一些基本常识,看已有的资料很容易产生疑惑。其实,从Bellman-ford算法优化到SPFA算法实际上是顺理成章的。

本文旨在阐明这两个算法思想和步骤,如果有什么晦涩或者疏漏之处在所难免,烦劳读者们指出。

Bellman-Ford算法有什么用

Bellman-Ford算法是用来解决单源最短路问题的。
在现实生活旅游途中,我们通常想知道一个景点到其他所有景点的最短距离,以方便我们决定去哪些比较近的景点。而这时候,Bellman-Ford算法就有用了。

Bellman-Ford算法的优点是可以发现负圈,缺点是时间复杂度比Dijkstra算法高。
而SPFA算法是使用队列优化的Bellman-Ford版本,其在时间复杂度和编程难度上都比其他算法有优势。

算法流程

(1)初始化:将除起点s外所有顶点的距离数组置无穷大 d[v] = INF, d[s] = 0
(2)迭代:遍历图中的每条边,… Read the rest

Update 2019/07/26:根据读者提出的问题,添加了查找数据方法、时间安排、论文及代码的下载地址等内容。

前言

本文主要是记录这次建模的过程和思路。用到的模型简单提及,并省略数据和结论。

涉及到的最小二乘法、模糊数学模型和马尔科夫链知识可以见我的文章“半小时学习最小二乘法”“模糊评价模型-以2018美赛为例”“马尔科夫链详解(TBC)”。

问题

Problem: A large multinational service company, with offices in New York City in the United States and Shanghai in China, is continuing to expand to become truly international. This company is investigating opening additional international offices and desires to have the employees of each office speak both in English and one or more additional languages. The Chief Operating Officer of… Read the rest

前言

最小二乘法在统计学的地位不必多言。本文的目的是全面地讲解最小二乘法,打好机器学习的基础。本文主要内容是最小二乘法的思想及在线性回归问题中的应用。后面的系列文章会继续讲解最小二乘的正则化。
至于非线性最小二乘和广义线性模型,如果以后有时间会进行整理。

不熟悉极大似然法的读者可以阅读我的另一篇文章《十分钟学习极大似然估计

updata 2019/6/13:添加了对线性回归问题的矩阵定义和简要介绍,修改了少量句子,修正了公式中的少量错误。

核心思想

最小二乘法是勒让德( A. M. Legendre)于1805年在其著作《计算慧星轨道的新方法》中提出的。它的主要思想就是求解未知参数,使得理论值与观测值之差(即误差,或者说残差)的平方和达到最小:
\[E = \mathop \sum \limits_{i = 1}^n e_i^2 = \mathop \sum \limits_{i = 1}^n {\left( {{y_i} – \hat y} \right)^2}\]
观测值\(y_i\)就是我们的多组样本,理论值\(\hat y\)就是我们的假设拟合函数。目标函数也就是在机器… Read the rest

前言

参数估计是机器学习里面的一个重要主题,而极大似然估计是最传统、使用最广泛的估计方法之一。

本文主要介绍了极大似然估计,简单说明了其和矩估计、贝叶斯估计的异同,其他估计(如MAP)并不涉及。

为什么要用极大似然估计

对于一系列观察数据,我们常常可以找到一个具体分布来描述,但不清楚分布的参数。这时候我们就需要用极大似然估计来求解这个分布的参数。换句话说,极大似然估计提供了一种给定观察数据来评估模型参数的方法,即:“模型已定,参数未知”。

极大似然估计概述

下面结合一个例子介绍极大似然估计法的思想和方法:

设一个袋子中有黑、白两种球,摸到白球的概率为p,现在要估计p的值。
我们令总体X为
\[
X = \left.
\begin{cases}
0,\quad 从袋中取得一白球,\\
1,\quad 从袋中取得一黑球.\\
\end{cases}
\right.
\]
则X服从01分布\(B(1,p)\)。

我们先进行有放回地摸球10次,其结果可用随机变量\(x_i\)表示,则\(x_1,x_2,⋯,x_10\)是… Read the rest

前言

本来想写一个关于感知机的总结,但如果要深入探讨,涉及的东西实在太多。仅仅浅尝辄止的话,那我就相当于照搬原文,违背了我写文章的初衷。

所以就单纯地把我自己写的感知机实现代码发上来,辅助大家学习。
我还提供了一个数据生成器,可以生成训练模型所需要的数据。

简单地对结果做了可视化,具体绘制代码见文末提供的github地址。跪求star=v=

感知机模型

感知机算法用于计算得到划分可二分数据集的超平面S。

我们定义优化函数为损失函数:
L=误分类点到超平面S的距离和

\(d = \frac{1}{{\left| w \right|}}|w \bullet {x_i} + b|\)

\(L = – \sum\limits_N {{y_i}} (w \bullet {x_i} + b)\)

采用随机梯度下降算法

\(\frac{{dL}}{{dw}} = – \sum\limits_N {{y_i}} {x_i}\)

故对于每一个误分类点

\(w = w + \eta {y_i}{x_i}\)

算法流程

输入:w, b;
训练:f(x)=sign(wx+b)

  1. 选取初值w0, b0
Read the rest