简单理解KMP算法

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)

Machine Learning-神经网络(Neural Network)

本文覆盖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 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],
]

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