3个在字符串中寻找子串的算法

m是子串长度,n是父串长度。
θ是渐进,Ω是最快,O是最慢。

leetcode链接 https://leetcode.com/problems/implement-strstr/

1、暴力法

O(n*m)

2、Rabin-Karp法

是在m上做文章。
预处理:求子串哈希。θ(m)
匹配:O(n*m),θ(n),因为有哈希,不用遍历子串

3、Knuth-Morris-Pratt法

预处理:子串算出自己的next组。θ(m)
匹配:因为有next组,不用遍历父串。O(n)

【算法设计模式】动态规划

1. leetcode上动态规划相关的题https://leetcode.com/tag/dynamic-programming/

2. 动态规划不是一个算法,是一个算法设计模式;

3. 动态规划的英文dynamic programming中的programming不取“编程”之意,是“训练、预先调整”的意思;

4. 动态规划可视为递归的一种优化,很多动态规划能解决的问题都可以通过递归解决,但是动态规划更快;

5. 动态规划是通过用额外的空间缓存住计算结果,防止在递归中重复计算来达成优化的。通常管这个缓存叫“表”;

6. 设计动态规划的两个主要步骤:
a> 找到子问题、
b> 找到问题-状态方程;

7. 适合动态规划来解的问题一般具有以下特点:
a> 可分解为子问题、
b> 子问题与前面数个的子问题有重叠( 在方程中体现为:x(i) = f(x(i-1), x(i-2)) )、
c> 子问题不与前面所有的子问题相关(无后效性);

8. 动态规划的程序有两种等价的书写方式:
a> 递归写法。自解到初始条件,带有表缓存、
b> 循环写法。自初始条件到解;

9. 动态规划与贪心的区别在于子问题重叠,相同之处在于无后效性。

简版:
a. 表优化
b. 递归cache
c. 问题-状态方程
d. 子问题重叠
e. 子问题后无效
f. 顶向底的递归+表 等价于 底向顶的While写法

我心不屈

http://www.miaopai.com/show/J0rE2pZ61lePVYDjdmhGNA__.htm

这个视频的英文如下,背之。

Unbroken – Motivation Comes From Within

“So you have to trust that the dots will somehow will connect in your future
You have to trust in something
Your gut, destiny, life, karma, whatever.
Because believing that the dots will connect down the road
Will give you the confidence to follow your heart,
Even when it leads you off the well worn path.
And that will make all the difference.

Your time is limited,
So don’t waste it living someone else’s life

Don’t be trapped by dogma :
Which is living with the results of other people’s thinking
Don’t let the noise of other opinions drown out your own inner voices.
You’ve got to find what you love
And that is true for works
as its for your lovers
your work is gonna fill a large part of your life
And the only way to be truly satisfied
Is to do what you believe is great work
And the only way to do a great work
Is to love what you do
If you haven’t found it yet
Keep looking and don’t settle
Have the courage to follow your heart and intuition
There somehow, already know
What you truly want to become.”
– Steve Jobs.

That you going to have some ups and you’re going to have some downs
Most people gave up on themselves easily
You know that a human spirit is powerful?
There is nothing as powerful – its hard to kill the human spirit!
Anybody can feel good when they have their health, they bills are paid, they have happy relationships
Anybody can be positive then,
Anybody can have a large of vision then
Anybody can have a lot of faith under those kind of circumstances

The real challenge of growth, mentally, emotionally and spiritually
Comes when you get knocked down

It takes courage to act
Part of being hungry when you’ve been defeated
It takes courage….
To start over again

Fear kills dream
Fear kills hope
Fear….put people in the hospital
Fear can age you
Can hold you back from doing something that you know within yourself that you are capable of doing,
But it will paralyzed you

At the end of your feelings is nothing,
But at the end of every principles is a promise
Behind your little feelings, it might not be absolutely nothing at the end of your little feelings
But behind every principles is a promise
And some of you in your life
The reason why you are not in your goal right now, because you just all about your feelings
All on your feelings, you don’t feel like waking up, so who does?

