总结了一下C++ STL里面用的比较频繁的一些代码片段. (地址: https://github.com/X-Wei/cpp-demo-snippets/tree/master/STL)
cpp文档: http://en.cppreference.com/w/cpp
常用的library主要有:
<algorithm>, <vector>, <queue>, <set>, <map>, <cmath>
另外一个常见的cpp文件开头版本是:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define forloop(i,lo,hi) for(int i = (lo); i <= (hi); i++)
#define rep(i ...今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.
PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的用途: pq是一种队列, 不过不是先进先出(FIFO), 而是每次出队的元素永远是优先级最高的.
个人感觉"堆"这个名字大概源于PQ的(逻辑上的)形状吧: PQ是一种树(tree), 准确的说, 是一种二叉树(binary tree), 说得再准确一点, 它是一种完全二叉树(complete binary tree): 没错, PQ是一种满足某些条件的完全二叉树.
所谓的"完全二叉树", 要满足:
- 除了最后一层, 所有层都排满(没有非空节点)
- 最后一层的所有非空节点都排在左边
一张图可以直观说明, 完全二叉树其实就是长得像这样:
一个完全二叉树能被成为PQ的话, 要满足的条件就是:
对于任何一个节点, 它的优先级都大于左右子节点的优先级.
比如下图 ...
今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition).
快速排序的算法可以用三句话描述:
[Algo]
- 选择基准项(pivot element, 一般取第一个元素为pivot)
- 把数组里所有小于pivot的移动到pivot左边, 大于pivot的移动到右边 ⇒ 此时pivot已经位于最终排序时的正确位置
- 对pivot左右两个数组分别递归进行快速排序
由以上描述可见, qsort是一个递归算法, 我们可以把它的函数声明写成: void qsort(int[] a, int lo, int hi), 表示排序a[lo, hi]之间(闭区间)的所有元素.
由上面描述可以见, qsort最关键的是第二步: 把数组元素以pivot分为两部分. 这个操作就是quick partition.
函数声明为: int partition(int[] a, int ...
weighted graph的最短路径问题有三个非常有名的算法, 分别以三个大牛的名字命名, 今天用尽量简洁的篇幅一一介绍.
简单起见(这回只写伪代码好了), 对于图的定义如下:
{1,2,...,n} e[u,v] = distance of edge(u,v); if (u,v) is not an edge, e[u,v]=INF Floyd算法解决的问题是: 对于任意两个节点s(source)和t(target), 求s到达t的最短路径.
Floyd算法的思想是动态规划:
- 定义
d ...
今天总结一下也许是搜索问题里最重要的算法: DFS !
由于树可以看成是一个graph, 这里还是只写对于graph的DFS算法. Graph类的定义还是用每一个节点保存邻居信息:
public class GraphNode{
int val;
List<GraphNode> neighbors;
}
为了防止重复, 仍然用一个HaseSet记录走过的节点:
HasheSet<GraphNode> visited = new HasheSet<GraphNode>();
首先写递归版本的DFS, DFS就是一条路走到底, 不撞南墙不回头, 所以递归写起来很自然: 每到一个节点, 标记其已经访问过了, 然后对于邻居里面没有访问的节点继续递归进行DFS.
递归的DFS代码非常简洁:
public void DFS(GraphNode nd){
System.out.println(nd.val);
visited.add(nd);
for(GraphNode next: nd.neighbors){
if ...今天总结一下广度优先搜索(BFS). BFS是树/图的遍历的常用算法之一, 对于没有边权重的图来说可以计算最短路径.
由于树的BFS只是图的BFS的一种特殊情况, 而且比较简单不需要visited标记, 这里只写一下图的BFS好了.
先定义一个Graph类, 这里在每一个节点保存邻居信息:
public class GraphNode{
int val;
List<GraphNode> neighbors;
}
图的遍历需要注意不走重复节点, 所以需要一个HashSet(名字叫visited)来保存哪些节点已经访问过了. 需要注意的是, 在把一个节点放进队列queue的时刻就要把它放进visited, 而不是在队列里取出来的时刻再放.
public void BFS(GraphNode start){
LinkedList<GraphNode> q = new LinkedList<GraphNode>();
HasheSet<GraphNode> visited = new HasheSet<GraphNode>();
q.push(start);
visited ...Here is a mindmap of the common algorithms and data structures, it can give an overview of the algorithmic terms.
I shall update its content later on. And maybe write some blog entries on some of the items.
This mindmap is drawn using xmind.
python科学计算包的基础是numpy, 里面的array类型经常遇到. 一开始可能把这个array和python内建的列表(list)混淆, 这里简单总结一下列表(list), 多维数组(np.ndarray)和矩阵(np.matrix)的区别.
列表属于python的三种基本集合类型之一, 其他两种是元组(tuple)和字典(dict). tuple和list区别主要在于是不是mutable的.
list和java里的数组不同之处在于, python的list可以包含任意类型的对象, 一个list里可以包含int, string或者其他任何对象, 另外list是可变长度的(list有append, extend和pop等方法).
所以, python内建的所谓"列表"其实是功能很强大的数组, 类比一下可以说它对应于java里面的ArrayList<Object> .
ndarray是numpy的基石, 其实它更像一个java里面的标准数组: 所有元素有一个相同数据类型(dtype), 不过大小不是固定的.
ndarray对于大计算量的性能非常好, 所以list要做运算的时候一定要先转为array(np.array(_a_list_ ...
Scrapy是用来爬取数据的很流行的包, 这里小记一下. 以前几天做的一个爬虫为例子, 这个爬虫把韩寒一个app的前九百多期的文章抓了下来.
scrapy的安装参考: http://scrapy-chs.readthedocs.org/zh_CN/latest/topics/ubuntu.html
(直接pip安装的好像缺少什么包)
需要学习scrapy首先需要会XPath, 这是一种方便与在html/xml文档里查找所需元素的语句. 这个还是很好学的, 其实只需要花一刻钟时间看看w3school的教程, 就可以掌握够用的知识进行下一步了.
这里总结一下我觉得会用到的语句(不全, 不过经常用到):
//book 选取所有名字叫做book的元素bookstore/book 选取bookstore的子元素中所有叫book的元素//title[@lang='eng'] 选取lang属性为"eng"的所有title元素//titile/text() 选取title元素的文字内容descendant-or-self::text(): 选取自己或者所有后代节点的文字内容另外还有个在线测试XPath语句的网站 ...
INF580(programmation par contraintes) 大概是在X学到的最有用的一门课, 它让我能够用把运筹学(MAP557)里学到的东西和计算机结合起来: 用电脑的力量解决(大规模)运筹问题.
这门课的projet是去年巴黎谷歌举行的一个比赛的题目: 最优化谷歌街景拍照小车的路线. 做这个projet的三周里, 我和Manu从一开始信心满满, 到中间一筹莫展, 再到后来柳暗花明, 以及最后乘胜追击终于在今晚得到了近乎完美的解答, 非常精彩, 这里特意一记.
谷歌那次比赛的题目在这里(我们做的是Main Round的题目): https://sites.google.com/site/hashcode2014/tasks
简单来说, 就是已知巴黎的道路信息, 设法用八辆车(每辆车的行驶时间有限)从巴黎谷歌出发, 尽可能多的走遍巴黎的所有街道, 参赛者给出这些车的路线, 他们的分数就是这八辆车走过的街道的长度之和(重复走的街道不算分).
去年四月份我们也参加了这个比赛, 不过当时纠结于如何设计每辆车的路线, 最后只是用了贪心算法, 再加上一点点的随机, 得到的结果并不好... 当时ENS的人包揽了前三名, 而且比赛后进一步把分数刷到了满分: 他们的路线可以把所有街道都跑遍.
这学期学了INF580以后, 手里有了 ...