深入分析java中的priorityqueue底层实现与源码-编程思维

本文分享自华为云社区《滚雪球学Java(70):深入理解Java中的PriorityQueue底层实现与源码分析》,作者: bug菌。 环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8 @[toc] 前言 PriorityQueue是Java中一个非常常用的数据结构,它可以实现基于优先级的排序,常用于任务调度、事件处理等场景。本文将深入探讨

c语言实验报告六——指针-编程思维

题目:编写一个函数,求1~m之间(含m)能被7或11整除的所有整数并放在数组a中,在main函数中输出这些数和这些数的个数。 例如:若m的值为50,则程序输出:       7  11  14  21  22  28  33  35  42  44  49        总数:11 思路: 声明一个数组 a 存储1到50的整数。使用循环填充数组

南外集训 2024.2.23 t3-编程思维

Kubic 素质如此,如何国家队? 有一个初始为空的序列,对其进行 \(q\) 次操作(强制在线)。操作分为两种: \(1\;x\) 表示在序列末尾插入一个 \(x\)。 \(2\;x\) 表示询问当前序列中长度等于 \(x\) 的区间的价值之和 \(\bmod 998244353\)。 定义一个区间的价值为中前 \(m\) 大的数的乘积,其中 \(m\) 是给定的常数。如果区间长

数据结构【树状数组】-编程思维

树状数组是线段树的衍生产物,牺牲了部分通用性,节约了空间,且大大减少了手写码量, 借助树状数组,我们可以用O(logN)的时间复杂度来实现给定序列中长度为n的区间中元素和的计算。 https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from=333.337.search-card.all.click&vd_source=5795184

树状数组区间修改区间查询-编程思维

树状数组区间修改区间查询 问题——两种操作 给定 \(l,r,x\) ,将 \([l,r]\) 这个区间内的所有值都加上 \(x\) 给定 \(l,r\) 求出 \([l,r]\) 的区间和 这道题肯定要用前缀和和差分,那么大体框架可以出来了 //操作一: update(l, x), update(r + 1, -x); //操作二 query(r) - query(l - 1) 那么怎么

gdkoi2023 错排-编程思维

