// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除,需要保证头结点存在
void remove()
{
head = ne[head];
}
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}
(1). 普通队列:
// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt)
{
}
(2). 循环队列
// hh 表示队头,tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt)
{
}
常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度
求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
(1)朴素并查集:
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
(2)维护size的并查集:
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集:
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点,及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
(1) 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
(2) 开放寻址法
int h[N];
// 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
核心思想:将字符串看成P
进制数,P
的经验值是131
或13331
,取这两个值的冲突概率低
小技巧:取模的数用2^64
,这样直接用unsigned long long
存储,溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
(1).vector
, 变长数组,倍增的思想
size()
返回元素个数
empty()
返回是否为空
clear()
清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算,按字典序
(2).pair<int, int>
first
, 第一个元素
second
, 第二个元素
支持比较运算,以first
为第一关键字,以second
为第二关键字(字典序)
(3). string
,字符串
size()/length()
返回字符串长度
empty()
clear()
substr
(起始下标,(子串长度)) 返回子串
c_str()
返回字符串所在字符数组的起始地址
(4). queue
, 队列
size()
empty()
push()
向队尾插入一个元素
front()
返回队头元素
back()
返回队尾元素
pop()
弹出队头元素
(5). priority_queue
, 优先队列,默认是大根堆
size()
empty()
push()
插入一个元素
top()
返回堆顶元素
pop()
弹出堆顶元素
定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>> q
;
(6). stack
, 栈
size()
empty()
push()
向栈顶插入一个元素
top()
返回栈顶元素
pop()
弹出栈顶元素
(7). deque
, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
(8). set
, map
, multiset
, multimap
, 基于平衡二叉树(红黑树),动态维护有序序列
size()
empty()
clear()
begin()/end()
++
,--
返回前驱和后继,时间复杂度 O(logn)
(1) 输入是一个数x,删除所有x
O(k + logn)
(2) 输入一个迭代器,删除这个迭代器
(9).lower_bound()/upper_bound()
lower_bound(x)
返回大于等于x的最小的数的迭代器
upper_bound(x)
返回大于x的最小的数的迭代器
map/multimap
insert()
插入的数是一个pair
erase()
输入的参数是pair或者迭代器
find()
[]
注意multimap
不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
(10).unordered_set
,unordered_map
, unordered_multiset
, unordered_multimap
, 哈希表
和上面类似,增删改查的时间复杂度是O(1)
不支持 lower_bound()/upper_bound()
, 迭代器的++
,--
(11).其他
bitset
, 圧位
bitset<10000> s
;
~
, &
,|
, ^
>>
, <<
==
, !=
[]
count()
返回有多少个1
any()
判断是否至少有一个1
none()
判断是否全为0
set()
把所有位置成1
set(k, v)
将第k位变成v
reset()
把所有位变成0
flip()
等价于~
flip(k)
把第k
位取反
文章浏览阅读7.6k次。在 Ubuntu Terminal\text{Ubuntu Terminal}Ubuntu Terminal 中执行一些命令时总是需要交互式的输入信息,如 Y/N/passwd\text{Y/N/passwd}Y/N/passwd 等等,这可以起到提醒用户的作用,也更加保险。但是有的时候在执行自动化脚本时并不希望一直进行交互式的操作,所以 expect\text{expect}..._bash expect
文章浏览阅读56次。这是个线程同步的经典例子,源代码如下:[java]view plaincopy<spanstyle="font-size:16px;">packagedemo.thread;/***经典生产者与消费者问题:生产者不断的往仓库中存放产品,消费者从仓库中消费产品。*其中生产者和消费者都可以有若干个。仓库容量有限,库..._5)仓库中每次只能入一人(生产者或消费者)。 6)仓库中可存放产品的数量最多5个。 7
文章浏览阅读1.3w次,点赞10次,收藏93次。文章目录1. 统计功效与关键概念2. Z检验样本量确定2.1 统计功效公式推导2.2 样本量计算公式2.3 求解样本量3. 卡方检验样本量确定3.1 求解样本量4. 简要总结Reference在数据分析过程中,一个完整的闭环是从数据中得到洞察,根据洞察得到某种假设,通过实验检验这一假设。AB实验实际上是在做一个假设检验,可以参考上一篇笔记【概率论】- (2)假设检验,在查资料的过程中,主要有两..._abtest最小样本量确定
文章浏览阅读805次。【声明】首先,这系列文章均基于自己的理解和实践,可能有什么不对的地方,欢迎大家指正。其次,这是一个入门系列,涉及的知识也仅限于够用,深入的知识网上也有许许多多的博文供大家学习了。最后,希望大家能够有所收获。前言新房的建造,首先肯定是从地基开始架构,那么我们该如何架构好呢,请看下一步。1、构造AudioRecord我们首先通过AudioRecord的构造器,来了解下需要的参数publicAudioRecord(int audioSource, int sampleRateInHz, in_audiorecord使用
文章浏览阅读558次。转载地址:http://www.ibm.com/developerworks/cn/linux/l-assembly/_linux 汇编 调用 wire
文章浏览阅读959次。Java手写单例之饿汉式、懒汉式、双重判定锁。package org.fh.action;/** * 饿汉式 * @author Administrator * */public class Singleton { /** * 私有的 final 修饰的变量 不能被二次赋值 */ private static final Singleton singleton = n..._1、手写单例(懒汉、饿汉、双锁安全全部写一遍)
文章浏览阅读577次。一、二维数组的介绍 当数组元素具有两个下标时, 该数组称为二维数组。 二维谁可以看做具有行和列的平面数据结构。二、二维数组的定义 定义二维数组的形式: 数据类型 数组名[常量表达式1][常量表达式2] ; 数据类型是数组全体元素的数据类型, 数组名用合法的标识符表示, 两个整型常量表达式可以理解为分别代表行数和列数, 与一维数组相同, 数组元素的下标一律从 0 开始..._pycharm 二维数组
文章浏览阅读46次。ametor阮一峰:蒙特卡罗方法入门发表于2016/4/24 10:26:54 84人阅读分类: 算法作者:阮一峰日期:2015年7月27日本文通过五个例子,介绍蒙特卡罗方法(Monte Carlo Method)。一、概述蒙特卡罗方法是一种计算方法。原理是通过大量随机样本,去了解一...
文章浏览阅读3.4k次。1、简单介绍 sysbench是一个开源,模块化的多线程性能测试工具,可以用来进行硬件环境性能测试,也可进行数据库的性能测试。但是由于需要支持DM测试,所以我们一般使用源码进行编译。2、运行方法 sysbench通过运行lua脚本进行数据库测试。而每次测试都分为prepare、run、cleanup这三个步骤,分别对应数据准备,运行测试,数据清理。每一次测试都是一个闭环,必须严格按照这三步来进行操作,不然会报错。 使用sysbench源码进行编译测试时,由..._stmt handle to the limit the number of statements or system of memory
文章浏览阅读4.7k次。胜利往往伴随着放弃不切实际的幻想。当地时间2月26日,美国、英国、欧盟与加拿大发表共同声明,宣布将俄罗斯主要银行从SWIFT体系中剔除。SWIFT凭借着其强大的制裁效果,在民间一直有着金融核武器之称,因此这一劲爆消息引发了全网的热议,不少人认为此举将对于俄罗斯经济产生巨大影响;也有人认为,我国也要对此未雨绸缪,加强跨境人民币系统CIPS系统的建设;而最乐观的看法是SWIFT是一把伤敌一千自损八百的双刃剑,美国一旦把SWIFT的牌打出来,那么也就意味着美元的金融霸权即将走向终结。个SWIFT到.._swift作为进口商有什么顾虑
文章浏览阅读108次。唐僧呈交给唐太宗的这份取经报告,绝对是前无古人,后无来者,世界一流水平。对于现代公务员写公文而言,的确有值得学习借鉴的高深之处!尊敬的唐太宗陛下:我叫唐三藏,又名唐僧。为弘扬佛法,普度众生,超度亡魂。根据《公元627年大唐工作安排》(唐发[627]1号)的精神,成立唐三藏取经办公室,奉命到西天拜佛求经。取经办公室师徒4人历时14年,行程十万八千里,经历九九八十一难,终于取得了我佛大乘真经,圆满地完..._唐僧的工作报告,堪称史上最牛
文章浏览阅读109次。1. 标识符的作用域与可见性 1.1 作用域 标识符的作用域包括:函数原型作用域、局部作用域、类作用域、命名空间作用域 (1) 函数原型作用域:函数的参与的作用域就是从函数的开始到结束 (2) 局部作用域:void fun(int a){ int b = a; cin>>b; if(b>0) ..._c++数据的共享和保护实验总结