标签归档：Algorithm

简单理解KMP算法

1条回复

KMP是非常著名的字符串匹配算法，学生时代看了几遍都没有真正理解。偶然的，今天在微博上看到有人在哔哩哔哩上直播讲解KMP，看完之后觉得没讲到点子上，他只是教你怎么使用，却没有说出为什么要这么做。
网上关于KMP算法的介绍太多了，我就不再写了，可以先看完这几篇文章：
字符串匹配的KMP算法-阮一峰
（原创）详解KMP算法-孤影
KMP算法的Next数组详解-北京小王子
看完之后感觉自己好像是理解了，但是又总感觉没有真正理解。直到某一个瞬间突然灵光乍现，豁然开朗！我们知道，KMP有个重要的概念是要构造查询串的前缀和后缀，然后通过一个next数组来移动指针，以加快匹配效率。
但是为什么要构造前缀和后缀呢？
string_match
如上图所示，当我我们移动到红圈位置时，发现C和D是不一样的，这时候蛮力的做法就是把下面的字符串一个个往右移，但这样做效率并不高。仔细观察一下会发现：C和D之前的最长公共子序列肯定是一样的（也就是上图的ABCDAB），我们定义上面的为X，下面的为Y。现在想象一下：X不动，Y开始向右移动1个长度，那么匹配的就是X的后5位（BCDAB）和Y的前5位（ABCDA）,发现并不匹配。[……]

继续阅读

Machine Learning-神经网络（Neural Network）

2条回复

本文覆盖Coursera Machine Learning Week 4&Week 5的内容。

什么是神经网络？
在机器学习和认知科学领域，人工神经网络（Artificial Neural Network，缩写ANN），简称神经网络（英文：Neural Network，缩写NN）或类神经网络，是一种模仿生物神经网络(动物的中枢神经系统，特别是大脑)的结构和功能的数学模型或计算模型，用于对函数进行估计或近似。（摘自：维基百科-人工神经网络）
神经网络并不是什么新鲜的玩意儿，早在1958年,美国心理学家Frank Rosenblatt就提出了一种具有单层计算单元的神经网络,称为感知器(Perceptron)。这个概念一经提出就被认为有着良好的发展潜能，因为他结构简单，也能解决一些复杂问题。但是感知器有一个天生不可解决的问题：只能解决线性可分问题，连最简单的异或（XOR）模型都无能为力。1969年Marvin Minsky写了一本叫做《Perceptrons》的书，他提出了著名的两个观点：1.单层感知机没用，我们需要多层感知机来解决复杂问题 2.没有有效的训练算法。大意就是这玩意儿[……]

继续阅读

P和NP问题（P versus NP problem）

P和NP问题（P versus NP problem）
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它也是克雷数学研究所七个千禧年大奖难题之一。学计算机的肯定会经常听到P和NP，但我相信很多人跟我一样对这个问题既熟悉又陌生，并不能真正地把他理解透彻，今天花点时间总结下吧。

什么是P问题？
能够在多项式时间内给出答案的问题被称为P问题，也就是说存在一个多项式时间复杂度内的算法解决该问题。这个很好理解，那为什么要是在多项式时间呢？因为只有在多项式时间内的复杂度才是计算机所能接受的，再大的复杂度（比如指数级，阶乘级别）即使有解也没有实际价值（计算量太大）。

什么是NP问题？
对有些问题而言，并不存在一个已知的多项式时间内的算法来解决问题，但是如果有人能够提供一个答案（不论对错），我们却能够很快地验证这个解是否正确，那么这些能够在多项式时间内验证一个解的问题被称为NP问题。通俗，不严谨的讲就是能在多项式时间内猜出解的问题。举个栗子：著名的子集合求和问题（subset sum problem），给定一个整数集合：{−2, −3, 15, 14, 7, −[……]

继续阅读

Perfect Squares

发表评论

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

这题是个经典的动态规划（Dynamic Programming）问题，当前问题的解决依赖于子问题的答案。以前上算法选修课的时候这快内容是必讲的，但是当时对这个问题一知半解，感觉好难啊，就算当时懂了过了一段时间又忘了。然而DP却是算法里面最基本也最常用的技能，必须掌握！于是去网上搜了一些资料，发现好像也没那么难，结合例子很好理解，学完这块内容基本的DP问题就可以解决了。
动态规划-从新手到专家
这篇文章说的详细了，自己在这里只记录下一些要点，以供日后回忆。
1.什么是动态规划
动态规划是一种求解多阶段决策过程的最优解算法，含有[……]

继续阅读

Combinations

发表评论

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

这题没有什么特别的思路吧，递归遍历。代码如下：

[……]

继续阅读