- 博客(149)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 C++知识点大全（第二版）
贝尔实验室20世纪80年代(1979)变量声明向编译器保证变量以给定的类型和名称存在，这样编译器在不需要知道变量完整细节的情况下也能继续进一步的编译。可以在 C++ 程序中多次声明一个变量，但变量只能在某个文件、函数或代码块中被定义一次。多个变量赋同一个值时，需要分别赋值。//错误x = y = z;extern 数据类型 变量名;数据类型 变量名1,变量名2,...变量名n;// 变量声明{// 变量定义int a, b;// 初始化a = 23;b = 25;
2022-10-24 22:00:53
4051
2
原创 霍夫曼树（Huffman Tree）
给定N个权值为N的叶子节点，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也成为霍夫曼树。霍夫曼树是带权路径长度最短的树，权值最大的节点离根较近。......
2022-08-29 19:00:00
1931
1
原创 2021CSP入门级第一轮认证详细解析
预计阅读时间：10分钟1.单选题（2分）以下不属于面向对象程序设计语言的是（ ）。A.C++B.PythonC.JavaD.C解析：C语言并非面相对对象，而是面向过程。答案：D2.单选题（2分）以下奖项与计算机领域最相关的是（ ）。A.奥斯卡奖B.图灵奖C.诺贝尔奖D.普利策奖解析：奥斯卡奖是电影奖，诺贝尔奖是诺贝尔遗嘱里的5个奖，普利策奖是新闻奖，图灵奖是计算机领域的奖项。答案：B3.单选题（2分）目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。A.二进制B.十进制C.八进制D
2022-08-23 22:36:48
4142
3
原创 2023CSPJ题解
本题直接推公式就能做。用两个变量分别存储所有苹果被拿走的天数和最后一个苹果被拿走的天数。本题不需要用数组标记，只需要每次将当前苹果数减去拿走的苹果数，得到拿走之后的苹果数，每次再判断一下最后一个苹果有没有被拿走即可。
2023-10-24 21:08:58
354
原创 “背包”相关题目笔记
因为加入了附件，所以我们用zhuW表示主件费用，用zhuC表示主件价值；同样，用fuW表示附件费用，用fuC表示附件价值。可以把40个数左右分开，对两边的数进行分别枚举子集，用一个数组将子集组合存起来即可。这道题只是在原本背包的基础上加入了求背包的组数，在读如数据时求出即可。1.选，剩余重量减去该物品重量，总价值奖赏该物品价值；4.选，且选择1、2号附件；2.选，且选择1号附件；3.选，且选择2号附件；1.选，但只选择主件；
2023-07-31 23:08:27
189
1
原创 “搜索”相关题目笔记
题目传送门众所周知，宽搜是一层一层搜，直到发现目标。宽搜主要使用队列 ，从起点开始，只要遇到合法的点，直接压入队列尾端。每次处理从队首弹出进行处理，搜索到新元素就放到队尾。如果全都处理完了，还是没有目标点，就是无解；如果遇到目标点，就结束搜索。而深搜是一条道走到黑，就像二叉树一样，一直一直走左子树，直到叶子结点，再回到上一个父亲节点，再走右子节点，一直一直走。只要发现有解，直接结束。深搜在实践上，经常使用到递归和回溯。在走过的节点上进行标记，避免重复搜索或死循环。话不多说，上题目。
2023-07-30 20:51:04
128
原创 P1058 [NOIP2008 普及组] 立体图
小渊有一块面积为 $m \times n$ 的矩形区域，上面有 $m \times n$ 个边长为 $1$ 的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是 $1$），小渊想请你打印出这些格子的立体图。接下来的 $m$ 行，是一个 $m \times n$ 的矩阵，每行有 $n$ 个用空格隔开的整数，其中第 $i$ 行第 $j$ 列上的整数表示第 $i$ 行第 $j$ 列的格子上摞有多少个积木（$1 \le $ 每个格子上的积木数 $ \le 100$）。\quad\textsf{高}\\。
2023-07-24 18:49:21
62
原创 并查集(Union-Find Disjoint Sets/DSU)
并(unity)查(find)集(set)，即可以合并、查找的树状数据结构，常用于处理不交集查询问题。图1图1中每个箭头两端连接的是两名呈同班同学关系的学生，请问，1号同学和5号同学是同一个班的吗？我们简化一下，就是如果我们能确定任意两个人之间是不是同班同学，我们能不能确定所有同学之间是不是同班同学。在简化，在同一个班的学生里，指定一个老大(t),当查询两个学生（x,y）时，只需要看者两个学生是否与老大间接认识或直接认识，如果都认识，那么者两个学生就在同一个班里。
2023-07-22 19:45:53
110
原创 1752:鸡兔同笼
一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个0，中间用一个空格分开。一行，一个正整数a (a < 32768)。希望本博客对大家有所帮助。
2023-01-19 21:09:55
332
原创 贝尔曼-福特算法(Bellman-Ford)
在边权可正可负的图中，环游零环、正环、负环3种。如果包含零环或正环，去掉以后路径不会变长；如果包含负环，则意味着最短路不存在。既然没有环，最短路最多只经过不含起点在内的n-1个节点，可以通过n-1“轮”松弛操作得到。上述算法就是Bellman-Ford算法。我们也可以用FIFO队列来代替上面的循环检查。当负权值存在时，最短路不一定存在，但还是有办法在最短路存在的情况下求出来的。如果最短路存在，则一定存在一个不含环的最短路。以上就是本文的全部内容啦！时间复杂度：O(nm)。
2022-12-29 17:21:14
317
2
原创 二分图(Bipartite Graph)
二分图の定义二分图又叫二部图，是图论中的一种特殊模型。假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，就可以称图S为一个二分图。简单来说，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。二分图の匹配。
2022-12-28 15:55:52
11218
2
原创 迪科斯特拉算法(Dijkstra Algorithm)
Dijkstra算法是用于解决单源最短路径问题的贪心算法。先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
2022-12-28 15:45:17
387
原创 线性筛(Linear Sieve)
线性筛，即欧拉筛，比起埃及筛，优点就是每个数直筛一遍。线性筛的思想是“这个合数只会被它的最大非自身因数（对应最小质因数）筛”。线性筛的时间复杂度为O(n)。
2022-12-23 18:50:02
766
原创 霍夫曼树：霍夫曼编码(Huffman Tree:Huffman Coding)
预计阅读时间：10分钟接上回 之前我们了解了霍夫曼树，今天我们来了解一下霍夫曼编码。 霍夫曼树常处理符号编写工作。根据整组数据中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。相关术语 霍夫曼编码就是再霍夫曼树上进行实现的。 从树根开始，从待译电文中逐个取码。若编码为0，就往左走；编码为1，就往右走，一旦到达了叶子节点，就是译出了一个字符；在从根出发，直到电文结束。 T:00 ;:00 A:10 C
2022-12-03 17:59:14
1196
原创 空间复杂度(Space Complexity)
预计阅读时间：5分钟 随着计算机空间的发展，空间复杂度逐渐变得不那么重要了，但它在比赛中仍然存在。 tips：O(1) < O(logN) < O(N) < O(N^2) < O(2^N) 1、常数 O(1) ： 普通常量、变量、对象、元素数量与输入数据大小 N 无关的集合，皆使用常数大小的空间。 如以下代码所示，虽然函数 test() 调用了 N 次，但每轮调用后 test() 已返回，无累计栈帧空间使用，因此空间复杂度仍为 O(1
2022-12-03 16:02:12
487
原创 时间复杂度(Time Complexity)
预计阅读时间：5分钟 时间复杂度，又叫时间复杂性，也就是我们常说的大O。时间复杂度是不容忽视的衡量算法好坏的重要指标。 时间复杂度是一个函数，用于描述该算法的运行时间。 举个简单的例子：一个20米的木头，一群蚂蚁三年吃一米，那吃掉整个木头要多少年？答案是20*3=60年。那木头是N米呢？那就需要3N年。如果这是一个函数，就可以记作T(N)=3N。 时间复杂度就是把T(N)化简为一个可以是N，,等等的数量级。 那如何推导时间复杂度呢？
2022-12-03 15:32:15
791
原创 弗洛伊德算法(Floyd-Warshall)
弗洛伊德算法又名插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。弗洛伊德算法是一种在具有正或负边缘权重但没有负周期的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度（加权）。虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径。该算法的版本也可用于查找关系R的传递闭包，或在加权图中所有顶点对之间的最宽路径。
2022-11-29 17:09:04
2888
原创 链式前向星(Chain Forward Star)
一、简介其实就是链表写法的邻接表改成数组来实现，不直接使用指针，用数组下标间接代替指针的作用。参考链表实现邻接表：1.链表中每插入一个边，是采用头插的方法，这里的思路也是头插；2.链表访问的结尾采用的是NULL，这里采用的是-1；而且我们经常直接使用（~i）作为循环的结束，因为对-1进行取反操作，可以直接得到0（-1在计算机内以补码存储，为11111111，取反即00000000）
2022-11-05 16:18:01
367
原创 前向星(Forward Star)
前向星是以储存边的方式来存储图的数据结构。构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序，如下面例程)，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。前向星的时间复杂度为O(m)，m为边数。总体时间并不会逊色于邻接表。
2022-11-05 16:01:24
1428
1
原创 双端队列(Deque)
deque，即双端队列(double ended queue)，是一种可以在两端扩展或收缩的序列化容器。deque是C++ 标准模板库的一部分，想要使用deque，需要在程序中包含头文件deque。规定了deque中可以存放哪种类型的元素。为deque名。
2022-11-05 15:12:33
12165
2
原创 顺序查找(Sequential Search)
为了避免顺序查找过程的每一步都要检测整个表是否查找完毕，查找之前需要先将key赋予a[0]的关键。如果数据量很大很大，顺序查找显然是不能用了，那我们应该用什么查找呢？按相应顺序进行查找，直到找到目标数据。
2022-10-29 16:36:37
394
原创 二叉查找树（BST）
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为 O ( log n )。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。二叉查找树是能够高效地进行如下操作的数据结构。插入一个数值查询是否包含某个数值删除某个数值。
2022-10-29 16:34:04
1215
原创 04:奇偶ASCII值判断
例如，字符A的ASCII值是65，则输出YES，若输入字符B(ASCII值是66)，则输出NO。任意输入一个字符，判断其ASCII是否是奇数，若是，输出YES，否则，输出NO。如果其ASCII值为奇数，则输出YES，否则，输出NO。使用getchar进行字符的读取。希望本博客对大家有所帮助。元培-From Whf。
2022-10-29 16:24:16
405
原创 广度优先搜索(BFS)
广度优先搜索（Breadth First Search）又名宽度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。图1 广度优先搜索广度优先搜索适合找最优解，如图1所示：1就是从0到1；2就是从0到2；
2022-10-29 13:58:27
2821
原创 快速排序(Quick Sort)
快速排序是由东尼·霍尔所发明的排序算法。事实上，排序算法通常明显比其他算法更快，因为它的内部循环可以在大部分框架上很有效地被实现出来。
2022-10-29 13:49:11
154
原创 归并排序(Merge Sort)
归并排序是创建在归并操作上的一种有效的排序算法，与1945年由冯·诺伊曼提出。归并排序的实现分为递归实现与非递归（迭代）实现。递归实现的归并排序是算法设计中分治策略的典型应用，可以讲一个大问题分割成若干个小问题解决，然后用所有小问题的答案解决整个大问题。分递归（迭代）实现的归并排序首先进行的是两两归并，然后是四四归并，接着是八八归并，一只到归并完整个数组。
2022-10-29 13:47:57
515
原创 堆排序(Heap Sort)
对排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆排序是用一维数组实现的），并满足性质：以最大堆为例，其中父节点的值总是大于起孩子节点的值。
2022-10-29 13:46:34
86
原创 插入排序(Insertion Sort)
插入排序是一种简单直观的排序算法，他的工作原理与抓扑克牌非常类似。插入排序的工作原理是：对于未排序数据（右手抓到的牌），在一排序序列（左手已经排好序的牌）中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用in-place排序（即志勇到O(1)的额外空间的排序），因此在从后向前扫描的过程中需要反复将以排序的元素逐步向后移位，为新元素提供插入空间。
2022-10-29 13:45:00
270
原创 选择排序(Selection Sort )
选择排序也是一种简单直观的排序算法，工作原理是：开始时在序列中找到最小（大）的元素，放到序列的其实位置作为已排序序列，然后从生于未排序的元素中寻找最小（大）的元素，放到一排序序列的末尾。以此类推，直到所有元素均排序完毕。
2022-10-29 13:43:05
860
原创 冒泡排序(Bubble Sort)
冒泡排序（Bubble Sort)的名字由来是因为越小（或者越大）的元素回经由交换慢慢“浮”到数列的顶端，就像气泡一样。
2022-10-29 13:41:24
436
原创 二叉搜索树(BST)
一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。（3）既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s。（2）仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2022-10-24 22:13:16
170
原创 顺序表（Contiguous List）
用一组地址连续的存储单元依次存储线性表中每个数据元素的数据结构名叫顺序表。顺序表的逻辑关系相邻的两个元素在物理位置上也相邻。
2022-10-24 21:50:28
171
原创 堆(Heap)
要想真正了解堆，就需要先了解二叉树。树和二叉树(Tree&Binary Tree)_Hacker_徐的博客-CSDN博客树是一种非线性的数据结构，它在表示机构的组织关系图等方面非常好用，树的示意图如图1所示。图1 - 树的示意图。堆是所有树中最具有特点的树，因为它是用数组存储的，并且总是完全二叉树。
2022-10-22 21:32:31
430
原创 03:奇偶数判断
输出仅一行，如果n是奇数，输出odd；如果n是偶数，输出even。给定一个整数，判断该数是奇数还是偶数。输入仅一行，一个大于零的正整数n。北京大学 计算概论 06。希望本博客对大家有所帮助。
2022-10-22 16:23:04
114
原创 02:输出绝对值
输出这个浮点数的绝对值，保留到小数点后两位。输入一个浮点数，其绝对值不超过10000。输入一个浮点数，输出这个浮点数的绝对值。希望本博客对大家有所帮助。
2022-10-22 16:21:15
353
c++高精度加减乘除计算器
2022-08-03
我这个代码哪里错了啊
2022-08-12
TA创建的收藏夹 TA关注的收藏夹
TA关注的人