数据结构3Accepted6

数据结构3Accepted6 Hash表

拉链法

#include 
#include 

using namespace std;

const int N = 100003;// 数学上可以证明模取质数时，冲突概率最小。大于100000的最小质数为100003

//h[]头结点指针，e[]存放数据，ne[]存放指针，idx当前下标
int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;// 先模再加再模，C++中负数求模还是负数
    
    // 和单链表里面一样
    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])// i从头结点开始，只要不为空指针，一直找，直到找到
    {
        if (e[i] == x)
        {
            return true;
        }
    }
    
    return false;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    memset(h, -1, sizeof(h));// 按字节
    
    while(n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if (op[0] == 'I') insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

开源地址法

#include 
#include 

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;// null大于10的9次方，0x3f3f3f3f=1061109567

int h[N];

int find(int x)
{
    int k = (x % N + N) % N;
    
    while (h[k] != null && h[k] != x)// 当前位置不为空，并且当前位置上的数不等于x，k看下一个
    {
        k ++ ;
        if (k == N ) k = 0;// k看完所有位置，返回第一个位置
    }
    
    return k;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    memset(h, 0x3f, sizeof(h));// 初始化为0x3f
    
    while(n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        int k = find(x);
        if (op[0] == 'I') 
        {
            h[k] = x;
        }
        else
        {
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

字符串前缀哈希法

#include 

using namespace std;

typedef unsigned long long ULL;// 取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

const int N = 100010, P = 131;// 将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低

int n, m;
ULL h[N], p[N];// h[k]存储字符串前k个字母的哈希值，p[k]等于P^k mod 2^64，存放各位相应的权值
char str[N];

ULL get(int l, int r)// 计算子串str[l~r]的哈希值，l和r范围为1~n
{
    return h[r] - h[l - 1] * p[r - l + 1];// 将h[l-1]左移，使h[l-1]的高位与h[r]相对齐从而才可以未完成计算
}

int main()
{
    scanf("%d%d%s", &n, &m, str + 1);
    
    // 初始化
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = p[i - 1] * P; // 计算每一位相应的权值
        h[i] = h[i - 1] * P + str[i];// 计算字符串前缀值，最新加入的数的权值为p的0次，所以直接加上str[i]即可
    }
    
    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

C++ STL简介

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair pair是将2个数据组合成一组数据。通过嵌套可以实现不止两个
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string, 字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址
    
 queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  d出队头元素
    没有clear()函数，例:queue q;想清空的话，q = queue();

priority_queue, 优先队列，默认是大根堆。#include 
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  d出堆顶元素
    定义成小根堆的方式：priority_queue, greater> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  d出栈顶元素

deque, 双端队列。用的不多，比数组效率慢很多。
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
	size()
	empty()
	clear()
	begin()/end()  ++, -- 返回前驱和后继，时间复杂度 O(logn)

	set/multiset
		insert()  插入一个数
		find()  查找一个数
		count()  返回某一个数的个数
		erase()
			(1) 输入是一个数x，删除所有x   O(k + logn)
			(2) 输入一个迭代器，删除这个迭代器
		lower_bound()/upper_bound() 注意，这两个函数的含义是相近的，不是相反
			lower_bound(x)  返回大于等于x的最小的数的迭代器
			upper_bound(x)  返回大于x的最小的数的迭代器
	map/multimap, 映射
		insert()  插入的数是一个pair
		erase()  输入的参数是pair或者迭代器
		find()
		[]  时间复杂度是 O(logn)
		lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 基于哈希表序列
		和上面类似，增删改查的时间复杂度是 O(1)
		缺点：不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
	bitset<10000> s;
	~, &, |, ^  取反，与，或，异或
	>>, <<  移位
	==, !=
	[]
	
	count()  返回有多少个1
	
	any()  判断是否至少有一个1
	none()  判断是否全为0
	
	set()  把所有位置成1
	set(k, v)  将第k位变成v
	reset()  把所有位变成0
	flip()  等价于~
	flip(k) 把第k位取反