- 博客(36)
- 收藏
- 关注
RSS订阅原创 算法与数据结构 - 滑动窗口
滑动窗口滑动窗口的作用是可以将一部分问题中的嵌套循环转变为一个单循环，因此可以减少时间复杂度。滑动窗口的基本思想使用 left 和 right 指针来指定窗口大小，默认值都为 0。先让 right 向右移动直到窗口大小符合要求。然后将 left 向右移动不断缩小窗口，直到窗口不再满足要求。重复第 2-3 步，直到 right 指针到达数组的尽头。难点在于判断窗口的要求。例题分析以 leetcode 第2024题为例：一位老师正在出一场由 n 道判断题构成的考试，每道题的答案.
2022-03-29 15:06:16
1190
原创 算法与数据结构-分治法
分治法分治法的思想将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。分治模式在每层递归时都有三个步骤：分解：将原问题分解为若干子问题，这些子问题是原问题的规模较小的实例。解决：递归地求解这些子问题。当子问题规模足够小时，可直接求解。合并：合并子问题的解成原问题的解。一个经典的分治法的例子就是归并排序。分析分治算法当一个算法包含对自身的递归调用时，我们往往可以用递归式来描述其运行时间。按照分治模式的三个步骤依次分析。假设 T
2022-03-27 18:27:21
2056
原创 九、【栈和队列】栈和递归
栈和递归栈的另外一个重要应用就是在程序设计语言中实现递归。1 递归 Recursion简单来说，递归就是直接调用自身或通过一系列调用语句间接调用自身的一种编程技巧或方法，使用递归来实现的函数被称为递归函数。递归通常将一个大型的复杂问题层层转化为一个与原问题类似的小规模问题来求解，有助于解决复杂的重复度高的问题，并使代码变得简洁。先通过一个简单的例子来了解递归，以斐波那契数列为例：Fib(n)={Fib(n−1)+Fib(n−2), n>11, n=10,
2021-06-07 13:59:58
1461
原创 十、【栈和队列】队列
队列 Queue队列和栈一样，也属于受限线性表。1 队列的基本概念1.1 队列的定义队列是只允许在表尾进行插入，表头进行删除的线性表。插入操作又称为入队，删除操作又称为出队。队列的逻辑关系就和现实和生活中的队列一样，最早排队就最早离队，这种特性被称为“先入先出”（First In First Out, FIFO）。1.2 队列的基本操作队列的基本操作和栈类似，不同的是删除操作在队首执行。主要操作操作结果InitQueue(&Q)初始化一个空队列 Q。
2021-06-05 00:07:19
326
原创 七、【栈和队列】栈
栈 Stack在第一节中我们提到，数据结构的逻辑结构分为线性结构和非线性结构，其中线性结构又可分为一般线性结构、受限线性结构和推广结构。栈和队列从数据结构上看和线性表很类似，但是他们在普通线性表的基础上有额外的要求限制，因此说他们是受限的线性结构。这一节我们主要来了解什么是栈。1 栈的基本概念1.1 栈的定义栈是只允许在表尾进行插入或删除操作的线性表。从定义上来看，栈依然属于线性表，只是它的操作仅限在表的一端执行。允许变化的一端通常称为栈顶，一般用表尾构成；而始终固定的一端被称为栈底，由表头构
2021-06-04 10:56:07
385
原创 六、【线性表】双向链表、循环链表和静态链表
双向链表、循环链表和静态链表上节我们实现了单链表的基本操作，在实现过程中可以发现，单链表的逻辑关系仅由一个单向指针表示，指向其后继结点，使得单链表只能从头向后地顺序遍历。这个缺点让单链表使用起来不太方便，因此我们引入几个功能更强大的链式存储结构：双向链表、循环链表和静态链表。1 双向链表 Double Linked List1.1 双向链表的定义顾名思义，双向链表的结点中包含两个指针，分别指向其前驱结点和后继结点。单链表可以非常容易地找到下一个结点，但是回到上一个结点就比较麻烦，而且单链表很多操
2021-06-03 20:50:29
323
原创 五、【线性表】线性表的链式表示和实现
线性表的链式表示和实现上节提到，由于顺序表的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素。然而，这也导致了顺序表在执行插入或删除操作时，需要移动大量元素。本节来讨论线性表的另一种存储方式——链式存储结构。1 线性表的链式表示1.1 单链表的定义线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这些存储单元可以连续也可以不连续。因此，为了表示每个数据元素与其后驱的逻辑关系，除了存储其信息本身外，还需要存储一个指示其后驱的信息（即其后驱的存储地址
2021-05-27 20:56:42
638
原创 四、【线性表】线性表的顺序表示和实现
线性表的顺序表示前文我们提到过线性表是逻辑结构，只说明了数据元素之间的相互关系，想要使用线性表，我们还需要在计算机上表示出这些数据元素以及元素之间的关系。而对于同一种逻辑结构，可以有多种存储结构来实现它。线性表作为一种基础的数据结构，可以用顺序存储和链式存储两种不同方式来实现，本节主要说明线性表的顺序表示。1 线性表的顺序表示和实现1.1 顺序表的定义线性表的顺序存储又称为顺序表， 它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理地址上也相邻。顺序表的特
2021-05-26 12:23:11
849
原创 三、【线性表】线性表概述
线性表概述 Linear List在了解线性表之前，我们首先了解一下什么是线性结构。线性结构的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称为“第一个”的数据元素；（2）存在唯一的一个被称为“最后一个”的数据元素；（3）除第一个外，集合中的每个数据元素均只有一个前驱；（4）除最后一个外，集合中的每个数据元素均只有一个后驱。1 线性表的定义线性表是一种最常用且最简单的数据结构。简单来说，一个线性表是nnn (n≥0)(n \ge 0)(n≥0) 个数据元素的有限序列，其中nnn为表长，
2021-05-26 09:07:10
651
原创 二、【绪论】算法和算法评价
算法和算法评价1 算法的基本概念算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。一般具有下列5个重要特性：有穷性：一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。输出：一个算法有一个或多个输出，这些输出
2021-05-25 17:16:41
711
原创 Python数据结构——tuple
tuple 元组什么是tuple元组是一种和列表非常相似的线性数据结构，也支持不同的数据类型。最大的区别就是元组一旦创建不可改变，和string一样，所有改变元组内容的操作都会返回一个新的元组。对于可变、不可变的理解:元组和列表一样，都是存储引用而不是对象本身，因此所谓的不可修改是指元组自己的每一个元素保存的引用不能被修改。如果元组某个元素的引用是另一个引用，我们也可以做到“修改元组...
2020-05-02 14:48:09
456
原创 Python数据结构——list
list 列表什么是list列表是Python中特有的一种线性数据结构，列表是可变的，有序的，我们可以用选择操作符来改变任意位置的值，和数组不同的是，列表可以同时保存不同类型的元素（异构）。在CPython中，list是一个存储指针的长度可变的数组（用C++的话来说是一个动态数组）。也就是说列表中的每个元素存储的并不是对象本身，而是一个指向对象的引用。list有哪些功能list的创...
2020-05-02 00:19:42
728
原创 Python数据结构——array
array 数组array是什么一般来说，array基本是所有程序语言都有的一种基础线性结构，元素以特定的顺序存储在一段连续的内存中。在Python中其实也有array这种数据结构，和其他语言的array一样，也是内存连续，只能存储相同类型元素的线性数据结构，而且Python的array只能存储数值和字符。array有哪些功能这里只讲一下内置array。需要先import array...
2020-05-01 18:56:53
30117
原创 算法与数据结构（归并排序）
归并排序 Merge Sort利用分治策略来解决排序问题分治法 Divide and Conquer：分：将大问题分成一些小的问题然后分别求解；治：将求出来的答案组合到一起，形成最初问题的答案归并排序的思路：归并排序的基本思路是先将序列分为两部分，让左右两部分分别有序，然后合并。但是左右两部分的排序又重复上述过程，不断地分裂成两部分，直到最终都只有一个元素，此时所有的数组都是有序...
2020-04-29 21:16:48
325
原创 算法与数据结构（快速排序）
快速排序 Quick Sort快速排序是对冒泡排序的一种改进通过一趟排序将序列分为两个部分，其中一个部分的所有数据比另一个部分的所有数据都小，然后再分别对两个部分进行类似操作（递归），直到整个序列有序基本思路：随机找出一个数，或是取第一个或最后一个数为基准。然后将所有的数和基准比较，比基准小，就放左边，比基准大就放右边，这样就把一个序列分成了两个子序列。然后按照同样的方法对子序列排序...
2020-04-29 21:11:55
217
原创 算法与数据结构（希尔排序）
希尔排序 Shell’s Sort我们都知道直接插入排序对有序度高的列表排序效率是比较高的。而当列表为倒序时，最后一位元素的值是最小的，直接插入排序会进行 n-1 次比较才能找到正确的位置。这种情况下直接插入排序的效率是很低的希尔排序是改进的直接插入排序，也称为缩小增量排序希尔排序的基本思路：把列表元素按下表的一定增量分组，对每组分别使用直接插入排序这种做法成功的把大规模的有序度较...
2020-04-29 21:05:30
144
原创 算法与数据结构（冒泡排序，选择排序和插入排序的总结）
冒泡排序，选择排序和插入排序的总结在规模较小时，或者元素的有序性较高时，插入排序的时间复杂度可以接近 O(n) ，是上述三种排序里表现最好的一、通过表格我们可以发现，冒泡排序的时间复杂度是要优于选择排序的，但实际上选择排序的平均效率要优于冒泡排序冒泡排序的思想是不断比较相邻元素大小，如果逆序，就需要不断的交换位置，也就是说在冒泡排序的一次子循环中，可能需要进行多次交换操作选择排序的思想...
2020-04-29 21:02:03
302
原创 算法与数据结构（插入排序）
插入排序 Insertion Sort类似选择排序，构建有序列表，默认原无序列表第一位在有序列中，将无序列表（已除去原第一位）的第一位元素插入到有序列表的相应位置，不断重复直到无序列表为空和选择排序的区别：选择排序是首先在无序表中找到最小值，放到有序表的最后一位插入排序是将无序列表的第一位取出，排序后放入有序列表中实现：首先将原列表的第一位当作有序列的第一位，然后从原列表的第二...
2020-04-29 20:56:00
163
原创 算法与数据结构（选择排序）
选择排序 Select Sort从待排序序列中选出最小（或最大）元素，放入新建的有序序列中，并将其从原无序序列移除。不断重复直到无序序列最终没有元素剩余选择排序规则：总共要进行 n-1 次循环每一轮循环中又嵌套了一层循环–从第一个元素遍历到最后一个，找出最小元素实现：从无序序列中找到最小元素，将其和无序序列首位的元素交换（此时首位元素属于有序序列，剩下的元素属于无序序列）...
2020-04-29 20:53:23
132
原创 算法与数据结构（冒泡排序）
冒泡排序 Bubble Sort对序列从前向后，不断比较两个相邻元素的大小，如果逆序，则交换位置，使值较大的元素逐渐从前向后移动，就像水底的气泡向上浮一样冒泡排序规则：一共会进行 n-1 次循环每一趟循环排序的次数在减少有序序列是从队尾向队首延伸如果发现在某次循环中没有发生任何一次交换，可以提前结束排序实现：第一次循环：从第一位开始，遍历到最后一位第二次循环：从第一位开...
2020-04-29 20:50:08
241
原创 算法与数据结构（排序算法概述）
排序算法 Sort Algorithm排序算法是将一系列数据根据指定的顺序进行排列的过程排序算法的分类：内部排序：指将需要处理的所有数据都加载到内存中进行排序插入排序直接插入排序希尔排序选择排序简单选择排序堆排序交换排序冒泡排序快速排序归并排序基数排序外部排序： 数据量过大，需要借助外部存储器来排序对排序算法来说，一般有两种基本操作：...
2020-04-29 20:49:31
143
原创 算法与数据结构（Java解八皇后问题）
递归 Recursion简单的说，递归就是方法自己调用自己，每次调用时传入不同的变量递归有助于解决复杂的重复度高的问题，并使代码变得简洁递归调用规则:每当程序执行一个方法时，就会开辟一个独立的空间（栈）每个空间的数据（局部变量）是独立的如果在递归中使用引用变量，那么引用变量的数据会被共享递归遇到 return 或 将方法执行完毕就会返回，遵循谁调用谁返回原则递归必须向退出递归...
2020-04-29 20:42:25
159
原创 算法与数据结构（约瑟夫问题）
单向环形链表 Circular Linked List单向环形链表和单链表类似，只是最后一位节点不再指向 null，而是指向 head（如果有头节点的话）或是第一位节点（如果没有头节点）图示：构造方式和单向链表类似，只是最后一位节点指向第一位节点...
2020-04-29 20:22:26
173
原创 Java实现单链表
单链表 Single Linked List链表是有序的列表，每个节点包括一个数据元素（data）和指向下一个节点的地址（next）链表的各个节点不一定是连续存储在内存中图示：head节点不存放具体数据，作用是表示单链表表头对于链表来说，最关键的是要定义节点： class Node{ public int no; public String cont...
2020-04-29 20:09:41
251
原创 算法与数据结构（稀疏数组）
稀疏数组 Sparse Array当一个数组中有大量元素相同时，可以用稀疏数组来表示，通过将有用信息记录在小规模的数组中来缩减程序规模原数组：[0000102000300000004000000023000]\left[\begin{matrix}0 & 0 & 0 & 0 & 1 \\0 & 2 & 0 & 0 &...
2020-04-29 19:02:53
171
原创 一、【绪论】数据结构的基本概念
简述 Abstract数据结构可分为线性数据结构和非线性数据结构线性结构：最常用的数据结构，其特点是数据元素之间存在一对一的线性关系2. 线性结构又两种不同的数据存储结构：顺序存储和链式存储。顺序存储中的元素一定是连续的；链式存储的元素不一定连续，元素节点中存放数据元素和相邻元素的地址信息常见的线性结构有：数组、队列、链表和栈非线性结构：非线性结构包括：二维数组、多维数......
2020-04-29 18:58:30
474
1
原创 进制的转换
进制转换任意进制的数字转十进制：若基数为B，对于数字 anan-1…\dots…a2a1a0a-1a-2，转换公式为：N = an×\times×Bn + an-1×\times×Bn-1 + …\dots… + a2×\times×B2 + a1×\times×B1 + a0×\times×B0 + a-2×\times×B-1 + a-2×\times×B-...
2020-03-06 17:01:49
1655
原创 解决Mac上VSCdoe断点失效问题
问题描述：VSCode正确配置 tasks.json 和 launch.json 后，调试模式下无法识别断点，并提示：Warning: Debuggee TargetArchitecture not detected, assuming x86_64.在github和知乎上找到问题来源，Mac在更新到Catalina后不再支持lldb调试。解决方法：在VSCode上安装 CodeL...
2020-02-21 13:17:06
7298
3
原创 关于C++指针的理解
什么是指针在C++中，为了让程序可以从底层操作内存，所以地址被处理为可操作的数据类性–指针。指针的声明方式为<type>∗varname;<type> * varname;<type>∗varname;一般将星号 * 视为变量名的一部分，原因如下：* 是一元运算符，表示值指向运算当我们写 int *p1, p2;时， 表示创建了一个指针变量p1，...
2020-02-19 11:15:38
539
原创 Subset-Sum Problem 子集和问题
递归求解子集和问题的思路子集和问题:给定一个集合S和一个目标值t，求问是否能从S中找出一个子集，使得这个子集元素之和等于目标值t假设有一个集合S = {-1, 2, 7, 10}，一个目标值t = 8。那么我们可以找到S的一个子集S1 = {-1, 2, 7} 各项之和等于8。解决子集和问题的基本思路是 The inclusion/exclusion pattern，即判断某个元素el...
2020-02-16 15:38:30
1000
原创 斐波那契数列递归解法
递归解斐波那契数列斐波那契数列最直观的递归解法：int fib(int n){ if (n<2) { return n; } else { return fib(n-1) + fib(n-2); } }然而这种解法效率很低，会进行很多重复运算例如：当计算 fib(5) 时，我们共需要计算1次 fib(4)，2次 fib(3)，3次 fib(2)，5次 fib(1...
2020-02-12 16:50:25
22286
原创 wchar.h not found
报错信息：wchar.h not found/usr/local/Cellar/gcc@8/8.3.0/include/c++/8.3.0/cwchar:44:10: fatal error: wchar.h: No such file or directory#include <wchar.h>^~~~~~~~~compilation terminated.Mac系统更...
2020-02-07 22:46:23
3750
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人