Zsprinkle-CSDN博客

原创算法基础16 —— 递推(铺骨牌问题 + 信奥一本通 1313 位数问题 + NOIP 2002 过河卒)

基本概念所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。初始条件如何得到呢？其实，初始条件要么是问题本身已经给定，要么是通过对问题的分析与化简后确定的递推的方式顺推逆推递推的特点可用递推算法求解的题目一般有以下两个特点：问题可以划分成多个状态；除初始状态外，其它各个状态都可以用固定的递推关系式来表示。递推入门 — Fibonacci数列1、1、2、3、5、8、13… …递归写法：#include <iostream>

2022-02-13 22:43:55 1078

原创算法基础15 —— 分治算法(归并排序 + 快速排序)

分治法的基本概念、思想分治法是一种很重要的算法。字面解释，分治分治，分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。不难发现，分治法的思想与递归极其类似。实际上，分治与递归确实是密不可分。分治法的策略将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破。分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模1较小）则直接解决，否则将其分解为k个规模较小

2022-02-12 22:14:49 10537

原创算法基础14 —— 图论入门之迪杰斯特拉算法(Dijkstra)

回顾Floyed算法可以求任意两点之间的最短路径，但是Dijkstra算法只能求一个结点到另一个结点的最短路径，它是一个单源的最短路径算法Floyed算法的时间复杂度为O(n^3)，故一般情况下数据范围要求在100以内Dijkstra算法描述设起点为s，dis[v]表示从s到v的最短路径长度，如dis[3] = 6表示从起点到3号结点的最短路径为6pre[v]为v的前驱节点，用来输出路径初始化：dis[v] = ∞(v ≠ s);//初始时路径为无穷 dis[s] = 0;//s

2022-02-11 01:51:46 1296

原创算法基础17 —— 单调栈(Acwing 830 单调栈)

单调栈的分类单调递增栈：栈中的元素从栈底到栈顶是单调递增的。不难发现，单调递增栈的出栈序列递减单调递减栈：栈中的元素从栈底到栈顶是单调递减的。不难发现，单调递减栈的出栈序列递增单调栈的应用求数列中每个元素X的右边第一个大于元素X的新元素Y求数列中每个元素X的左边第一个小于元素X的新元素Y给一个数组，返回一个大小相同的数组，返回的数组的第i个位置的值是对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素给一个数组，返回一个大小相同的数组，返回的数组的第i个位置的值是对于原

2022-02-10 13:19:23 825

原创算法基础14 —— 图论入门之弗洛伊德算法(Floyed + Dijkstra + Bellman-Ford + SPFA)

入门概念带权图：如下图所示，我们把边带有权值的图称为带权图可以将边的权值理解为两点之间的距离一张图中任意两点间会有不同的路径相连最短路径：最短路径就是指连接两点的这些路径中最短的一条Floyed、Dijkstra、Bellman-Ford、SPFA可以有效地解决最短路径问题。需要注意的是：边的权值可以为负。当出现负边权时，有些算法不适用最短路径问题是图论中典型的问题，多数模型可以归结为一下三种管道铺设线路安装地图规划问题引入国庆期间，7535寝室计划去旅行。在出发前，寝室长

2022-02-10 02:12:52 3144

原创算法基础13 —— 树进阶(优先队列的应用—合并果子 + 哈夫曼树)

堆的应用虽然可以把堆画成二叉树的形式，但是其本质依然是一维数组拓展：树状数组也可以画成树的形式，它与堆一样，本质依然是一个一维数组堆的例题：NOIP 2004 合并果子非常妙的一道例题，即是堆，也是贪心分析：假设目前有四堆果子分别是2、3、5、6。合并果子方案一：如果先将2与3合并，会耗费体力值5；再将5与6合并，会耗费体力值11；最后将5与11合并，会耗费体力值16；采取以上合并方案，一共需要耗费体力5 + 11 + 16 = 32合并果子方案二：先将耗费体力最小的2与3合并，会

2022-02-09 21:28:27 1245

原创算法基础12 —— 树进阶(二叉搜索树 + 堆—优先队列)

二叉搜索树定义：二叉搜索树，又叫二叉排序树、二叉查找树(Binary Search Tree)它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树性质：二叉搜索树的中序遍历结果为一个无重复数据的升序序列判断方法：将待判断的二叉树采用中序遍历，结果保存在vector中，然后遍历vector，判断是否满足是升序并且无重复数据，不满足则不是二叉搜

2022-02-08 17:53:28 1431

原创算法基础11 —— 树入门(二叉树的遍历以及构造 + 普通树转换成二叉树 + 例题 + 二叉树的一些操作)

字符二叉树的遍历对于以上二叉树先序遍历为(根左右) : ABCDEFG中序遍历为(左根右) : CBEDAFG后序遍历为(左右根) : CEDBGFA层序遍历：(从左往右、从上往下) ABFCDGE以先序次序输入以上二叉树：ABC##DE###F#G##代码实现遍历操作：#include <iostream>#include <queue>using namespace std;typedef struct node{ char data;

2022-02-07 18:36:31 2795

原创算法基础11 —— 树入门(树的相关术语 + 二叉树的性质 + 顺序及链式存储 + 二叉树的遍历)

