转载
AI tools such as ChatGPT will disrupt hydrology, too
:root{--sf-img-23: url("data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHdpZHRoPSIyNCIgaGVpZ2h0PSIyNCI+PHBhdGggZD0iTTcuNDA2IDcuODI4TDEyIDEyLjQyMmw0LjU5NC00LjU5NEwxOCA5LjIzNGwtNiA2LTYtNnoiIGZpbGw9IiNmZmYiIHN0cm9rZT0iI2ZmZiIvPjwvc3ZnPg==")}#000;border-color:#000;stroke:#fff}.osano-cm-info-dialog-header__close:hover{stroke:#141414}.osano-cm-info-dialog-header__close:focus:hover{stroke:#ebebeb}.osano-cm-button:focus,.osano-cm-button:hover{background-color:#5f95fc}.os ...
数据结构与算法
【算法】插入排序与希尔排序的一些理解
本章讲解了插入排序与其升级版–希尔排序的主要思想与代码实现。
🤑插入排序
插入排序是最简单的一种排序方法,其本质就在于不断从后向前插入。
意思就是,将待排序序列的第一个当做有序序列,然后将第二个往前插入,要求升序则将两数中较小的那个排至最前面,降序则把较大的放在最前面。这样操作一次就把前两个数变成了一个有序数列,同理操作第三个数,第四个数·······直到将整个数列排列完成。
以下是一张动图,可以直观感受插排的过程。
图源菜鸟教程。
就像是打牌一样,将手中的牌进行整理,按照一个顺序依次排好。
思想清楚了就可以写代码了,先书写单趟的循环(这里写的是升序)。
我们将每次排好序的队列的下标的最后一位定为end,那么需要往前插入的就是处在end+1的元素。将这个元素暂存在tmp中,并向前比较,遇到比他大的则依次向后放。
123456789101112int end; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; ...
数据结构与算法
【算法】二叉树里的层序遍历与完全二叉树的判断
本篇文章主要是填上一篇的层序遍历的坑,具体的讲解层序遍历的代码实现与完全二叉树的判断。
💿思想
在之前就已经提到过,层序遍历就是一层一层的按顺序遍历,也是几种遍历中最简单明了的,但其实现相比于前序中序这种巧用递归思想的在代码书写中却要复杂不少。
给出一棵树:
我采取的办法是建立一个队列,然后将根节点进行入队,此时队伍里就只有根节点,将根节点出队,同时将其两个孩子按顺序入队。
之后要执行的操作就是不断的进行出队,在出队的同时将出队元素的两个孩子进行入队,当队列为空后,整个出队的顺序就是层序遍历的顺序了。
📀队的函数
既然要入队,首先肯定是建立一个队列的结构及其功能的实现。
在上述的思想中,我们肯定会用到初始化队列,入队,出队,取队头四种功能。
还有队的销毁,这点很重要,为了防止内存泄漏,一定要牢记malloc的节点如果不用就要销毁掉!
先是书写队列的结构,那么考虑队列里放什么类型呢?答案是指针,如果存放的是树结构里节点的值,那么在出队后,将其左右孩子进行入队就会很麻烦,因为单一的值是无法连通前后的!
1234567891011121314typedef struct Bina ...
数据结构与算法
【算法】链式二叉树里的遍历与分治思想
在上一篇里我讲到了使用数组来模拟二叉树,也就是物理结构虽然是动态开辟的数组,但其逻辑上我们却认为其是一棵二叉树,每个节点都与对应的节点有着父或者子的关系。这一篇使用的是链式存储的二叉树,使用结构体为每个节点开辟空间,讲解四种遍历,并使用到了分治的思想来求解二叉树的节点个数与高度等问题。
💑链式存储
定义一个结构体,其包含值(本章定位int),两个指针,分别指向其两个孩子,也可以没有指向,当不存在左孩子或者右孩子时,其指针指向NULL。
用图表示其关系即如下:
12345typedef struct binarytreenode { int val; struct binarytreenode* left; struct binarytreenode* right;}btnode;
这一步很常规,没有什么值得深入的。
再写一个创建节点的函数。
12345678btnode* creatnode(int x) { btnode* newnode = (btnode*)malloc(sizeof(btnode)); newnode->left = ...
数据结构与算法
【算法】堆和堆排序
📲堆
🏒概念
以下源自百度百科对堆的解释说明。
堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
堆中某个结点的值总是不大于或不小于其父结点的值;
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构,相当于一维数组,有两个直接后继。
若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
(以上源自百度百科)
堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
$$
k_i<=k_{2i+1}且k_i<=k_{2i+2}
$$
这种则被称为小堆,其父节点小于他的两个子节点。
$$
k_i<=k_{2i+1}且k_i<=k_{2i ...
刷题
【leetcode】设计循环队列
来源:622.设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为环形缓冲器。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQ ...
刷题
【leetcode】巧解深度拷贝“带随机指针”的链表
题目来源:leetcode 138.复制带随机指针的链表
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 hea ...
刷题
【leetcode】双指针巧解判断链表是否有环的问题
本章讲述的例题来自leetcode 141.环形链表1,142.环形链表2,旨在利用双指针解决此类型的问题。
💻141.环形链表1
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
解法:本题可以思考转换为追击问题 ...
数据结构与算法
【算法】快速排序,归并排序,两种二分的模板干货讲解,附带边界问题的分析。
前言:本篇内容会总结快速排序与归并排序两种常见的排序以及整数二分,浮点数二分,并给出相应的模板代码与示例题目。在代码的讲解过程中也会附带讲解让人头疼的边界问题,到底如何划分区间,划分后又该如何设定参数。
📣快速排序
🥗 基本思想
快速排序的中心思想就是分治算法。其操作过程就是在区间上选定一个值,然后排序整个数组,使得值左边的都小于它,右边的都大于它,然后整个数组就被分成了两段,分治的思想就体现在这里,分别在左右两个数组里取一个值,又继续上述的操作,直到只剩一个数。
比如给出一个数组
{1,3,6,4,7,8,9,3,4}
我们以(左边界+右边界>>1)为每次确定的值的下标,那么取到的第一个值就是7,我们需要进行的操作就是将比7大的排到7右边,比7小的排到7左边。‘
可以得到如下结果
{1,3,6,4,3,4}{7}{8,9}
此时7就被放到了最合适的位置,只需要分别排序左右两个数组即可。
上述的便是快排的基础思想。最初的快排是由hoare提出的,经由后人的不断优化有了多种的版本。
🍌hoare版快排
在开篇时谈到其中心思想是分治,需要找到区间中的一个值来作为分隔 ...
c/c++
【c】简述内存中数据如何存储?动态内存该如何分配?
😍在本章的内容里会详细的介绍在c语言的程序中,整型int与浮点型float是如何进行存储的,以及动态分配的一些基础知识点。
🥕数据类型
数据类型在初始c语言的阶段就已经与大家见过面了。基本上可以分为以下几种基本的内置类型:
1234567char // 字符数据类型short // 短整型int // 整型long // 长整型long long// 更长的整型float // 单精度浮点数double // 双精度浮点数
通常就上述的七种类型就可以满足我们的日常需要了。
那么开始进入正题。
🥔类型的分类
在c语言中,我们大致将数据类型分为五大类。其具备不一样的特点。
整型
1234charshortint long
整型基本就为上面四种,将字符型归入整型是因为字符型在存储时是以asc码的形式,而asc码又是整数,故将其归纳在整型之中了。
有时候我们还会见到类似这样的写法
123unsigned intunsigned shortsigned int
unsigned意思是无符号型,signed则是有符号型。其中signed int中的signed也可以省略不 ...