欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Acwing Arithmetic Learning:数据结构(3)

程序员文章站 2022-04-14 15:11:34
数据结构(3) acwing 1.hash表 哈希函数概念: (1)x mod 10 ^5 即缩小了值域 {模的数最好取成**“质数”**:这样冲突的概率最小} (2)解决冲突 求大于i的第一个质因子 存储结构 开放寻址法 (数组开辟长度为2~3倍){涉及到操作:添加、查询、删除(只是做一个标记,并 ......

数据结构(3) acwing

目录

1.hash表

哈希函数概念:Acwing Arithmetic Learning:数据结构(3)

(1)x mod 10 ^5 即缩小了值域 {模的数最好取成“质数”:这样冲突的概率最小}

(2)解决冲突

  • 求大于i的第一个质因子

Acwing Arithmetic Learning:数据结构(3)

  1. 存储结构

    • 开放寻址法

      (数组开辟长度为2~3倍){涉及到操作:添加、查询、删除(只是做一个标记,并不真正删除)}

      • Acwing Arithmetic Learning:数据结构(3)

        Acwing Arithmetic Learning:数据结构(3)

        0x3f3f3f3f是一个大于10^9的数,在memset()函数中,其按照字节进行存储,因为h为int型数组,占用4个字节,因此写一个0x3f就够了(一个字节是0x3f)

    • 拉链法

      • Acwing Arithmetic Learning:数据结构(3)
      • Acwing Arithmetic Learning:数据结构(3)
  2. 字符串哈希

  • 所有的关于字符串匹配问题,不一定利用kmp做,也可以使用字符串哈希方式
  • 使用场景:比较两个字符串是否相等
  • kmp算法和字符串哈希比较: kmp的特点是可以处理“循环结”

核心是:将一个字符串用k进制的形式,看做是一个数字

3.stl

Acwing Arithmetic Learning:数据结构(3)

1.vector

  • size(),元素的个数

  • empty() 返回是否为空

  • clear() 清空

  • front() /back() 第一个元素 /最后一个元素

  • push_back() / pop_back() 向后面插入一个数 / 删除数组最后一个数

  • begin() / end() 第0个数 / 最后一个数的后面一个数

    Acwing Arithmetic Learning:数据结构(3)

    Acwing Arithmetic Learning:数据结构(3)

倍增:系统为某程序分配空间时,所需时间与空间大小无关,只与请求次数有关

2.string

  • size(),元素的个数
  • empty() 返回是否为空
  • clear() 清空
  • substr():截取字符串
  • c_str()​ :字符串第一个下标

初始下标为0

Acwing Arithmetic Learning:数据结构(3)

3.queue

  • empty()

  • size()

  • push(): 向队尾插入一个元素

  • front(): 返回队头元素

  • back(): 返回队尾元素

  • pop(): 弹出队头元素

4.priority_queue(就是堆)

默认是大根堆,转成小根堆的方式

  • push() :插入一个元素
  • top(): 返回堆顶元素
  • pop(): 弹出堆顶元素

5.stack

  • empty()

  • size()

  • push()

  • top()

  • pop()

6.deque(双端队列)--basically not use

相当于加强版 vector

Acwing Arithmetic Learning:数据结构(3)

7.set、multiset、map、multimap

size()、empty()、clear()、begin()/end() ++,-- 返回前驱和后继,时间复杂度o(logn)

  • set/multiset

Acwing Arithmetic Learning:数据结构(3)

  • map/multimap

Acwing Arithmetic Learning:数据结构(3)

  • unordered_set,unordered_map,unordered_multiset,unordered_multimap

    ​ 和上面类似,但增删改查的时间复杂度为o(1)

    ​ 不支持 lower_bound() / upper_bound()、迭代器的++、--

  • bitset 压位

Acwing Arithmetic Learning:数据结构(3)