b站视频 文章目录 #21堆排序前传堆和堆的向下调整#22堆排序的过程演示#23向下调整函数的实现#24堆排序的实现1#25堆排序的实现2#26堆排序的时间复杂度#27堆的内置模块#28topk问题#29topk实现#30归并排序归并 博客cPen_web#21堆排序前传堆和堆的向下调整 ### 堆排序——什么是堆 # 堆：一种特殊的完全二叉树结构 # 注：完全二叉树：满的，最后一排可以少 # 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大 # 小...
带权并查集是普通并查集的进阶版本，功能更加强大。 普通并查集只能判断两个元素是否在一个集合中，带权并查集可以维护集合元素之间的关系，这个关系由每个元素的权值维护。 对权值的维护，我们需要在find()，unite()操作中分别进行修改。 例：399. 除法求值 class UnionFind { public:unordered_map<string, string> p;unordered_map<string, double> d;UnionFind(vector<vector<string>>& equations, vector<double>& values) {f...
并查集是一个非常优雅简洁的，相对高级的数据结构，常常用于元素分组问题。 对于并查集的介绍和推导这里不细说，推荐看Pecco的算法学习笔记。这里主要记录我使用并查集刷题的模板和技巧。 一、什么时候使用并查集？ 个人认为并查集可以用在图中，可以用来求取图中的连通分量。当然题目不一定会直接给出图的数据结构，可能是一个二维数组（200. 岛屿数量），也可能是多个互相连接的结点（1319. 连通网络的操作次数）。可以多做几题，...
数据结构和算法绪论 什么是数据结构？数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关程序设计 = 数据结构 + 算法逻辑结构和物理结构 逻辑结构数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构，数据的逻辑结构分为以下四种：集合结构：集...
本文将讨论指针堆与数组堆的区别，和指针堆的具体实现方式。 题目：洛谷P3378 啊对了，下文不会解释指针是什么、指针的用法、为什么加“&”等基础问题，需要的建议去看《算法竞赛入门经典训练指南》中指针版名次数(treap)的实现，或是向懂的小伙伴提问。 一 指针与数组的比较 数组版中，由于下标的特殊性质，我们可以快速找到某个节点的父亲节点。所以在数组版中，大多使用的是从叶子往根节点更新的插入/删除方式。同时，数组版的原...
最大最小值DP Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state. routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i] 有时候也会min(f[x-1]+1, f[x])， 特别时重复走过x 746. Min Cost Climbing Stairs 到i的路径来自于i-1和i-2。最后一步可以为n-1或者n的总cost。 class Solution { public:int minCostClimbingStairs(vector<int>...
动态规划（DP）不是某种具体算法，而是一种思想。把大问题转化为小问题，利用小问题的解推断出大问题就是DP的核心思想。step 1: 设计状态。把面临的每一个问题，用状态表达出来。 step 2: 设计转移。写出状态转移方程，从而利用小问题的解推出大问题的解。两种状态转移的方法1.pull型：从哪来， 从0到n 2.push型：到哪去， 从n到0e.g.上楼梯问题 pull: f[n] = f[n-1] + f[n-2]; push: f[n] -> f[n+1] += f[n] f[n+2] += f[n] push能...
背景 最近在恶补数据结构和算法相关的知识，查询到一本比较好的书籍算法笔记，然后就开始学习了，学完第二章C/C++语言基础后，做了第三章的题目，虽然书上已经有题解了，但是还是想发表这篇文章，原因是通过记录下来我的学习过程，以提醒和鼓励自己。 第三章题解 #include <stdio.h> #include <cstring>int main() {}/*** 说反话* @return*/ int reverseWords() {char strOri[80] = {};char words[40][80] = {};gets(strOri);int r...
目录1 贪心算法1.1 基本概念1.2.1 贪心算法解释1.2.2 贪心算法的证明问题1.2 贪心算法求解思路1.2.1 标准求解过程1.2.2 贪心算法解题套路1.3 贪心算法套路解题实战1.3.1 例一：会议日程安排问题1.3.2 例二：居民楼路灯问题1.3.3 例三：哈夫曼树问题1.3.4 例四：项目花费和利润问题 1 贪心算法 1.1 基本概念 1、最自然智慧的算法 2、用一种局部最功利的标准，总是能做出在当前看来是最好的选择 3、难点在于证明局部最优解最功利的标...
密钥协商的输入包括椭圆曲线参数（具体参数情况请参见6.2.2），以及己方私钥s和对方公钥W，注意这里的公私钥都必须是在同一条椭圆曲线上选取。以下假设椭圆曲线参数、己方私钥s和对方公钥W都是合理有效的。密钥协商算法如下： ─────────────────────────────────────── 算法 密钥协商 输入： 己方私钥s，对方公钥W，椭圆曲线参数 输出： 协商出的秘密值s。 步骤： step1、...
进制转换 进制转换是一个很常用的技巧，平时在刷题中一般是一个小模块，在一个大题里面作为数据处理的步骤。 数据定义：待转换数Q为W进制，需要转换为P进制。 下面是进制转换的一般流程： （1）将Q先转换为10进制数temp （2）将temp再转换为P进制 以下为算法的详细步骤： （1） 首先要先明确一个定义，即十进制的数y=d1d2d2d3...dny=d_{1}d_{2}d_{2}d_{3}...d_{n}y=d1?d2?d2?d3?...dn?，如53245，5万2千3百4十5。令其为yyy，那么其...
说明： 用Python实现十大排序算法，仅有简单解释，无算法的详细介绍。 相关术语： 稳定排序：如果a原本在b的前面，且a==b，排序之后a仍然在b的前面，则为稳定排序。 非稳定排序：如果a原本在b的前面，且a==b，排序之后a可能不在b的前面，则为非稳定排序。 原地排序：指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换。 非原地排序：需要利用额外的数组来辅助排序。 排序算法（默认从小到大进行...
一般用 Tarjan 算法解决 桥和割边是一个东西 割点和割边 定义 若对于无向连通图的一个点 \(x\)，从图中删去这个点和与这个点相连的所有边后，图不再是连通图，则 \(x\) 为这个图的割点。 若对于无向连通图的一条边 \(e\)，从图中删去这条边后，图不再是连通图，则 \(e\) 为这个图的割边。 当然那张图可能本来就不连通，所以严格来说是把一个连通块断开了，改变了原来的连通块是否连通，是这个连通块的割点或割边。不过从总体来看，...
由于想把文章写的短一点，所以把割点和这篇分开了。 在阅读本文之前，请先阅读割点与割边 边双联通分量 Edge Double Connected Component 先讲边双是因为它比点双简单 性质 先给定义：不存在割边的极大双连通子图 （再加入任何一个/一些点后，它都会不连通或出现割边，不再是 e-DCC） 画张图吧，好理解红边是割边，圈出来的是三个双联通分量。 性质：边双连通分量中任意一条边都包含在至少一个简单环中这条性质也是边双的充要条件。...
这道题也当做二叉搜索树的建树模板。这道题其实直接把这颗树建出来后，比较前序序列和中序序列即可，这里我用的数组实现，更好写和查错qwq。 code： #include <bits/stdc++.h> using namespace std; int n , len; string a , b , c; char tree[400040] , pd[400040] , st[400040]; void t_insert(int i , char x){if(tree[i] == '?'){ //如果查找到了空位置，那么那个位置即为该插入的位置 tree[i] = x;return;}if(tree[i] > x) t_...