【数据结构】splay伸展树

引言

splay树并不是严格意义上的平衡树，但是他可以做到平衡树可以做到的一切。

而且，相比与RBT和AVL，splay简直不能更好写了～

所以，用来解决一般的算法问题，基本上splay已经是够用了。

splay

操作

关于splay的基本操作就是旋转，将一个子树向左或向右旋转。

关于两种旋转，可以参考这篇博客。

但是，从我个人理解，无论是左旋还是右旋，本质都是将一个节点上提（降低节点的深度）。

而旋转操作有用在区间操作上：我们可以通过旋转将一个区间旋转到一棵子树上，这样就可以直接对树根打上lazy标记。

【数据结构】线段树

引言

线段树虽然写起来没有树状数组那么简洁，时间效率也没有树状数组那么好，但是他的功能更加强大。

线段树

主要功能：

• 单点更新、区间更新（lazy）
• 单点查询、区间查询

剩下的不想多说了，太容易理解了，找个图一看就明白了～

只有一点要注意的：

• 区间边界有没有包含在两棵相邻的子树内

线段树根据不同的题目变化很丰富，所以没有模板，只有大致的框架。

看应用中的例子吧～

【数据结构】树状数组

引言

树状数组可以说是最好写，也是最好用的一种数据结构了～

树状数组

概览

树状数组是用数组存储的，它并没有显式的树形结构，而是用数组下表的二进制表示中最低位1的位置构建的一个隐式的树形结构。

这里不盗图了，要有版权意识～所以，更形象的展示可以参考这个博客中的AB图。

关于lowbit

lowbit当然不是low逼的意思啦～

lowbit(x)=x&-x，要理解这个，首先要知道计算机中补码的概念。如+8，因为正数的补码为其本身，所以其的二级制表示为01000（最高位是符号位）。而-8的补码将+8的所有位（包括符号位）取反，然后加1的结果，也就是11000。

所以，这个函数的作用就是求x最低位1所对应的数字，lowbit(8)=1000=8。

【算法】Trie图

引言

Trie图是Trie树的变种，结合了ac自动机中的思想。

而ac自动机的根本思想是基于kmp的next数组构建的fail指针。

所以，在学习Trie图前，请先搞清楚kmp算法。

关于AC自动机

我太久没写过AC自动机了，只知道AC自动机可以自动ac了。

所以，我还真的说不出AC自动机和我写的trie图有什么区别，可能我写的就叫ac自动机吧。

或者说，可能AC自动机和Trie图本来就是几乎一样的。

Trie图

关于Trie图，只要找到有图（那种非常好看的图）的那种博文，一般讲的都比较清楚。

因为，根本不用看字，看看图就明白了。

这里推荐一个博客：http://www.cnblogs.com/gtarcoder/p/4820560.html

Trie图写起来非常短，我这种邋遢的代码风格也就10行。

【算法】后缀数组（SA）

引言

关于后缀数组的原理，集训队论文中已经将的非常详细了。

但是，其中的代码对于第一接触这个东西的人来说可能就觉得有些恶心了。

所以，我这篇文章主要是讲怎么理解倍增方法的SA的构建过程。

SA的实现

基数排序

很多人理解不了这个是因为不知道基数排序。

所以，在学习后缀数组之前请先动手写一个双关键字的基数排序程序：求sa[i]表示第i大的元组在数组中的下标。

然后就可以正式进入SA部分了～

【算法】字符串：KMP算法

引言

kmp算法是字符串算法中最简单的一种算法，可以用于一下问题解决（待补充）：

• 字符串匹配
• 字符串循环节

但是，我发现有很多人都像我以前一样，其实并不是很懂这个算法。于是，就采用背代码的方式试图理解，但总是徒劳。而我个人认为，唯一可以通过背代码加深理解的只有复杂的数据结构。而这种巧妙的算法不是能通过背来理解的。

关于KMP算法

关于kmp算法的讲解网上有很多，找那种图多的博客看看，基本上讲的都差不多，也都非常明了。

所以，这里我只想讲讲我自己的体会。不画图，纯想：

• kmp算法的核心是一个next数组（我的代码中为p数组），当我们处于字符串（设为a）的第i个字符处时，求出的next[i]满足数组的前next[i]个字符和以a[i-next[i]+1]～a[i]这next[i]个字符是完全一样的，且next[i]最大，但又不能等于i

上面说的还是有点抽象，那么我们从字符串匹配的角度思考：

• 现在我们要从a串中找到一个子串和b串完全匹配，假设已经匹配了前i个，但是第（i+1）个不匹配，那么我么就要将字符串b向后移动再次寻求匹配。
• 既然我们向后移动了b串，那么，如果a中与b串匹配的串的首个字符的位置在i之前，那么这个匹配的子串一定跨越了i这个位置。
• 那么，我们自然而然就像知道，以a中以i位置结尾的子串最多能与b中的前几个匹配呢？
• 要回答这个问题，就是取求next数组了。

python爬虫实战（四）：selenium+phantomJS使用