Everyday you say ‘no’ to your dreams,
You might be pushing your dreams back a whole six months, a whole year!

That one single day, that one day you didn’t get up could have pushed your stuff back I don’t know how long

Don’t allow your emotion to control you
We are emotional but we wanna begin to discipline your emotion
If you don’t discipline and contain your emotion, they will use you

You want it and you’re going to go all out to have it
Its not going to be easy, when you want to change
Its not easy. If it were in fact easy, everybody would do it
But if you’re serious, you’ll go all out

I’m in control here
I’m not going to let this let this get me down, I’m not going to let this destroy me!
I’m coming back!
And I’ll be stronger and better because of it
You have got to make a declaration
That this is what you stand for
You standing up for your dream
You standing up for piece of mind
You standing up for health
Take full responsibility for your life
Accepts where you are and the responsibility that you’re going to take yourself where you want to go
You can decide that I am going to live each day as if it were my last

Live your life with passion
With some drive
Decide that you are going to push yourself
The last chapter to your life has not been written yet

And it doesn’t matter about what happened yesterday
It doesn’t matter about what happened to you, what matter is
What are you going to do about it?

This year I will make this goal become a reality
I wont talk about it anymore
I Can
I Can!
I CAN!

To persevere I think its important for everybody
Don’t give up, Don’t give in
There’s always an answer to everything.

OCR选型笔记

OCR(按照识别率从低到高排序)

Cuneiform for Linux —— 本来是个Windows软件,这是Linux的移植,2011年4月已经停止维护。
GNU Ocrad —— 命令行工具。有JS移植,可用于前端。
GOCR —— 命令行工具。有JS移植,可用于前端。
Tesseract —— 开源OCR引擎,也有命令行工具。HP开发Google接手。3.0之后支持训练。Golang绑定入门教程
OCRopy —— 基于训练的OCR引擎,训练后可以达到比Tesseract更高的准确度,项目比Tesseract更年轻。包含一个叫做OCRopus的布局分析器。in Python。
Microsoft OCR Library —— Windows8.1之后的版本内置OCR引擎,可用于桌面和WindowsPhone。
Abbyy —— 收费软件,有SDK,有Cloud版本。

预处理

OpenCV —— 图像处理老大哥。OpenCV3中有Scene Text Detection值得一用。
Libccv —— 现代图像处理库,被很多人推荐。实现了精选的若干个图像处理算法,干净容易移植。其中Stroke Width Transfor尤其有用。
lswms —— 分行检测。
OCRopus —— 基于神经学习网络算法的布局分析库。教程
TiRG —— 文字区域检测库,效果演示
unpaper —— 检测文字和旋转,用的是Hough transform算法。

Scene Text Detection

API
例子1
例子2
Paper
高层包装应用

高层项目

node-dv —— in Node.js,整合了OpenCV、Tesseract和一些其他项目。
node-fv —— node-dv的更高层,用于证件识别。
OpenOCR —— 包装了SWT、Tesseract、Docker、RabbitMQ,提供队列和HTTP访问服务。in Golang。
openalpr —— 包装了Tesseract和OpenCV,支持多系统build,支持Docker,有Python和Node.js绑定。

百度OCR

API值得借鉴学习。

关于移动端

tess-two,Tesseract的安卓移植,教程
microblink,免费的移动OCR-SDK。

新方法:机器学习

如果有够多的样本和验证能力,机器学习可以很好的处理OCR的问题。
http://www.danvk.org/2015/01/09/extracting-text-from-an-image-using-ocropus.html
http://www.danvk.org/2015/01/11/training-an-ocropus-ocr-model.html
https://en.wikipedia.org/wiki/Long_short_term_memory
https://github.com/nypl/map-vectorizer

一个快速深度学习的框架,和基于它构建的OCR项目。
https://github.com/BVLC/caffe/
https://github.com/pannous/caffe-ocr

