kenby
- 浏览: 717713 次
- 性别:
- 来自: 北京
-
最新评论
-
wxweven：
Surmounting 写道既然 Java 的跳表那么少，我决 ...
SkipList 跳表 -
暮雪云然：
写的不错，很透彻
Java静态内部类 -
bzhao：
好，赞扬！
Linux信号详解 -
jacktao219：
赞一个~！ ，现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon：
vote--后还要判断是否为0吧，如果为0则废掉重新置位can ...
现在有一个整数数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数
文章列表
poj 2774 后缀数组
- 博客分类：
- algorithms
#include <stdio.h>
#include <string.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define maxn 200004
#define MIN(a, b) (a) < (b) ? (a) : (b)
int wx[maxn],wy[maxn],c[maxn], h[maxn];
int sa[maxn], *rank, hei ...
poj 2823 线段树
- 博客分类：
- algorithms
赤裸裸的线段树，数据量很大，加了IO优化函数。
#include <stdio.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b)
#define inf 20000000
#define N 1000001
st ...
一 题意：给定递增序列，找出连续出现的最长子序列，然后求出它的长度，即最高频率。注意必须是连续出现。
二 算法：可以事先求出序列中每个数字的最高频率，比如序列(-1,-1,1,1,1,1,3,10,10,10)中各个数字的最高频率为：
( ...
poj 3264 ST算法
- 博客分类：
- algorithms
RMQ问题，既可以用线段树解决，也可以用ST算法，关于ST算法，这篇文章图文并茂，还有动画演示，讲解非常精彩，一
学就会。我就不罗嗦了，直接贴代码。
#include <stdio.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b ...
poj 3264 RMQ 线段树
- 博客分类：
- algorithms
zkw式线段树解决RMQ问题，只需查询，不用更新，很简单，ps: 为什么C++比gcc快那么多啊？gcc提交3047ms，用C++
的话，只需1329ms。
#include <stdio.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a) ...
poj 2777 线段树
- 博客分类：
- algorithms
至多有30种颜色，要求某个区间段有多少种不同的颜色，很容易想到用1个位表示一种颜色，
最后二进制的或运算一下子就求出了颜色的种数。
跟poj 3468一样，要支持区间的修改和区间的查询，但我始终没有想到如何用zkw式的线段
树的解决办法，貌似这个题目只能自顶向下查询，所以只好用朴素的线段树，为了把更新操
作的复杂度变成O(log n)，要引入一个标记，表示这条线段的所有子线段都被刷成了同一种颜色，
好在颜色用二进制表示的话，如果只有一种颜色，那么颜色值必定是2的n次幂，用 x&(x-1)
可以判断一个数是否为2的n次幂。所以颜色值也可以作为标记，每必要再引入一个标记了。 ...
poj 3468 树状数组解法
- 博客分类：
- algorithms
一 算法
树状数组天生用来动态维护数组前缀和，其特点是每次更新一个元素的值，查询只能查数组的前缀和，
但这个题目求的是某一区间的数组和，而且要支持批量更新某一区间内元素的值，怎么办呢？实际上，
...
关于zkw式线段树，请参考zkw大牛的ppt--百度文库《统计的力量》，其特点是利用完全二叉树数组存储的特点，自底向上遍历节点，非递归地完成查询和更新，加上位操作的使用，可以提高程序的效率。ps：__int64比long long的效率高很多。
#include <stdio.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 100002
struct tree_node{ ...
poj 3468 线段树朴素递归解法
- 博客分类：
- algorithms
一 题意
给定一个数组A，定义Add(s, t, d)的操作为对A[s]...A[t]加d，定义Query(s, t)的操作为查询A[s] + ... + A[t]的值
二 算法
在一系列Query操作中，如果每次查询都把A[s]...A[t]加一次，那么要执行加法(t-s+1)次，算法复杂度为O(t-s+1)，用线段树，
令线段<x, y>保存A[x]...A[y]的和，对于查询Query(s, t) , 只需在线段树中找到<s,t>对应的若干条线段<s, k>, <k+1, l>,...,<m, t>连接起来刚好 ...
一 题意：输入很多棵树(单词)，统计每种树所占的百分比
二 算法：用trie树轻松解决，trie树的典型应用就是统计单词出现的个数。
三 代码如下，ps：清华大学《数据结构-C语言版》的trie树实现很傻逼，我不知道它如何
解决前缀字符串的问题，比如统计aaa和aaabb的出现次数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA ...
poj 2002 二分查找，hash
- 博客分类：
- algorithms
算法过程：
1 将顶点按x坐标递增排序，若x相同，按y坐标递增排序，然后枚举所有边，对每一条由点p1和p2(根据排序p1 < p2)组成的边按照如下方式可唯一确定一个正方形：
1) 将边绕p1逆时针旋转90度得到点p3
2) 将边绕p2顺时针旋转90度得到点p4
则p1 p2 p3 p4组成一个正方形，设p1 = (x1,y1), p2 = (x2, y2)，根据向量的旋转公式可以求出p3, p4的坐标为
p3 = (y1 - y2 + x1, x2 - x1 + y1)
p4 = (y1 - y2 + x2, x2 - x1 + y2)
2 然后搜索点 ...
一些常用的算法
- 博客分类：
- algorithms
char *str_cpy(char *dest, char *src)
{
char *tmp = dest;
while ((*dest++ = *src++) != '\0');
return tmp;
}
<audio controls="controls" style="display: none;"></audio>
#include <stdio.h>
#include <string.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define M 530001
#define N 500001
struct trie_node {
int color_id; /* 叶子节点存储颜色编号，从1开始 */
int child[26]; /* 分支节点，静态链表表示 ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
int n, len, count;
char found;
int stick[64];
int st[64]; /* st[k] = sum{a[k]...a[n-1]}, 某根木棒和所有比它 ...
#include <stdio.h>
#include <string.h>
char pos[300]; /* pos[i] = j表示第i行上的皇后放在第j列 */
int n;
int count;
/* 寻找第i行的皇后可以放的位置，不能放则令pos[row]等于-1 */
void find (int row)
{
int i, j, k;
char ok;
if (row == n) {
printf("第%d种解决方案: ", ++count);
for (k = 0; k ...