引言

phantomJS是一个没有界面的浏览器；selenium则是一个web测试工具，可以模拟用户操作。
在对phantomJS使用不熟练的时候，可以用firefox和selenium一起使用。

配置

• phantomJS直接从官网下载二进制包，解压，然后用软链接的方式添加到/usr/bin/
• 使用firefox必须添加到环境变量，同时还要下载驱动

python爬虫实战（三）：爬取淘女郎图片

引言

爬取淘女郎图片是为了给一个朋友找找穿衣的搭配，但是期间遇到了很多问题，所以就写了这篇文章记录一下解决方案。

分析

• 我们要爬取的网页是：淘女郎，通过分析可以看到每个淘女郎的主页：

  )

• 随便找一个淘女郎的个人主页，有大量的图片，而且几乎没有多余的无关图片，所以直接用正则表达式可以轻易提取出图片的原始链接

• 那么我们爬完第一页，就要翻页了，尝试点击了一下“第二页”，网址竟然没变？！看来有麻烦了：翻页操作使用的是ajax异步加载的！那么我们的主要问题就是取解决如何获取ajax异步加载的内容了

[Linux]软链接

引言

我们经常会从网上下载一些程序，有些可以直接安装，像windows中的exe一样；有些则是源码安装，也是最麻烦的；而有些则是已经编译好的二进制文件，可以直接运行，就像windows中的“绿色软件”～

而面对这种绿色软件，如果想在任意目录下随意的运行，且不去修改系统的环境变量，软链接就派上用场了～

软链接vs硬链接

• 软链接

  • 相当于windows中的快捷方式，不会占用多余的空间

  • 使用方式：ln -s 源文件 目标文件，其中源文件必须使用绝对路径

  • 软链接和源文件是两个不同的文件，对应不同的节点

  • 使用ls -l时可以看到软链接有特殊的箭头符号表示

    

控制hexo文章摘要长度

方法很简单，不用安装任何插件，不用配置任何文件，只需要：
在期望显示的摘要后加上<!--more-->就可以了～

hexo文章置顶

由于我经常非常自恋的点开自己的博客，所以想到将自己的计划放在自己的首页提示自己。同时，也是激励自己。
所以就搜索了一些资料，总结了hexo博客文章置顶的方法，备忘。

requests模块学习

基础

基本请求

• requests支持http的6种基本请求（get，post，put，delete，head，options），请求名即为函数名
• get方法：res = requests.get(url)，返回的是Response实例，主要包含如下属性
  • res.status_code
  • res.url
  • res.encoding
  • res.cookies：如果response中包含cookie，则可通过cookies属性获取
  • res.text
  • res.content

get

• get添加参数：

1
2
3

payload = {'key1': 'value1', 'key2': 'value2'}
res = requests.get("http://httpbin.org/get", params=payload)
print(res.url) # http://httpbin.org/get?key2=value2&key1=value1

python爬虫（一）：urllib

urllib

urllib.request

urllib.request.urlopen

• 原型：request.urlopen(url, data, timeout)
• 返回：Request类实例
• 实践：response = request.urlopen('http://blog.proverbs.top')

urllib.request.read

• 返回：Request实例的文本
• 实践：request.read()

urllib.request.Request

• 推荐使用构建Request实例作为urlopen的参数
• 构建：req = request.Request('http://blog.proverbs.top')
• 实践：res = request.urlopen(req)

urllib.request.ProxyHandler

• urllib默认使用环境变量http_proxy作为代理
• 手动设置代理：使用Handler可以构建opener，而opener代替urlopen

1
2
3

proxy_handler = request.ProxyHandler({"http" : 'http://some-proxy.com:8080'})
opener = request.build_opener(proxy_handler)
request.install_opener(opener)

《鸟哥的Linux私房菜》学习笔记（未完）

linux内置工具

• man
• info：需要以info格式书写说明文档
• nano：简单的文本编辑器

linux命令

维护

• who：查看当前在线用户
• ps -aux：查看进程
• netstat -a：查询网络状态
• shutdown，reboot：在执行前会自动执行sync
• init：切换运行级别（0：关机，3：纯文本，5：图形接口模式，6：重新启动）

权限

身份类别：owner, group, others
权限类别：read, write, execute

• chgrp (-R，递归) 所属组名 文件名：改变group
• chown (-R，递归) 所有者名 文件名：改变owner
• chmod (-R，递归) 文件名：改变权限
  • chmod 777 文件名：r=4，w=2，x=1
  • chmod [u/g/o/a] [+/-/=][r/w/x] 文件名：chmod u=rwx,g=rx,o=r 文件名

颜色空间人脸检测

实验目的

使用颜色空间的方法检测人脸，并用二值化的方法进行显示。

实验内容

选定图像色彩模型

如果使用RGB颜色模型，当光照、肤色稍微变化时，对RGB各分量的灰度值有较大的影响。所以通过查阅资料，最终选定了YCbCr颜色空间作为人脸检测的颜色模型，并选定Cr分量的灰度作为判定标准。