经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
Acwing Arithmetic Learning:数据结构(2)
来源:cnblogs  作者:~快乐王子~  时间:2021/6/28 9:42:04  对本文有异议

数据结构(2)acwing

image-20210626200453694

1.trie树

  • 快速存储和查找字符串的集合
  • 结构特征:image-20210626175138514
  • 例题:Trie字符串统计 ?

2.并查集(近乎O(1))

  • 思路
  1. 将两个集合合并
  2. 询问两个元素是否在一个集合中
  • 基本原理:

    每个集合用一颗树来表示,树根的编号就是整个集合的编号。每个节点存储他的父节点,p[x]表示x的父节点

  • 问题:

  1. 问题1:如何判断树根:if(p[x] == x)
  2. 问题2:如何求x的集合编号:while(p[x] != x) x = p[x];
  3. 问题3:如何合并两个集合:px是x的集合编号,py是y的集合编号。p[x] = y,直接上图image-20210626191315099

优化:

1.路径压缩

  1. scanf使用%s会默认忽略“空格”和"回车",不用%c
  • 上代码:image-20210626191425784

3.堆

  • 概念:”小根堆“(顾名思义{根小于左右儿子})----》为“完全二叉树”(最后一行可以不满,以上全满),上图

image-20210626195342299

  • 存储方式(一维数组存储)

    image-20210626195623804

    • x的左儿子:2x
    • x的右儿子:2x+1
  • 如何手写一个堆?

    1. 插入一个数

      1. heap[ ++ size] = x;up(size);
    2. 求集合中最小值

      1. heap[1];
    3. 删除最小值

      1. heap[1] = heap[size];size --;down(1);
    4. 删除任意一个元素

      1. heap[k] = heap[size];size --; down(k);up(k);
    5. 修改任意一个元素

      1. heap[k] = x;down(k);up(k);

原文链接:http://www.cnblogs.com/happy-prince/p/14939025.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号