树？盆栽？下图是一棵典型的树数据结构中的树长这样：(不像树？倒过来看看?)树的相关术语一棵树是由n(n>0)个元素组成的有限集合，其中：结点：每个元素称为结点(node)根：每棵树有一个特定的结点，称为根结点(root)，如上图的结点 ①子树：除根结点外，其余结点能分成多个互不相交的有限集合，其中每个子集又都是一棵树，这些集合称为这棵树的子树。性质一：一棵树中的任意两个结点有且仅有唯一的一条路径连通。性质二：一棵树如果有n个结点，那么它一定恰好有n-1条边

2022-01-25 22:06:17 602

原创算法基础10 —— BFS (迷宫问题 + 一维坐标的移动 + 炸弹人 + 蒜头君回家)

前置知识 - 队列什么是队?STL —— queue特点：先进先出(First In First Out)方法：push(x):将x入队pop():队首元素出队front( ):获取队首元素back( ):获取队尾元素empty( ):判断queue是否为空size( ):队列长度#include<queue>#include<iostream>using namespace std;int main(){ queue<int&

2022-01-22 16:15:41 653

原创算法基础1 —— 时间空间复杂度 + 进制转化

算法是解决问题的方法与步骤。

2022-01-16 14:03:22 2047

原创算法基础9 —— 数论 (倍数 + 约数 + 素数(埃氏筛法) + 欧几里得与拓展欧几里得算法 + 快速幂)

数论 - 倍数定义：对于自然数a和b，如果存在自然数k，使得k * a = b，那么称b是a的倍数性质：一个数有无穷多个倍数所有数都是其自身和1的倍数(任意一个整数x，一定有 1 * x = x)[1,n]范围内的x的倍数一共有n/x(向下取整)个举例说明第三条性质：例1：取n = 12，x = 2,设在区间[1,12]内2的倍数最多有k个，则2 * k <= 12，即k <= 6。[1,12]内2的倍数一共有6个，分别为2( 1 * 2 )，4( 2 * 2 )，6(

2021-08-09 00:56:58 1073

原创算法基础8 —— 详解贪心算法(部分背包问题 + 区间调度问题)

引言贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。——《算法导论》

2021-07-26 00:49:34 7782

原创算法基础7 —— 二分算法 (二分模板 + 洛谷-A-B数对 + 蓝桥杯-分巧克力) + 浮点二分(求一个数的三次方根 + 剪绳子)

二分查找

2021-07-11 00:03:11 901 1

原创算法基础6 —— DFS(全排列 + 数独游戏 + 子集 + 马走日 + N皇后 + 迷宫)

DFS的算法 —— 不撞南墙不回头,不到黄河心不死例1 全排列问题例2 子集例3 数独例4 马走日例5 N皇后例6 迷宫例7 染色DFS总结与模板

2021-06-26 17:31:59 631 1

原创算法基础5 —— 线性表(链表的建立、输出、查找、插入、删除等操作)

线性表定义：线性表是最基本的一种数据结构，是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表中除了首元素和尾元素之外，每一个元素都有唯一的前驱和唯一的后续线性表包括顺序表和链表，其中，可以将顺序表理解为数组链表：链表由各结点组成，每个结点至少包括数据域和指针域。在上图中的链表里，head 为头结点(一般不存放数据)，5所在结点为尾结点且其指针域为NULL物理与逻辑物理上连续指的是数据元素在计算机内存中的地址是连续的逻辑上连续指的是人们想象中的元素相邻链表

2021-06-22 00:34:30 3906

原创基础算法4 —— 结构体(成绩统计) + 栈(模拟进制转换 + 优秀的拆分) + 指针

结构体结构体的实际应用场景：在实际问题中，一组数据往往具有不同的数据类型。比如，某次期末考试中要记录一个学生的考试信息，除了有姓名(char)外，还有班级(int)、性别(char)、语文、数学、英语的分数(int)等信息，这些信息中，类型不一样。那么，该如何存储呢？为了解决这类问题，引出了一种构造数据类型 —— 结构体类型。定义结构体的方法：struct 结构体类型名{ ... ... };例如：struct student{ int num;//学号 char name

2021-06-11 11:51:37 937

原创算法基础3 —— 递归(下) 杨辉三角 + 欧几里得算法 + 汉诺塔 + 递归与数组

例1 递归求解杨辉三角(如果想打印出杨辉三角，可以开一个二维数组，将每行每列的数值存入数组之中。本题使用递归求杨辉三角中的数值，可以不开数组，但是同样需要利用二位数组的思想来解题。)求解第一步：先将上图的杨辉三角向左旋转，并建立坐标，如下图所示：设delta(x,y)表示二维数组中第x行第y列所对应的值。由上图不难发现当x == y的时候，delta(x,y) = 1; 即delta(0,0) = delta(1,1) = delta(2,2) = delta(3,3) = delta(4,4

2021-06-06 18:19:22 829

原创算法基础3 —— 递归(上)

递归递归是算法竞赛中的难点。传说人可以理解迭代，但是神才能理解递归。(不要试图"理解"递归，有很大风险把自己绕进去)To Iterate is Human, to Recurse, Divine. —L. Peter Deutsch定义直接或间接地出现对自身的调用。本质递归 = 递进 + 回归(递进与回归缺一不可)如何理解递进与回归？你的面前有一扇门(一号门)，打开这扇门，看到屋里面还有一扇门(二号门)。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门(三号门)，你继续

2021-06-06 10:17:46 654