吴灿锦，吉林财经大学2019级本科生，曾作为长春鹰迅网络科技有限责任公司CEO，带领鹰迅公司团队在“互联网 +"和"挑战杯"等竞赛中斩获3个国家级，11个省部级奖项。目前在上市公司从事Java开发工作已经超过两年了，参与了两个千万级用户的分布式系统的开发和维护工作，在做项目期间，对Mysql优化，分库分表，多线程，分布式锁，分布式事务，Redis缓存，RabbitMQ，xxl-job，ElasticSearch，SpringCloud微服务框架以及前端的Vue框架都有比较深入的研究，积累了丰富的实际经验和良好的职业履历。算法其实是解决某个实际问题的过程和方法。比如腾讯地图给你规划路径，计算最优路径的过程就需要用到算法。再比如你在抖音上刷视频时，它会根据你的喜好给你推荐你喜欢看的视频，这里也需要用到算法。
Java语言本身就内置了一些基础算法给我们使用，不用我们自己写这些算法。但学习算法依然是成为一个高级程序员的必经之路。
学习算法的方式：先要搞清楚算法的流程，再去推敲代码怎么写。
冒泡排序基本思路：每次把相邻的两个元素继续比较，第一轮排序：索引为0的元素与索引为1的元素做比较，索引为0的元素就与索引为1的元素通过一个临时变量进行交换位置，然后第索引为1的元素与索引为2的元素进行比较，依此类推。每一轮遍历后，最大（或最小）的元素就会像“冒泡”一样逐渐移到序列的一端。升序就是每次排序把最大的元素放到参与排序元素的最后边。最好情况：当输入的数据已经是正序时，时间复杂度为O(n)。因为只需要遍历一次，不需要进行任何交换。
最坏情况：当输入的数据是反序时，时间复杂度为O(n²)。因为需要进行n(n-1)/2次比较和交换。
平均情况：时间复杂度也为O(n²)。这是因为无论数据的初始顺序如何，冒泡排序都需要进行大量的比较和交换操作。
2.空间复杂度：
冒泡排序的空间复杂度为O(1)。这是因为冒泡排序是原地排序算法，它只需要一个额外的存储空间用于交换元素，不需要额外的数据结构来存储数据。这个额外的存储空间通常是一个临时变量。
![]()
选择排序基本思路：每次都拿参与排序元素第1个元素与后面的元素进行比较，当遇到比第1个元素小的元素时，就用临时变量存储它并交互元素的位置，然后用它跟后续的元素进行比较，遇到更小的，临时变量的值就改为更小的值。最后将参与排序元素的第1个元素与临时变量的元素进行交互，然后开始第2轮的比较，直到排序完成。![]()
选择排序的时间复杂度是O(n²) ：即使输入数据已经是有序的，选择排序仍然需要遍历每个元素来寻找最小（或最大）值。
选择排序的空间复杂度是O(1) ：这是一种原地排序算法，因为它只需要一个额外的变量来存储当前找到的最小（或最大）元素的索引，不需要额外的数据结构来存储数据。在交换元素时，也只需要一个临时变量
插入排序是把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，只需重复n-1次可完成排序过程。1. 初始状态：有序区[5]，无序区[3, 4, 2, 8]。2. 取出3，与5比较，3小于5，交换位置，有序区变为[3, 5]，无序区变为[4, 2, 8]。3. 当前状态：有序区[3, 5]，无序区[4, 2, 8]。4. 取出4，与5比较，4小于5，但与3比较时，4大于3，所以4插入到3和5之间，有序区变为[3, 4, 5]，无序区变为[2, 8]。![]()
希尔排序又称递减增量排序算法，是插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。下面数组的长度length为8，初始增量第一趟 gap = length/2 = 4，即让第1个数和第5个数比较，第2个数和第6个数进行比较，第3个数和第7个数进行比较，第4个数和第8个数进行比较，最终结果是【1 5 2 3 7 6 9 4】。![]()
第二趟，gap=gap/2=2,增量缩小为 2。即让第1个数、第3个数、第5个数和第7个数进行比较，第2个数、第4个数、第6个数和第8个数进行比较，最终结果是【1 3 2 4 7 5 9 6】。
![]()
第三趟， 当gap = gap / 2 = 1时，增量缩小为1。此时，我们对整个数组进行一次传统的插入排序。具体来说，我们从数组的第二个元素开始（索引为1），将其与它前面的元素（索引为0）进行比较。如果前面的元素比它大，则交换这两个元素的位置。然后，我们继续将下一个元素（索引为2）与它前面的已排序部分进行比较，并在必要时进行交换。这个过程一直持续到数组的末尾。最终，我们得到完全排序的数组[1, 2, 3, 4, 5, 6, 7, 9]。![]()
![]()
归并排序是一种采用分治策略的排序算法，同时它也是稳定性排序算法。它将原始数组分成较小的数组，直到每个小数组只有一个元素，接着将小数组归并成较大的有序数组，直到最后只剩下一个排序完成的数组。1. 分解：将数组分成两半，左边是【2、9、5、4】，右边是【8、1、6、7】。2. 继续分解：左边继续分成【2、9】和【5、4】；右边分成【8】和【1、6、7】（但这里【1、6、7】还需继续分解为【1】和【6、7】，【6、7】再分解为【6】和【7】）。4. 开始合并：从底层开始，将相邻的有序子数组合并成一个有序数组。合并【2、9】和【4、5】得到【2、4、5、9】。5. 类似地，合并右边的子数组得到【1、8、6、7】（过程中包含【1】、【8】、【6】、【7】的合并）。6. 最终合并：合并【2、4、5、9】和【1、8、6、7】得到【1、2、4、5、6、7、8、9】。![]()
![]()
![]()
计数排序不是一个基于比较的排序算法。它是用一个数组来统计每种数字出现的次数，然后按照大小顺序将其依次放回原数组。但是计数排序有一个很严重的问题，就是其只能对整数进行排序，一旦遇到字符串时，就无能为力了。假设我们有原始数组 arr = [0, 2, 5, 3, 7, 9, 10, 3, 7, 6]。第一步：遍历数组 arr，找到其中的最大值 max。在这个例子中，max = 10。![]()
第二步：根据最大值 max，创建一个长度为 max + 1 的计数数组 count，并初始化所有元素为 0。因此，count 的长度为 11，索引从 0 到 10，每个元素初始化为 0。![]()
第三步：遍历原始数组中的元素，以原始数组中的元素作为计数数组count的索引，以原始数组中的元素出现次数作为计数数组count的元素值。下图可以得到原始数组【0,2,5,3,7,9,10,3,7,6】中元素0出现1次，元素2出现1次，元素3出现2次，元素5出现1次，元素6出现1次，元素7出现2次，元素9出现1次，元素10出现1次。![]()
第四步：遍历计数数组count，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到结果数组result中去，每处理一次，计数数组count中的该元素值减1，直到该元素值不大于0，依次处理计数数组count中剩下的元素。![]()
![]()
1. 快速排序是一种采用分治策略的排序算法。它通过选择一个基准元素，将数组分为两部分，左边部分小于基准，右边部分大于基准，然后递归地对这两部分进行排序。2. 快速排序的关键在于基准的选择，它直接影响算法的效率。优化措施包括随机选择基准、三数取中法以及在小数组时切换到其他排序算法。快速排序的平均时间复杂度为O(n log n)，但在最坏情况下可能退化到O(n^2)。它通过递归分解问题，实现了高效的排序。3. 快速排序和归并排序的主要区别在于：快速排序直接在原数组上进行，不占额外空间（除递归栈外），通过分区实现排序，不稳定；而归并排序需要额外空间，将数组不断二分至单元素，再合并排序，稳定且空间复杂度为O(n)。两者都运用了分治思想，但实现方式和性能特点不同。堆排序是一种利用堆数据结构的排序算法，通过将待排序元素构建成堆（大根堆或小根堆），然后依次将堆顶元素与堆底元素交换，并重新调整堆，直至整个序列有序。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，适用于大规模数据的排序。其优点是效率高，缺点是不稳定。堆排序通过构建二叉堆（通常是最大堆或最小堆）来实现排序。它首先将待排序的数组元素构建成一个堆，确保父节点的值总是大于（或小于）其子节点的值。然后，堆顶元素（最大或最小值）与堆的最后一个元素交换，并减少堆的大小，接着重新调整剩余元素以维持堆的性质。这个过程重复进行，每次都将堆顶的最大（或最小）元素移到序列的末尾，直到堆的大小为1，此时数组就完全有序了。堆排序的时间复杂度为O(n log n)，且不稳定。桶排序（Bucket Sort）是一种排序算法，其工作原理是将数组分到有限数量的桶子里，每个桶子再个别排序（可能使用其他排序算法或递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果，当被排序的数组内的数值是均匀分配时，桶排序可以使用线性时间（O(n)）进行排序。然而，桶排序并不是比较排序，它不受O(n log n)下限的影响。基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。1. 时间复杂度指执行这个算法需要消耗多少时间，也可以认为是对排序数据的总的操作次数。常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)。O(1)< O(logn)<O(n)<O(nlog2n)<O(n2)<O(n3)<…<O(2n)<O(n!)。![]()
空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数。常见的空间复杂度有：常量空间复杂度O(1)、对数空间复杂度O(log2N)、线性空间复杂度O(n)。对于一个算法来说，空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。有时我们可以用空间来换取时间以达到目的。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法是否为稳定的是由算法具体实现决定的。总体上，堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而冒泡排序、直接插入排序、归并排序、基数排序、计数排序、桶排序是稳定的排序算法。比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。如冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序。非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。如计数排序、基数排序、桶排序。![]()
1. k 表示输入数字的范围。例如，如果输入的数字都是非负整数，并且不超过某个最大值 M，那么 k = M+1。
2. 希尔排序的时间复杂度依赖于增量序列的选择，这里给出的 O(n^s) (s>1) 是一个比较宽泛的估计，实际上好的增量序列可以使得希尔排序的性能接近 O(nlogn)。
3. 快速排序的平均时间复杂度是 O(nlogn)，但在最坏情况下（如输入数组已经有序或几乎有序）会退化到 O(n^2)。其性能高度依赖于选择的基准值（pivot）。
4. 堆排序和归并排序在时间和空间复杂度上各有优势，堆排序使用 O(1) 额外空间但不稳定，而归并排序稳定但需要 O(n) 额外空间。
5. 计数排序、桶排序和基数排序是线性时间复杂度的排序算法，但它们要求输入数据满足一定的条件（如计数排序只能对整数进行排序，而且要求输入数据范围不大，桶排序要求输入数据分布均匀）。这些算法特别适合于特定场景下的高效排序。
二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的工作原理是，通过比较数组中间元素和目标值，来决定是在数组的左半部分还是右半部分继续搜索，从而每次迭代都排除一半的搜索空间。假设我们要查找的元素是81，如果是基本查找的话，只能从0索引开始一个一个往后找，但是如果元素比较多，你要查找的元素比较靠后的话，这样查找的此处就比较多，性能比较差。二分查找的主要特点是，每次查找能排除一半元素，这样效率明显提高。但是二分查找要求比较苛刻，它只适用于静态数据集合，对于需要频繁插入、删除元素的数据集合，二分查找可能不是最优的选择。第1步：定义两个变量，分别记录开始索引（left）和结束索引（right）。第2步：计算中间位置的索引，mid = (left+right)/2 ;第3步：使用while循环，每次查找中间mid位置的元素和目标元素key进行比较，如果中间位置的元素比目标元素小，那说明mid前面的元素都比目标元素小，此时改变left变量的索引值，left = mid+1。如果中间位置的元素比目标元素大，那说明mid后面的元素都比目标元素大，此时将left的值改为mid-1。然后再依次执行上面操作，当找到元素时就把目标元素返回，没有找到元素，当left左边的索引大于右边索引end时就结束while循环，返回-1作为没有找到目标元素的标识。
![]()
最好情况：O(1)，即目标元素就在数组中间位置，一次比较即可找到。但这种情况并不常见，因为需要恰好猜中目标元素的位置。最坏情况：O(log n)，即每次比较后，目标元素都在剩下未搜索部分的一端，导致每次只能排除一半的元素。这里的 log 是以 2 为底的对数，因为每次迭代都会将搜索空间减半。平均情况：O(log n)，在大多数情况下，二分查找的平均时间复杂度接近于最坏情况，因为平均而言，每次迭代都会排除大约一半的元素。O(1)，二分查找是一种原地算法，它只需要常数级别的额外空间来存储几个变量（如中间元素索引、左右边界等），不随输入数组的大小 n 而变化。因此，空间复杂度是常数级别的。链表是一种动态的数据结构，因为在创建链表时，我们不需要知道链表的长度，当插入一个结点时，只需要为该结点分配内存，然后调整指针的指向来确保新结点被连接到链表中。所以，它不像数组，内存是一次性分配完毕的，而是每添加一个结点分配一次内存。正是因为这点，所以它没有闲置的内存，比起数组，空间效率更高。链表是一种常见的数据结构，它通过节点（Node）的集合来表示序列。节点之间通过指针（或引用）相互连接。链表的分类可以简洁地归纳为以下几种：
1. 单向链表：每个节点包含一个数据域和一个指向下一个节点的指针（next）。链表的最后一个节点指向null（或称为nullptr、None等，取决于编程语言），表示链表的结束。2. 双向链表：每个节点包含三个域：数据域、一个指向前一个节点的指针（prev）和一个指向下一个节点的指针（next）。这使得双向链表可以向前或向后遍历。(1) 不带头链表：直接以第一个数据节点作为头节点，操作起来可能需要特殊处理头节点的情况（如插入、删除头部节点）。(2) 带头链表：在数据节点之前额外设置一个头节点（也称为哑节点或哨兵节点），其数据域通常不使用，但有两个好处：一是可以简化插入和删除头部节点的操作；二是可以作为链表的起点，使得链表的遍历等操作更加统一。(1) 非循环链表：如上所述，单向或双向链表的最后一个节点指向null，表示链表的结束。(2) 循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向链表的第一个节点（或头节点，如果是带头链表），形成一个环。这使得链表可以从任何节点开始遍历整个链表。![]()
![]()
![]()
![]()
![]()
![]()
![]()
(1）使用递归或迭代的方式，比较两个链表当前节点的值。(2）将较小的节点作为当前合并链表的节点，然后递归/迭代地处理剩余的部分。(3）如果一个链表已经为空，则将另一个链表直接连接到合并链表的末尾。![]()
栈是一种后进先出（LIFO）的线性数据结构，它仅允许在栈顶进行元素的添加（push）和删除（pop）操作。栈底是固定的，而栈顶是动态变化的，用于执行元素的添加和删除。这种特性使得栈在解决特定算法问题时非常有用，如括号匹配、表达式求值、回溯算法等。
![]()
![]()
![]()
队列是一种先进先出的数据结构，这和栈有所不同，但又更容易理解。类似于食堂排队打饭，车站排队买票。后来的人排在队伍最后边，先来的人先打饭或者买票走。![]()
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，进行插入操作的一端称为队尾出队列，进行删除操作的一端称为队头。Queue（队列）是一种先进先出（FIFO, First-In-First-Out）的线性表。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。在Java中，Queue 接口定义了多种队列操作，包括添加、删除、检查元素以及检查队列是否为空等。Java中常用的Queue实现类有LinkedList、PriorityQueue等。Queue（队列）的主要用途是在不同的线程之间安全地传递信息，或作为不同进程间通信的一种方式。1. boolean add(E e): 向队列末尾添加一个元素，如果队列容量达到上限（对于某些有容量限制的队列），则可能抛出异常。2. boolean offer(E e): 向队列末尾添加一个元素，如果队列容量达到上限，则返回false，不会抛出异常。3. E remove(): 移除并返回队列头部的元素，如果队列为空，则抛出NoSuchElementException。4. E poll(): 移除并返回队列头部的元素，如果队列为空，则返回null。6. isEmpty()：队列不包含任何元素返回true。在Java的单节点应用程序中，多线程之间使用Queue进行通信是一种常见的做法。Queue接口本身不直接支持多线程间的同步操作，但Java提供了线程安全的Queue实现，如ConcurrentLinkedQueue（非阻塞）和BlockingQueue接口的实现类（如ArrayBlockingQueue、LinkedBlockingQueue等），这些实现内部已经处理了同步问题，因此可以安全地在多线程环境中使用。以下是一个使用LinkedBlockingQueue在多个线程之间进行通信的示例。在这个例子中，我们将创建一个生产者线程来向队列中添加元素，以及一个消费者线程来从队列中移除并处理元素。![]()
![]()
![]()
![]()
![]()
在计算机科学中，BST通常指的是二叉搜索树（Binary Search Tree）。这是一种特殊的二叉树结构，其中每个节点的左子树中的所有节点都小于该节点的值，而右子树中的所有节点都大于该节点的值。这使得在BST中可以高效地进行搜索、插入和删除操作。普通二叉树：没有排序，查找起来就会特别复杂。如果是已经排好序的元素，存放到二叉树中就跟链表一样，性能并没有提升。
![]()
红黑树，又叫平衡二叉树，会根据树中的元素自动旋转整个树来确保左右的平衡性。如果右边添加的元素太多了，下图的根节点就会从13移动到17或者25的位置，就是要确定保证树的左右平衡。
红黑树能实现元素的快速查找：
比如要查找22这个元素的值，比较4次就可以找到了。第1次和13判断，大于13，走右边，大于17，再走右边，小于25，就走左边。比较4次就能找到22这个元素了。
3.2.1、二叉树的遍历方式
![]()
1. 二叉树的遍历方式有四种，分别是前序遍历（VLR）、中序遍历（LDR）和后序遍历（LRD）和宽度遍历。
2. 前序遍历的顺序是“根左右”，即首先访问根节点，然后遍历左子树，最后遍历右子树，上图最终遍历结果是：GEDACHS。
3. 中序遍历的顺序是“左根右”，即首先遍历左子树，然后访问根节点，最后遍历右子树，也是红黑树默认的遍历方式，上图最终遍历结果是：DEAGHCS。
4. 后序遍历的顺序是“左右根”，即首先遍历左子树，然后遍历右子树，最后访问根节点，上图遍历结果是：DAEHSCG。
5. 宽度遍历：从根节点开始依次遍历左子节点和右子节点，直到所有子节点都变遍历完才遍历下一层的节点，上图遍历结果是GECDAHS。
通过定义一个节点类，每个节点包含数据、左子节点引用和右子节点引用。![]()
![]()
![]()
![]()
图（Graph）：图是一种数据结构，用于表示对象之间的连接关系。它由顶点和边组成，其中顶点代表对象，边代表对象之间的连接。图算法主要用于解决涉及复杂关系网络的问题，如分析社交网络中的用户关系、信息评估路径、影响力、路线规划、推荐系统等。它们能够优化算法性能，如通过最短路径算法找到最佳路径，或利用最小生成树算法优化资源分配。此外，Java图算法还支持数据结构和算法研究，为高级算法和模型（如图神经网络）提供基础，并提升软件开发效率，特别是在处理大规模图数据和图数据库方面。1. 顶点（Vertex）：图中的基本元素，也称为节点。2. 边（Edge）：连接两个顶点的线段，表示顶点之间的连接关系。3. 度（Degree）：对于无向图，一个顶点的度是与该顶点相连的边的数量。4. 出度（Out-degree）：对于有向图，一个顶点的出度是从该顶点出发指向其他顶点的边的数量。5. 入度（In-degree）：对于有向图，一个顶点的入度是指向该顶点的边的数量。6. 有向图（Directed Graph）：图中的边具有方向性，即每条边都从一个顶点指向另一个顶点。![]()
7. 无向图（Undirected Graph）：图中的边没有方向性，即边连接的两个顶点可以相互到达。8. 带权图（Weighted Graph）：图中的每条边都有一个与之关联的权重，这个权重可以表示距离、成本、时间等可度量的值。![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历搜索树或图的算法。它沿着树或图的深度方向进行探索，直到达到一个叶子节点或搜索的终点。在每个节点上，算法首先尝试沿着一个分支深入，直到该分支的末端，然后回溯并尝试其他分支。这个过程会一直持续，直到所有可能的路径都被探索完毕。![]()
2. 创建一个哈希集用来记录已访问过的顶点，避免重复访问。3. 将起始顶点加入栈，并将其标记为已访问，并输出该顶点的值。步骤2：遍历该顶点的所有邻接顶点，如果邻接顶点未被访问过，则将其加入栈，并标记为已访问，并输出该邻接顶点的值。步骤3：如果找到了未访问过的邻接顶点，则将当前顶点再次压入栈，以便稍后继续探索其剩余的邻接顶点。![]()
2. 创建GraphTraversal封装遍历方法：![]()
![]()
![]()
描述：宽度优先搜索又叫广度优先搜索。该算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深的访问顶点。用途：用于寻找最短路径、检测图中是否存在从源节点到目标节点的路径等。![]()
2. 创建一个哈希集合用来记录已访问过的顶点，避免重复访问。（2）遍历该顶点的所有邻接顶点，如果邻接顶点未被访问过，则将其加入队列，并标记为已访问。![]()
2. 创建GraphTraversal封装遍历方法：![]()
![]()
拓扑排序是在有向无环图(Directed Acyclic Graph,DAG)中对顶点的一种线性排序方式。在这种排序中，对于任意一对顶点u和v，如果图中存在一条从u到v的有向路径，那么在拓扑排序的结果中，顶点” 必须出现在顶点υ之前。1. 任务调度：在项目管理中，任务之间可能存在依赖关系，比如 A 任务需要在 B 任务完成之后才能开始。这种情况下，可以通过拓扑排序来安排任务的执行顺序。2. 软件构建：在构建大型软件系统时，各个模块可能需要按照一定的顺序编译或链接。通过拓扑排序可以确定正确的构建顺序。3. 课程选修：在大学课程体系中，某些课程需要在学习了其他一些基础课程之后才能选修。拓扑排序可以帮助学生合理安排学习计划。4. 数据处理流水线：在数据处理流程中，某些操作依赖于前一个操作的结果。拓扑排序可以用来决定处理步骤的执行顺序。5. 依赖解析：在包管理器中，不同软件包之间可能存在依赖关系。拓扑排序可以用来解析这些依赖并确定安装顺序。假设我们有一个游戏，其中关卡的解锁顺序遵循一定的规则，比如打游戏时一定要先打第一关，因为只有打通了第一关，才能解锁下一关或下几关，而不能上来就打第二关，即某些关卡必须在其他关卡完成之后才能解锁。这时我们可以用一个有向无环图来表示这种解锁顺序。在这个图中，每个顶点代表一个关卡，每条有向边表示解锁一个关卡的前提条件。如下图1 号端点就相当于第一关，而 6 号端点就相当于是最后一关。![]()
找到入度为零的顶点：入度是指指向某个顶点的边的数量。在本例中，关卡 1 的入度为 0，因为它不需要任何前置关卡。第一步：输出该顶点的编号，即输出关卡 1 的编号。删除该顶点及其相关的有向边：从图中移除关卡 1，以及所有从关卡 1 出发的边。![]()
第二步：重复上述过程，在更新后的图中，关卡 2 和 3 的入度都变成了 0，根据题目要求，选择编号较小的顶点，即输出关卡 2 的编号，并移除关卡 2 及其相关的边。![]()
第三步：输出 “ 3 ”，并删除由该点出发的有向边。![]()
第四步：输出 “ 4 ”，并删除由该点出发的有向边。![]()
第六步：输出“ 6 ”，排序结束。所以，最终拓扑排序的结果是123456。![]()
1. 创建ToplogicalSort类封装排序方法：![]()
![]()
![]()
最小生成树（Minimum Spanning Tree, MST）问题是指在一个加权无向图中找到一棵包含所有顶点的生成树，使得这棵树的所有边的权重之和最小。这个问题在实际中有广泛的应用，比如在网络设计、电路布线、旅游路线规划等方面。常用的最小生成树算法有两种：Prim 算法和 Kruskal 算法。Prim 算法也是一种用于寻找加权无向图的最小生成树（Minimum Spanning Tree, MST）的贪心算法。与 Kruskal 算法不同的是，Prim 算法从图中的一个顶点开始，逐步构建最小生成树，每次添加一个顶点及其对应的最小权重边。步骤3：创建一个优先队列 Q（通常使用最小堆实现），用于存放未被加入 T 中的顶点及其与 T 中顶点的最短边。步骤4：将起始顶点的邻居及其边的权重加入 Q 中。步骤5：取出 Q 中具有最小权重的边，将其顶点加入 T 中，并更新该顶点的邻居到 Q 中。步骤6：重复步骤 5，直到 T 包含所有顶点或者 Q 为空。Kruskal（克鲁斯卡尔算法） 算法是一种贪心算法，用于寻找加权无向图的最小生成树（Minimum Spanning Tree, MST）。它的基本思想是按边的权重从小到大排序，然后依次考虑每条边是否加入生成树，如果这条边的加入不会形成环，则加入它。
1. 网络设计：例如在设计一个覆盖所有城市的光纤网络时，可以通过 Kruskal 算法找到成本最低的网络设计方案。2. 电路布线：在设计印刷电路板时，Kruskal 算法可以帮助确定电线之间的最佳连接方式，以减少材料和成本。3. 聚类分析：在数据挖掘和机器学习中，Kruskal 算法可以用来构建一个基于距离的层次聚类树。3. 遍历排序后的边，对于每条边 (u, v)：如果顶点 u 和 v 不在同一棵树中，则将这条边加入到最小生成树中，并将这两棵树合并成一棵。4. 重复步骤 3 直到森林变成一棵树，即得到最小生成树。贪心算法是一种直观且高效的算法设计策略，其核心在于“贪心选择”原则。在每一步选择中都采取当前状态下的最优（或看似最优）选择，以期望通过这种局部最优选择来达成全局最优解。这种策略类似于一个贪婪的人在每一步都追求即时利益最大化，不考虑长远的所有可能性，但在某些问题上却能意外地得到全局最优解。
1. 确定贪心策略：明确每一步选择时所依据的“最优”标准，选择的方案价值比率要最大。3. 迭代求解：不断执行贪心选择，每次选择都基于当前状态的最优解，逐步缩小问题规模，直至得到最终解。
贪心算法的优势在于其简单性和高效性，但它并不总是能得到全局最优解，因为它忽略了未来选择可能带来的潜在影响。然而，在许多特定类型的问题上（如区间调度、最小生成树、单源最短路径等），贪心算法能够确保得到全局最优解，这通常依赖于问题的特定性质。你经营一家小店，只能使用25分、10分、5分和1分四种硬币找零。现需要找给客户41分钱，问如何组合这些硬币，使得硬币的数量最少？解答提示：使用贪婪算法，优先使用面额最大的硬币，直至找完所有金额。![]()
![]()
如下图所示，给定一个会议的时间表，每个会议有一个开始时间和一个结束时间。如何在有限的时间内有召开多个会议，要求任何两个会议不能同时进行。![]()
![]()
为了实现这一目标，我们可以采用一种贪心策略，即每次从剩余的会议中选择最早结束的会议进行安排。1. 数据结构：使用了一个简单的 Meeting 类来存储每个会议的开始和结束时间。![]()
2. 排序：通过 Java 的 Arrays.sort 方法和自定义的比较器（基于会议的结束时间）来对会议进行排序。3. 贪心选择：遍历排序后的会议列表，选择那些开始时间不早于上一个选定会议的结束时间的会议。这样可以确保选定的会议时间段互不重叠。![]()
给定一个由多个闭区间组成的列表，每个区间表示为 [start, end] 形式，其中 start 是区间的起始时间，end 是区间的结束时间。要求设计一个算法，找出这些区间中最多可以有多少个互不重叠（即没有交集）的区间。注意，边界相同并不视为相交。
示例：
输入：intvs = [[1,3], [2,4], [3,6]]。
输出：2。
解释：可以选出 [1,3] 和 [3,6] 这两个区间，它们没有交集，因此是互不重叠的。
1. 排序：首先根据区间的结束时间（end）对所有区间进行排序。如果两个区间的结束时间相同，则根据起始时间（start）进行排序，以确保在结束时间相同的情况下，优先选择起始时间早的区间（虽然这一步对于最终结果不是必需的，但有助于保持一致性）。2. 贪心选择：遍历排序后的区间列表，使用一个变量来跟踪当前选择的最后一个区间的结束时间。对于每个区间，如果它的起始时间大于或等于当前最后一个区间的结束时间，则选择该区间，并更新最后一个区间的结束时间为当前区间的结束时间。4. 返回结果：遍历结束后，返回记录的区间数量，即为最多互不重叠的区间数。![]()
![]()
背包问题可以通过贪心算法来近似求解。给定一组物品，每个物品有自己的重量和价值，目标是选择一些物品放入背包中，使得背包中的物品总价值最大，同时不超过背包的最大承重限制。![]()
1. 计算性价比：为背包中的每个物品计算其性价比，即价值（value）与重量（weight）的比率。这有助于我们评估每个物品相对于其重量的价值贡献。2. 排序：根据性价比从高到低对物品进行排序。这意味着我们首先尝试装入单位重量价值最高的物品。3. 贪心选择：按照排序后的顺序，依次尝试将物品装入背包中，直到背包满或所有物品都已被尝试。在每一步中，如果当前物品可以完全装入背包（即不超过背包的剩余容量），则将其装入，并更新背包的剩余容量。4. 停止条件：当背包的剩余容量不足以装入下一个物品时，算法停止。由于我们处理的是“0-1背包问题”，因此不需要考虑部分装入的情况；如果某个物品不能完全装入背包，则将其留在背包外。1. 创建物品类，封装物品体积，体积、价值，以及价值密度。
![]()
![]()
![]()
![]()
![]()
递归（Recursion）是编程中的一个重要概念，它指的是一个函数或算法在其定义或执行过程中直接或间接地调用自身。
暴力递归是一种解决问题的方法，它通过将原问题分解成规模较小的子问题来求解，并递归地处理这些子问题直到达到基本情况（base case），即可以直接解决的情况。这种方法并不保留子问题的解，而是每次都重新计算它们，因此效率较低，但在某些情况下非常直接和易于理解。2. 必须要设计递归的终结点f(1)，如果没有终结点，就会导致死循环，最终引起栈内存溢出。3. 递归的方向必须走向终结点：就是设计了f(1)是终结点，那么程序在执行多次之后，就一定会走向终结点。1. 搜索问题：例如八皇后问题、N皇后问题等，需要遍历所有可能的解决方案。2. 组合问题：比如背包问题中的无限制物品背包问题，在没有使用动态规划的情况下，可以通过暴力递归来穷举所有可能的组合。3. 路径寻找：例如迷宫问题，可以通过暴力递归来探索所有可能的路径。4. 排列组合：计算所有可能的排列组合，例如求解所有可能的数列排列。5. 数学问题：例如计算斐波那契数列的值，可以使用暴力递归的方式逐个计算每一项。需求：计算n的阶乘，比如2的阶乘 = 1 * 2 ；3 的阶乘 = 1 * 2 * 3。编写一个程序，打印出给定字符串的所有子序列，包括空字符串。例如，对于字符串 "abc"，应该打印出以下子序列："", "a", "b", "ab", "c", "ac", "bc", "abc"。![]()
![]()
N皇后问题是一个经典的回溯问题，其目标是在一个 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不会处于同一行、同一列或同一对角线上。![]()
![]()
![]()
![]()
![]()
![]()
![]()
你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费?一块金条从中间打断两次，那么就可以将金条分为1段、2段和4段。
1. 使用二进制位操作来决定哪一天应该给出或收回哪一段金条。2. 对于每一天，我们需要支付的金条段是 1 << (day - 1)，位运算，意思是在第 1 天，需要支付 1 段金条；在第 2 天，需要支付 2 段金条；在第 3 天，需要支付 1 段金条；在第 4 天，需要支付 4 段金条。3. 根据需要支付的金额，决定是否给出或收回某一段金条。
![]()
![]()
烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢?步骤1：先将第一根绳子的两头都点燃，同时将第二根绳子的一端点燃。步骤2：当第一根绳子烧尽时（耗时30分钟），立即点燃第二根绳子的另一端。步骤3：当第二根绳子烧尽时（耗时45分钟），立即点燃第三根绳子的两端。步骤4：当第三根绳子烧尽时（耗时75分钟），即完成计时。![]()
![]()
1元钱可以买一瓶汽水，喝完后可以用两个空瓶换一瓶汽水。问：如果有20元钱，最多可以喝到多少瓶汽水？
假设你有20元钱，按以下步骤计算最多可以喝到多少瓶汽水：2. 喝完这20瓶汽水后，可以用20个空瓶换得10瓶汽水。3. 再喝完这10瓶汽水后，可以用10个空瓶换得5瓶汽水。4. 再喝完这5瓶汽水后，会剩下5个空瓶。其中4个空瓶可以换得2瓶汽水，喝完后会有3个空瓶。5. 用2个空瓶换1瓶汽水，喝完后会剩下2个空瓶。6. 用1个空瓶加上借来的1个空瓶再换1瓶汽水，喝完后归还1个空瓶。7. 总共喝了20+10+5+2+1+1+1=40![]()
桌上有100个苹果，你和另一个人轮流拿苹果，每人每次可以拿1到5个苹果。问：如何拿能保证最后一个苹果由你来拿？为了确保最后一个苹果由你来拿，你需要遵循以下策略：后续步骤：无论对方拿了多少个苹果（1到5个），你都要拿足够的苹果，使得两人这一轮拿的苹果总数为6个。1. 一开始你拿了4个苹果，剩下96个，原因是96%6=0。2. 每次两人一轮拿走6个苹果，确保每轮结束后剩余的苹果数都是6的倍数减去2。3. 这样，当剩下6个苹果时，对方拿走1到5个苹果后，你就能拿走剩下的苹果，从而确保最后一个苹果由你来拿。![]()
![]()
假设你有一个圆形的蛋糕放在一个蛋糕盒里，并且需要把这个蛋糕平均切成8份，分给8个人。但是有一个条件：在分发完毕后，蛋糕盒里还必须留有一份蛋糕。如何做到这一点？这个问题实际上是一个思维游戏，需要跳出常规的思考方式。解决方案如下：![]()
在一栋楼的一楼到十楼的每层电梯门口都放着一颗大小不一的钻石。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，你只能拿一次钻石。问：怎样才能拿到最大的一颗钻石？后续步骤：从二楼开始，每到一层楼，比较手中的钻石和当前楼层的钻石大小，保留较大的一颗。![]()
![]()
吴灿锦，泰伯一百零一世孙，明朝开国名将安陆侯吴复的后代，吉林财经大学2019级本科生；
第九届中国国际“互联网+”创新创业大赛吉林省赛区金奖项目总负责人;
第十三届“挑战杯”中国大学生创业计划大赛吉林省赛区特等奖，国家级铜奖项目总负责人；
2022年荣获吉林财经大学创业实践国家级立项第一名项目总负责人。
