- 博客(42)
- 收藏
- 关注
RSS订阅原创 高效的区间二叉搜索树：线段树
与树状数组类似，线段树也是一种用来维护区间信息的数据结构，可以在对数时间复杂度内实现更新和查询等操作。但相较于树状数组多用于前缀和查询不同，线段树的应用范围更为广泛，例如区间最值等问题，代价是需要消耗更多的存储空间。more。
2024-03-18 14:57:54
365
原创 动态前缀和数组：树状数组
前缀和是一种常见的算法思想，能够实现在常数时间复杂度下得到某个子区间内所有元素和。以一维数组 nums 为例，定义前缀和数组 preSum，preSum[i]表示 nums 前 i 个元素的和，利用动态规划的思想，易得的递推关系，因此构造一个前缀和数组的时间复杂度为 O(n)，而查询前 i 个元素的和只需查询preSum[i]的值，为常数时间。
2024-03-04 15:22:09
800
原创 从机器指令的角度看一些位级操作
C/C++ 中有时会遇到一些位级操作，通常是一些隐式的类型转换，它们往往很难凭借高级语言层面的直觉来理解或记忆。本文旨在分析这些操作对应的汇编代码，从机器指令的角度来理解这类操作。more。
2024-01-19 21:52:05
418
原创 二分搜索的几种写法与常见问题
最近在比赛和刷题的时候经常遇到二分答案的题，但时不时会因为一些细节上的错误而浪费时间，本文旨在整理常见的二分搜索的写法、二分搜索可能会遇到的一些小问题，以及C++中与二分搜索相关的库函数，以免今后再犯类似的错误。
2023-09-18 11:58:13
213
原创 算法分析与设计编程题 回溯法
中搜索状态，每种状态下需要 O(n) 时间来进行最优解的更新，因此两种算法的渐进时间复杂度都为 O(n * 2。（n 为被搜索对象的数目，在本例中为货物的总数）。由于递归回溯的本质可以看作是对一棵二叉树进行的搜索，每次选或者不选都将产生两个分支，那么所有情况的数量为 2。有没有被选择，通常用 1 代表被选择，0 代表不被选择。，关注它的 n 位二进制形式，其中 mask 的第 i 位二进制位就代表对应的货物。了，可以遍历 0~n-1 的所有整数 i，并将其右移 i 位，将。事实上，对于此类涉及。
2023-09-14 22:19:37
178
原创 王道数据结构编程题 图
已知无向连通图 G 由顶点集 V 和 边集 E 组成，当 G 中度为奇数的结点个数为不大于 2 的偶数时，G 存在包含所有边且长度为 |E| 的路径（称为 EL 路径），假设图采用邻接矩阵存储。分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表形式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径（i ≠ j）。假设图用邻接表表示，设计一个算法，输出从顶点 vi 到顶点 vj 的所有简单路径。写出图的深度优先搜索 DFS 算法的非递归算法（图采用邻接表形式存储）。
2023-09-09 22:23:23
154
原创 王道数据结构编程题 栈和队列
假设 I 和 O 分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。编写一个算法，判定所给的序列是否合法。若合法，返回 true，否则返回 false.
2023-09-09 22:21:54
206
原创 王道数据结构编程题 顺序表
从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
2023-09-09 22:18:40
134
原创 有关C++字符串拷贝的一个小问题
最近面试被问到了一个 C++ 中的小问题，就是如果有字符串 s1 和 s2，将 s1 赋值给 s2 后，它们的内存分布是什么样的。当时感觉可能是共享的，但也不太确定，回来后查阅资料发现结果并不是那么简单。more。
2023-04-04 16:49:37
115
原创 计算机基础面试题总结
大端和小端是指在多字节数据类型的存储方式中，高位字节和低位字节的存储顺序。大端模式是指高位字节存储在低地址，低位字节存储在高地址；小端模式是指低位字节存储在低地址，高位字节存储在高地址。死锁是指两个或多个进程在执行过程中，因争夺资源而造成的一种僵局，若无外力作用，它们都将无法继续执行下去。分段是将程序分成若干个逻辑段，每个段可以包含一个模块或若干个模块，每个段的长度是不固定的，每个段都有一个段名和段长，段名是一个符号，段长是指该段所包含的字节数。
2023-04-04 16:48:07
699
原创 C++面试题总结
野指针是指指向不可用内存的指针，可能会导致内存泄漏和程序崩溃。const 定义的常量是变量，带有数据类型，而 define 定义的常量是预处理器替换的文本，不带数据类型。const 定义的常量在编译运行时起作用，可以进行调试，而 define 定义的常量在预处理阶段起作用，不能进行调试。const 定义的常量可以进行作用域限制，而 define 定义的常量没有作用域的概念。const 定义的常量可以进行类型检查，而 define 定义的常量不能进行类型检查。
2023-03-24 12:41:48
389
原创 Ping命令的实现
Ping （Packet Internet Groper）是一种因特网包探索器，用于测试网络连接量的程序。本文将基于 Socket 编程，实现一个基本的 Ping 命令程序。
2022-06-03 09:43:13
1817
7
原创 使用遗传算法解决旅行商问题
遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。本文利用遗传算法解决经典的NP问题——旅行商问题，并加深对该算法的理解。问题描述有若干个城市，每个城市给定一个坐标，一个旅行商需要经过每个城市各一遍且不能重复经过城市，起点可以任意选择，求旅行商经过所有城市的总距离的最小值及其最
2022-05-26 12:57:23
6680
13
原创 停止等待协议的模拟实现
协议原理设计思路基本传输本次实验我采用了程序模拟的方式实现。发送方和接收方都为一个数组，传输过程即为发送方数组向接收方数组传递数据，并使用随机数生成的方式模拟传输过程中可能出现的差错，并且传输时间也为一个在 50 - 150 ms 间的随机数，用一个迭代器来模拟此时发送方的数据位置。传输过程为一个循环语句，终止条件为发送迭代器到达发送方数组的末尾位置。选择重传每次进行传输，传输时间就会累加，在一轮传输的最后判断累计时间是否超过了规定 tout，如果未超过，代表数据成功接收，发送迭代器自增 1。
2022-05-06 16:54:41
1229
原创 使用K-means算法进行聚类分析
本文将介绍如何使用 K-means 算法对给定的坐标数据进行聚类分析。使用K-means算法进行聚类分析问题描述K-means算法对data中数据进行聚类分析（1）算法原理描述（2）算法结构（3）写出K-means具体功能函数（不能直接调用sklearn.cluster(Means)功能函数)具体函数功能中返回值包括 数据类标签，累中心，输入包括：数据，类别数（4）可视化画图，不同类数据采用不同颜色（5）算法分析类类方差，平均方差，不同初始点对聚类结果的影响？如何解决？算法描述
2022-05-06 16:54:29
3443
原创 使用AStar算法解决八数码问题
八数码问题是一个经典的搜索问题，本文将介绍如何使用启发式搜索—— AStar 算法来求解八数码问题。问题描述八数码问题的A星搜索算法实现要求：设计估价函数，并采用c或python编程实现，以八数码为例演示A星算法的搜索过程，争取做到直观、清晰地演示算法，代码要适当加注释。八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0可自己随机设定，使用的操作有：空格上移，空格左移，空格右移，空格下移。试采用A*算法编一程序实现这一搜索过程。算法描述
2022-04-28 00:41:48
3095
原创 C++代码优化 Chapter2
本文将继续介绍一些常见的 C++ 代码优化技巧，本文为该系列的第二章，未来不定期更新。非必要时使用常量引用在上一章我们介绍了在进行函数的参数传递时，尤其对于所占内存空间较大的参数的传递，为了避免拷贝所带来的不必要的性能开销，应当尽量使用引用传递。并且，当该函数不需要对传入的参数进行更改时，应当在参数类型前添加 const 关键字表示这是一个常量引用。可能有朋友认为这里的 const 关键字的添加并不是必要的，但这样会带来两个问题：首先便是程序的可读性的下降，如果不添加 const 关键字，用户可能会
2022-04-19 15:37:19
421
原创 循环语句中指针赋值出错
最近在写人工智能作业的时候遇到了一点问题，就是在循环语句中对指针类型赋值出现错误，导致所有的结点的前驱指针最终指向自身。问题描述以下使用一个简单的示例来模拟当时出现的问题。MyStruct 为一个自定义结构体类型，包含数据成员 val 和前驱结点 pre。首先将初始结点(0，nullptr)加入队列 Q，随后在每次循环中，用变量 fs 接收队列 Q 的队首元素并将其出队，并根据该结点生成一个新结点，该新结点 val = fs.val + 1，且将其前驱结点设为 fs 并加入到队列 Q 中。直到 fs
2022-03-31 10:00:21
4759
原创 OpenGL入门 矩阵堆栈实现简单行星系统
本文介绍如何使用矩阵堆栈原理实现简单的行星运行系统。原理有时我们需要在一个场景中绘制不同的模型，如果这些模型彼此间没有联系，即各模型的位置不会相互影响，那我们只需要单独为每个模型创建合适的变换矩阵，并经过渲染管线将其渲染即可。而对于一个位置会相互影响的系统而言，例如行星运行系统，地球围绕太阳公转，而月球围绕地球公转。处理这样问题的关键在于如何确定各物体变换矩阵，准确来说是模型-视图矩阵。而矩阵堆栈可以很好地将这问题简化。所谓矩阵堆栈，就一个用来存储变换矩阵的堆栈结构，栈顶矩阵为栈底矩阵乘上另一个矩阵
2022-03-18 10:18:35
659
原创 子集生成算法
本文介绍生成一个集合子集的两种常见算法，借此从中深入理解搜索问题中常见的两种思路。递归回溯思路对于集合中的每个元素，我们都有选择和不选择两种处理方式，这种思路类似于二叉树的遍历，每种情况都向下衍生出两种情况，最终当遍历到下标 index = nums.size() 时，将生成的子集保存。由于此处我们使用一个数组的引用来保存子集元素，因此在递归回溯时，我们需要手动将上一步中加入添加的元素去除，来回溯到该元素未被选择的状态。代码class Solution {private: std::vec
2022-03-16 10:29:30
1260
原创 C++代码优化 Chapter1
本文将介绍一些常见的 C++ 代码优化技巧，本文为该系列的第一章，未来不定期更新。使用前置递增（递减）运算符可能很多从 C 语言开始学习的朋友会对此感到困惑，觉得这两者在适用的情况下可以任意选择，如 for 循环语句写作 for (int i = 0; i < n; i++) 。这样做当然没错，但会造成一定程度上的资源浪费，因为后置递增运算符需要先将原本的变量值保存下来，再对其进行递增操作，而在此 for 循环中，我们并不需要使用原本的 i 值。并且 ++i 的写法相对来说更符合我们的意愿。当
2022-03-08 13:21:37
709
原创 C++复合类型的声明
声明语句的构成在 C++ 中，一条声明语句由一个基本数据类型（base type）和紧随其后的一个声明符（declarator）列表组成。复合类型的声明定义多个变量对于基本数据类型变量的声明，声明符就是变量名。但对于复合类型来讲，例如指针类型和引用类型，变量名却只是声明符的一部分。例如 int *b; 需要注意的是， “*”运算符修饰的对象是变量名，而不是基本类型名。例如 int *a, b;，此处变量 b 的数据类型为 int，而非 int *。指针的引用指针引用的正确定义形式如下：i
2022-03-03 15:25:37
544
原创 LeetCode周赛总结 第277场
本文同步发布在我的个人博客 LeetCode周赛总结 第277场 欢迎访问本次周赛没想到比上周还要简单，前三题都可以用非常简单的方法快速解决，第四题如果想对了方向其实也比较简单。元素计数题目链接元素计数解题思路相当基础的题目，要同时具有一个严格较小元素和一个严格较大元素，只需要保证这个数 num 满足 num > minVal && num < maxVal即可。解题代码class Solution {public: int countElements
2022-01-23 15:00:54
5682
原创 LeetCode周赛总结 第276场
本文同步发布在我的个人博客：LeetCode周赛总结 第276场 欢迎访问本次周赛相对比较简单，前三题花的时间比较短，但无奈最后一题还是没思路。。。将字符串拆分成若干长度为 k 的组题目链接将字符串拆分成若干长度为 k 的组解题思路遍历字符串 s 的每个字符并加入到一个临时字符串中，当此临时字符串长度为 k 时，加入到结果数组中并清空此字符串。若此时遍历到字符串的最后一个字符且此时临时字符串长度没有达到 k 时，则向其末尾填入字符 fill 直到临时字符串长度达到 k，再加入到结果数组中。解
2022-01-17 19:54:25
278
原创 记一次CTF校赛
本文记录一下刚刚结束的CTF校赛，感觉本次校赛题目出得实在有点坑，但也算学到了不少东西。Cryptoeasy_ECC问题描述已知椭圆曲线加密Ep(a,b)参数为p = 15424654874903a = 305423748b = 315284355172G(15079176652031,83237376468)私钥为k = 655321求公钥K(x,y)思路常规的椭圆曲线加密问题，直接根据加密原理编写解密程序，得到两个结果。根据问题提示，考虑 flag 为两数的异
2021-12-04 10:58:15
4336
原创 C++比较函数cmp
本文将简单介绍C++比较函数 cmp.排序函数sort()sort函数是我们常用的库函数，它的参数如下：void sort (RandomAccessIterator first, RandomAccessIterator last, Compare cmp);通过传入容器的迭代器（或指针），我们可以对指定位置进行排序：vector<int> nums = { 1,3,2,4,5 };sort(nums.begin(), nums.end()); //排序得到nums = { 1,
2021-11-20 14:03:38
6228
原创 位运算基础及其应用
本文同步更新在我的个人博客，欢迎访问：位运算基础及其应用计算机中的数据以二进制的形式存储，即0、1两种状态。位运算就是直接对整数在内存中的二进制位进行操作。本文将介绍位运算的各操作符以及其在实际开发中的常见应用。操作符&（与）参加运算的两个数据，按二进制位进行与运算。（两位都为1时才为1，否则为0）例如 12 和 5 两个数，二进制形式分别为 1100、0101. 逐个按位进行与运算得：0100 = 4. 即 12 & 5 = 4.|（或）参加运算的两个数据，按二进制位进行
2021-09-27 13:35:38
188
原创 链表连接出错
太久没接触数据结构了，导致链表这一块的内容有点生疏了，这两天在做一道链表相关的题时出现了一点问题，在此记录一下以免之后再犯。问题描述题目链接两数相加链表定义struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNod
2021-08-31 11:15:34
197
原创 ZIP格式分析
最近遇到一道CTF题是和zip格式编码相关的，正好我一直以来就对各文件格式编码没有一个系统的认知，就趁这个机会好好学习一下。简介ZIP文件格式是一种数据压缩和文档储存的文件格式，原名Deflate，发明者为菲尔·卡茨（Phil Katz），他于1989年1月公布了该格式的资料。ZIP通常使用后缀名“.zip”，它的MIME格式为application/zip。当前，ZIP格式属于几种主流的压缩格式之一，其竞争者包括RAR格式以及开放源码的7z格式。从性能上比较，RAR及7z格式较ZIP格式压缩率较高
2021-08-29 20:42:33
3525
原创 hexo博客的备份与恢复
为了防止误操作或计算机崩溃导致的博客源文件丢失，或满足我们更换电脑进行写作的需求，定期进行备份与恢复就显得很重要了。备份需备份的文件目录我们在进行备份时，并不需要将整个博客目录全部备份，只备份以下几个用户自定义的即可：scaffolds目录，source目录，themes目录，.gitignore文件，_config.yml文件，package.json文件，其他都是通用的。首先我们先来观察整个博客目录的结构：(1) .deploy_git 本目录会在我们部署时生成，也就是github上保存的文
2021-08-25 11:29:27
500
原创 让批处理中的中文正常显示
最近在学习DOS命令和批处理相关内容的时候，遇到了点问题，就是在执行包含中文的批处理文件时，中文无法正常显示，在查阅了相关资料之后，了解了一些编码相关的内容。原因编码相关的那些事现在主要的两种编码格式为UTF-8和ANSI。ANSI是一种字符代码，为使计算机支持更多语言，通常使用 0x00~0x7f 范围的1 个字节来表示 1 个英文字符。超出此范围的使用0x80~0xffff来编码，即扩展的ASCII编码。为了应对不同国家和地区的使用，ANSI编码存在很多不同的标准：由于汉字的种类非常多
2021-05-29 21:58:34
2004
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人