JS构建的神经学习网络
https://github.com/mateogianolio/mlp-character-recognition

顺便

ImageMagick —— 实现PDF、PNG、TIFF之间的格式转换。
Apache Tika —— 从HTML、Word、Pdf、Excel、PPT、Zip等文档中提取内容的类库,in JAVA。

韦德健美训练法则

初级法则

渐进超负荷 —— 逐步加量,让肌肉始终处于超负荷的状态;
孤立 —— 单独锻炼一块肌肉;
金字塔 —— 每次锻炼时,从多次数少重量逐步改变到少次数多重量;
顶峰收缩 —— 肌肉收缩到极致时,保持1~2秒钟;
变换角度 —— 用不同的握距和角度锻炼目标肌群;

中级法则

动作多变 —— 定期改变已经习惯的训练动作、负荷、次数或顺序;
优先 —— 把最薄弱的肌肉放在每次训练的最前面;
分部 —— 把身体分为几个部分在不同的日子训练;
超级组 —— 将相对肌群组合在一起训练;
复合组 —— 连续使用不同的用力方式或运动路线锻炼同一组肌群;
交叉 —— 在练习大肌肉群的间隙插入联系小肌肉群;
三组合 —— 对同一个肌群连续采用3种不同的动作;
综合 —— 用不同的负荷、次数、动作锻炼目标肌肉群;
快速 —— 保证动作准确的前提下,用爆发力锻炼。此方法不宜安排多;
静力张紧 —— 在肌肉收缩到极致时,保持6~10秒。此方法塑形,赛前不可少于每日半小时;
先期疲劳 —— 先用孤立动作让目标肌肉疲劳,再与协同肌肉一起练习;
持续紧张 —— 慢速完成动作,避免借助摇摆力的惯性;
周期 —— 制定短期的训练目标和手段;
预热 —— 先做单关节动作,然后再做多关节动作;

SEO清单2015

是否安装了Google统计?
是否安装了Google站长服务?
是否逐条检查了Google站长服务的反馈信息?
检查失效链接了吗?
如果使用的是WordPress,是否安装了SEO for WordPress?
你的站点在手机上浏览效果怎么?
载入速度怎样?
检查过站内是否有重复内容了吗?
可以确保每个页面都有足够的内容吗?(至少要有100字以上)
如果是本地化的网站,有足够的本地化关键字和内容吗?
每个页面的meta里标题和描述都好好写了吗?
有没有使用H1, H2, H3, H4标签? (一篇文章应该由1个H1,和多个H2、H3、H4组成)
是否每个页面都有明显的主题和关键字?
是否每个页面的URL都是自描述且包含关键字的?
是否给Google和Bing提交了XML sitemap?
根目录下的robots.txt写好了吗?
图像是否都有alt描述?
网站是否容易逛来逛去?(导航、内链、搜索做得如何?)
如果是电子商务网站,启用HTTPS了吗?
外链足够丰富吗?(搜索引擎喜欢看到来自社交媒体、有价值的博客、同领域内的网站和高权重网站的链接)
有没有检查竞争对手的外链都来自哪里,他们做哪些关键词,他们的SEO效果咋样?
有没有抢注社交网站的名字?(赶紧注册,并把它们指向你的网站)
你的网站分享到社交网站容易吗?
有没有把网站提交给相关的垂直搜索引擎?
有没有确保你的网站在所有Google的相关服务上都能找到?(包括地图、Google+、搜索等)

译自:http://onlinemarketinginct.com/2015/05/09/seo-checklist-2015/

面包店算法

用于多线程操作同一个数据时同步使用。
优点在于没有锁。
本质在于把pid拿来当比较对象,从而把锁逻辑转嫁给了操作系统。

下面的代码是多线程中的一个线程的逻辑。

OAuth和OpenID的区别

OAuth和OpenID都是开放的Web第三方登录标准,都使用了HTTP重定向的方式,也都可以集中管理登录有效期。