逆天。 转化后的题意 \(q\) 组询问,求有 \(n-m\) 个自由元素,\(m\) 个限制元素的错排问题。 \(1\le n, m, q\le 2\times10^5\) 首先写出三种组合意义的转移方程: \[\begin{aligned} f(n, m) &= f(n,m-1)-f(n-1,m-1) & (1)\\ f(n, m) &= (m-1)f(n-1,m

树状数组复习-编程思维

基本原理 树状数组的原理简单来说就是利用二进制拆分区间 我们可以对一个数进行二进制分解,最多分解成log(x)个数,同样我们可以对[1,n]这个区间进行分解。也是最多log段,每次修改时我们维护受到影响的区间,然后查询时用这log个区间拼凑出一个前缀。这就是树状数组的大概思想。 最基本的作用是动态维护前缀和 在定义树状数组时,我们定义\(c[i]数组\) \(c[x]=\sum_{i=x-low

邓俊辉数据结构学习-0-绪论-编程思维

邓俊辉数据结构学习笔记 绪论 知识储备 离散数学基础 概率基础 如何评价一个算法 渐进分析:大O记号 问题:随着规模的增长,计算成本如何增长? 这里关系的是足够大的问题。 即当 n >> 2的时候 需执行的基本操作次数:T(n) = ? 需占用的存储单元数:S(n) = ? // 有时候,不考虑,为什么? 目前还不明白 估算能力大成: 像呼吸一样估算。 算法分析的俩个任务 正

邓俊辉数据结构学习-1-向量-编程思维

向量 根据基本的概率论知识,要求样本随机,且元素需要足够大,来保证其分布。 实际过程中,插值查找往往使用在大规模下,中小规模使用二分查找或者顺序查找 简介 向量本身其是就是一个封装了的数组。或者说是抽象的数组。使我们在使用的时候不用在意数组的大小。 ADT 与成员 事先说明 Tips 这里主要注意语义的问题。即所有的数据结构接口的语义尽量相同,从而在掌握一个后对其他接口 的操作也很容易掌握

邓俊辉数据结构学习-2-列表-编程思维

列表 stl中的列表实际上是双向列表 列表节点ADT 成员 功能 data 数据域 pred 直接前驱 succ 直接后继 接口 功能 insertAsPred 作为直接前驱插入 insertAsSucc 作为直接后继插入 将插入的接口写在了列表中。没有想到过的设计。 复习下双向列表的插入。 template <typename T&

邓俊辉数据结构学习-3-栈-编程思维

栈的学习 栈的应用场合 逆序输出 输出次序与处理过程颠倒,递归深度和输出长度不易预知 不是很理解 实例:进制转换 大致思路:对于进制转换,我们一般使用的都是长除法,因此要保存每次得到的余数,但是最后算下来 新的进制的数,刚好和存储的时候是逆序的。因此利用栈输出即可。原因是栈是FiLo后进先出。 递归嵌套 具有自相似性的问题可递归描述,但分支位置和嵌套深度不固定 实例:括号匹配,

邓俊辉数据结构学习-4-队列-编程思维

队列的学习 队列的模拟 使用数组对循环队列进行模拟的时候,必须放弃一个位置。 关于模板类继承之后派生类使用基类接口,需要使用基类的作用域限定。 队列的底层,如果不考虑空间的话,使用vector比较好,否则使用双向链表,主要delete太耗时间。 队列的应用 RoundRobin轮盘机制 RoundRobin 对某项资源进行轮流分配 void RoundRobin() { Que

邓俊辉数据结构学习-5-树-编程思维

树 树的一些结论 度: 一个节点的孩子数称为度。 一颗树的边数 = 节点数n - 1 意义在于衡量算法复杂度时使用。 树的特性 路径(通路) + 环路 通路: a, b 之间通过节点连接成的路。 * 长度:所有边的数目(有些文献使用节点定义长度) 环路:通路的俩个节点彼此短路,即重合构成环路。eg. a - b - c - d - b 连通图:节点之间均有路径 无环图:没

邓俊辉数据结构学习-6-图-编程思维

图 术语 俩个要素 顶点集和边集。分别使用V和E来表示 邻接关系: 指的是俩个顶点之间的关系。 关联关系: 指的是顶点和边之间的关系。 极大顶点: 图如果再加一个顶点,图就不连通了。 有向图和无向图 主要研究有向图,有向图可以转化为无向图 路径 简单路径:路径中不含重复节点。 普通路径:路径中可能含有重复节点。 环路:路径的起始点和终点相同。 简单环路:除了起始点外不包含任何重复的

邓俊辉数据结构学习-8-1-伸展树-编程思维

高级搜索树--伸展树 对于维护平衡因子,感觉很麻烦,希望抛弃掉平衡因子,使用更加潇洒的模式。 要求: 对于伸展树来说,也不做过多掌握 主要明白利用数据的局部性,我们可以实施的新策略 概述 背景知识补充: 数据局部性 刚被访问过得数据很快会被再次访问 因此这一次访问过的节点,极有可能再次被访问, 能够实现这种特性的树就是伸展树--就像自适应链表一样 新的名词: 自适应链表 在某一段时

邓俊辉数据结构学习-8-2-b树-编程思维

B树 概述 动机: B树实现高速I/O 640K如何"满足"任何实际需求了-- 源自比尔·盖茨的一个笑话 前提知识 高速缓存 为什么高速缓存有效? 不同容量的存储器,访问速度差异悬殊,磁盘和内存访问速度的量级相差\(>10^5\) 如果将访问内存比喻为1秒,那么访问外存则相当于1天 因此我们需要尽量减少IO次数 分级I/O 俩个相邻存储级别之间的数据传输,统

邓俊辉数据结构学习-8-3-红黑树-编程思维

红黑树 动机 Q: 在已经有了AVL之类的BBST,为什么还需要引入红黑树? A: 我们希望数据结构具有关联性,即相邻版本之间,比如说第一次插入,和第二次插入时,树的结构不能发生太大变化, 应该可以经过O(1)次数就可以变化完成。 对于AVL树来说,插入是满足这个条件的,删除却不满足这个条件。 红黑树就满足这一特性,插入和删除操作后的拓扑变化不会超过O(1)。 定义 前提:给红黑树添加外部节点,