kenby
- 浏览: 717695 次
- 性别:
- 来自: 北京
-
最新评论
-
wxweven：
Surmounting 写道既然 Java 的跳表那么少，我决 ...
SkipList 跳表 -
暮雪云然：
写的不错，很透彻
Java静态内部类 -
bzhao：
好，赞扬！
Linux信号详解 -
jacktao219：
赞一个~！ ，现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon：
vote--后还要判断是否为0吧，如果为0则废掉重新置位can ...
现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数
文章列表
1 二叉树的前序遍历是ABC，后续遍历是CBA，其中序遍历是
关于二叉树的三种遍历：
前序遍历+中序遍历 可以确定二叉树的结构
后序遍历+中序遍历 可以确定二叉树的结构
前序遍历+后序遍历无法确定二叉树的结构
2
...
关于Linux的进程和线程
- 博客分类：
- linux
什么是进程
直观点说，保存在硬盘上的程序运行以后，会在内存空间里形成一个独立的内存体，
这个内存体有自己的地址空间，有自己的堆，上级挂靠单位是操作系统。操作系统
会以进程为单位，分配系统资源，所以我们也 ...
TCP / IP 协议浅析
- 博客分类：
- Network
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Port | Destination Port |
+-+-+-+-+-+-+- ...
假设你要开发一个多线程下载工具，你会自然的想到把文件分割成多个部分，比如4个部分，然后创建4个线程，每个线程负责下载一个部分，如果文件大小为403个byte，那么你的分割方式可以为：0-99 (前100个字节)，100-199(第二个100字节)，200-299(第三个100字节)，300-402（最后103个字节）。 分割完成，每个线程都明白自己的任务，比如线程3的任务是负责下载200-299这部分文件，现在的问题是：线程3发送一个什么样的请求报文，才能够保证只请求文件的200-299字节，而不会干扰其他线程的任务。这时，我们可以使用HTTP1.1的Range头。Range头域可以请 ...
对于两个整数a和b, 求a/b，可以从1开始枚举结果result，找到满足 result *b <= a的最大result即为所求，
这是一种可行的算法，但效率比较低，事实上，枚举result的时候，可以成倍的增加result，找到满足 result * b <= a的
最大result，然后把a减去 result * b， 接下来对余数a再次迭代，直到余数a比b小。
比如计算29/5的过程为：
（1）
a = 29, b = 5
找出满足b*i <= a的最大i， 依次计算：
b*1 = 5, b*2 = 10, b*4 = 20
所以最大的i = 4， 然后 ...
Longest Common Substring和Longest Common Subsequence是有区别的
X = <a, b, c, f, b, c>
Y = <a, b, f, c, a, b>
X和Y的Longest Common Sequence为<a, b, c, b>，长度为4
X和Y的Longest Common Substring为 <a, b>长度为2
其实Substring问题是Subsequence问题的特殊情况，也是要找两个递增的下标序列
<i1, i2, ...ik> 和 <j1, j2 ...
LCS问题：
给定序列
X = <x1,x2,...,xn>
和另一个序列
Y = <y1,y2,...,ym>
找两个递增的下标序列
<i1, i2, ...ik> 和 <j1, j2, ..., jk>使
xi1 == yj1
xi2 == yj2
......
xik == yjk
令Z = <xi1, xi2,..., xik>，那么称Z是X和Y的一个公共子串，
LCS问题是求最长的公共子串，即最长的下标序列
动态规划解法：
令Xi表示X的前缀<x1,x2,...,xi>
c ...
归并排序
- 博客分类：
- algorithms
#include <stdio.h>
#include <string.h>
int a[9] = {0,49,38,65,97,76,13,27};
int b[9];
void merge(int s, int m, int t)
{
int i, j, k;
k = s;
for (i = s, j = m+1; i <= m && j <= t; ) {
if (a[i] < a[j]) {
b[k++] = a[i++];
}
else {
b[k++ ...
快速排序 顺序统计量 数组分割
- 博客分类：
- algorithms
#include <stdio.h>
#include <string.h>
#define N 2578
void swap(int *p, int *q)
{
int tmp;
tmp = *p;
*p = *q;
*q = tmp;
}
int partition(int *a, int s, int t)
{
int pv = a[t];
while(s < t) {
for (; s < t && a[s] < pv; s++);
...
位运算集锦
- 博客分类：
- algorithms
文中2'k代表2的k次方
1 除以2的k次幂可以用位运算：
n/2'k == n>>k
2 对2的k次幂取余数可以用位运算：
n%2'k == n & ((1<<k)-1)
比如 100%32
100的二进制为 1100100
((1<<5)-1)等于31为 0011111
两个数相与即得 100，故
100%32 = 4
3 对于整数n，从低位开始，把它的第k位（0<=k<=31）置为1的操作为：
n = n | (1<<k)
4 对于整数n，从低位开始，把它 ...
最长递增子序列
- 博客分类：
- algorithms
设L = <a1,a2,...an>是n个不同的实数的序列，L的递增子序列是这样一个子序列：
Lin = <ak1, ak2, ..., akm>, 其中k1 < k2 < ... < km且ak1 < ak2 < ... < akm。
求最大的m，即求最长递增子序列的长度。
使用动态规划解决：
令f[i] 表示长度为i的递增子序列中末尾的元素
len[i] 表示a[1]...a[i]的最长递增子序列的长度
那么如何求len[i]呢？
找出max{j, f[j] < a[i], j = 1...len[i-1] }， ...
1 互斥变量： pthread_mutex_t，本质上说是一把锁，在访问共享资源前对互斥量加锁，访问完成后释放锁。
对互斥量进行加锁后，任何其他试图再次对互斥量加锁的线程将会被阻塞直至当前线程释放该互斥锁。
pthread_mutex_lock : 加锁
pthread_mutex_unlock：解锁
2 条件变量：pthread_cond_t，多个线程协作的一种同步方式，若某个条件不满足，线程将一直等待。条件变量一般
和互斥变量一起配合使用，因为条件变量本身是互斥访问的，所以要有一个互斥变量保护它。
pthread_cond_wait: 若条件不满组，一直等待下去
pt ...
select使用的一般步骤：
1 清空fd_set
2 把描述符加入fd_set
3 调用select，更新所有描述符的状态
4 依次检测每个描述符，若可读或者可写，则从描述符中读/写数据
5 每次select之前都要重新对fd_set清零，并把关心的描述符重新加进去
错误的做法：
fd_set set;
ct timeval tv = {3, 0};
fd[n] = {1,2,3,4,5}; /* 文件描述符列表 */
maxfd = max{ fd[i], 0<=i<=n }; /* 求最大的描述符 */
FD_ZREO(&set); ...
一 编译
1 sudo apt-get install xutils-dev
2 注释掉adns下internal.h中第568—571行代码
3 到/usr/include/c++/下CP一份iostream文件到larbin的src目录下。并将其的名改为iostream.h.打开此文件添加一句
using namespace std;
4 ./configure && make
二 配置
修改larbin.conf的 StartUrl
修改options.h的4中输出
DEFAULT_OUTPUT : This module mainl ...
一 爬虫----下载html网页
1 广度优先还是深度优先，研究表明，按照广度优先搜索方式得到的网页集合要比深度优先搜索得到的集合重要
2 多线程和异步IO，爬虫下载网页分三个步骤：1）查询url的dns 2）socket连接服务器 3) 从服务器下载数据
只有把这三个步骤并行化才能加快抓取速度，采用的策略是，异步dns查询，多线程connect服务器，最后使用
select IO多路转接来下载数据，实践中发现最耗时的步骤是connect操作.
3 网页去重，把下载过的网页保存在一个大的hash table中
4 数据结构：一个保存待下载url的队列，一个保存已查询 ...