它们不同于,OpenID的目标在于使你只用一次登录动作就可以登录多个网站。当你想要登录一个使用了OpenID服务的网站时,它会将你重定向至提供OpenID服务的网站,如果你已经登录过,会自动重定向回来,此时你已经是登录状态。

OAuth的目标则在于让你可以独立授权“消费者”网站是否可以读取“提供者”网站上的数据。

比如说,你想让一个打印网站帮你打印微博上的相片。它会把你重定向到微博,微博问你“允许它读取你的相片吗?”如果你允许,这个打印网站就把你微博上的相片都下载走了。

使用OAuth需要你登录“提供者”网站,至于如何“提供者”网站提供何种登录方式,完全与OAuth机制无关。可以是用户名密码,物理令牌或者是OpenID。

OpenID不关心数据的事。虽然它的扩展协议也会支持存储像你的名字、头像、电话号码等内容,并将它们提供给使用了OpenID服务的网站。但本质上,它只是为了让你少输入几次这种通用信息而已。它不会存储与应用相关的敏感信息。

OAuth提供商会向别人提供你应用相关的数据,如果你用一个网站请求你的微博OAuth授权,你应该准备好它可以拥有你微博的所有权限。

你给了人家OAuth权限,那效果就像你把用户名密码给人家了。OAuth的好处就在于你不用真的把用户名和密码给他,而且可以做一些权限范围的控制。

但OpenID就没有这个效果,即使你用了两个使用同一个OpenID服务的网站,它们互相之间也读取不了任何信息,做不了任何操作。OpenID比OAuth更加“粗粒度”一些。

译自:http://softwareas.com/oauth-openid-youre-barking-up-the-wrong-tree-if-you-think-theyre-the-same-thing/

非阻塞read()时的errno

各个系统非阻塞read()的errno一般不会设置为EINTR。查看socket方法bind()、connect()、send()、receive()的man手册,或是POSIX标准,会发现一件有趣的事情:只有bind()不会把errno设置为EINTR,而bind()正好是其中唯一一个默认非阻塞的方法。

所以,看起来好像只有阻塞的方法才会设置EINTR,包括read()、write()。如果用O_NONBLOCK将它们设置为非阻塞的话,那它们也将不会设置EINTR了。

我们可以从API设计的角度来思考一下这个问题:当阻塞读被信号打断时,系统如何处理这个情况呢?

说read()失败了?其实它只是中断了一下,而且没读到数据而已。

说它成功了但是返回0字节?这也不合适,因为成功且返回0字节这件事已经用在“对方关闭连接”或者“读到文件尾”的状况了。也就是说继续读就读不到内容了。但我们这种情况,如果咱们继续读,是可以读出数据的。

想来想去,还是标记一个错误更合适一些。但是确实又没有发生什么值得去处理的关键性错误,所以就把错误标记成EINTR吧。它大概是在说:“数据流其实没发生啥错误,只是这次调用出了点问题,可能是被信号打断了。后面还有数据呢,请继续调用吧。”

但是如果我们使用了O_NONBLOCK的话,以上的情况就不会发生。因为反正对非阻塞读而言,返回成功又没读到任何东西是正常现象,它一般就会设置EAGAIN了。它大概是在说:“现在还读不到数据呢。我被设置为不许等着数据来,必须退出,所以你自己过会儿再尝试一次吧。”

当然,非阻塞读也会遇到被信号打断的情况。信号会无情地打断所有的方法,不管是系统的还是我们自己写的。所以理论上所有的系统API都可能设置EINTR。但由于非阻塞读总是会空返回,它就不额外提示这种状况了。

MacOS的代码中也确实是这样处理的。如果没读到东西,内核检查句柄的O_NONBLOCK标志位,如果有则返回EAGAIN,如果没有则调用msleep()等待。如果此时信号来了,msleep()将会被打断并设置EINTR,而read()则会把EINTR直接传递上来,于是我们就看到read()返回EINTR了。

所以如果是非阻塞读,我们则完全不会调用到msleep(),也就不会遇见EINTR了。

当然这只是MacOS,但大多数系统在这些基础的API设计上努力在保持一致。我们可以认为,一般而已非阻塞读不会设置EINTR,只会设置EAGAIN。

译自:http://stackoverflow.com/questions/14134440/eintr-and-non-blocking-calls

[逐字稿]ubuntuHackathon作品发表

slide地址:http://www.slideshare.net/pluschen/beijingubuntuhackathon

——

有没有可能“不花时间记单词”呢?

没有。梅花香自苦寒来,我们不相信不劳而获的事。

但是,我们意识到一件事——不同时间的价值是不同的。

大家都知道有一种时间叫做“碎片时间”。

(翻slide)

比如说,这样——在公交车上的时候。

(翻slide)

又或者这样——在匆忙赶路的间隙里。

在这样的时间里我们无法完成一个比较大的项目。

在这些时间里我们通常拿着手机都在干嘛呢?——刷微博、刷朋友圈,有些同学可能喜欢看看小说。

这些碎片的时间有没有可能拿来背单词呢?

当然有。

那,为什么我们没有这样去做呢?

我们觉得原因有两个——

首先,“背单词”这件事让人有负担感。

现在市场上有一些背单词的App,但是它们都会给你设定每日任务,有一个进度条。这进度条只要出现在脑海里就会给人负担感。如果只有5秒钟我们不会想要打开它,对吗?

现在我只有五秒钟,我只想快速获得一点简单的快乐。刷一下微博,对吧?哪怕这快乐并不长久。

另外,学习最重要的是什么?

成就感对吧?持续的正向反馈对吧?

如果说必须背到1000个单词,才能在阅读英文的体验上有明显的提升。这么长久的一个目标是让人容易放弃的。

OK。那么,我们有没有可能让记单词这件事变成一件“可以在5秒内启动、完成、关闭”,并且“可以持续提供正向反馈”的事呢?

(翻slide)

我们开发了桌面版的词典,和其他词典软件不同的是。这个软件会在每次你查词的时候把信息发到远端,服务器会根据你查词的词频计算出在你的阅读领域内最需要记下来的词。

你打开手机,这个词它就从服务器下来,出现在你面前。这个App没有启动屏,打开就看到那个你最需要记的词。5秒钟,记下它。

按照这样的方式来筛选和记忆单词。相信我,不再用两千、三千,只要一百个。你整个阅读英文文档的体验就会完全、完全不一样!

(翻slide)

事实上,我们已经在Mac App Store发布了这款软件。在教育分类排到过第一。

(翻slide)

这次在这个hackthon,我们打算在ubuntu上实现这个想法。

我们用cordova来做跨平台的事情。我们原本以为有cordova的帮助这件事是轻松写意的。

然而……

当我们打开cordova的插件页面,filte by ubuntu…

(翻slide)

“砰”,所有的插件全都消失了……

这确实给我们带来了很大的麻烦。

(翻slide)

但最终,我们还是实现了我们的想法。

简单的快乐,开机即得。

1个单词,3个意思。选到,对了。很简单,对吧?

简单的成就感,对吧?就这么唾手可得。

我们按照1、2、4天的记忆曲线给你展示需于你的单词,如果你连续三次选到了正确的释义,我们就认为你记住这个词了。

(翻slide)

我们也提供成就系统,让快乐有一个长期的积累。

有各种的成就,累计记忆了100个词啊,或者今天很努力,一天就记了50个词啊之类的。

我们希望通过自己的努力,使得记单词这件事不再是一个负担,而是像刷微博一样一个获得简单快乐的源泉。

(翻slide)

谢谢组织者给我们这个机会,得到两天非常专注的时间来实现我们的想法。

我们玩得很开心,谢谢大家。

大家有问题吗?