- 博客(40)
- 收藏
- 关注
RSS订阅原创 什么是优化
本篇文章会跟分享一些个人认为的优化的本质是什么。这里的优化是指效率上的优化，而非指代码的可读性，易于维护性等代码质量上的优化。通过本篇文章你将会知道什么是优化，优化的本质是什么，还有获得对于优化的一些思考
2022-09-02 13:54:31
1424
原创 你真的了解并查集？
本篇文章会说明并查集是什么，其构造是什么，对应的核心算法，以及优化算法——状态压缩。还有场景的一些使用场景。会有代码，也会有图示进行说明。
2022-09-02 13:50:31
392
原创 如何设计散列表（哈希表）
通过本章可以了解散列表是什么数据结构，为什么叫做散列表？他的特点是什么？以及如何去设计一个散列表？为什么要这么设计？会介绍散列表中三个重要的核心点：散列函数，处理冲突，查找效率。并且会从是什么，到为什么的去剖析散列表的设计。
2022-09-02 13:48:13
1679
原创 01背包
动态规划 （01背包模型）1、基本的背包模型2、动态规划的理解方式通常可以将 动态规划（DP） 问题分为两个部分进行理解：1. 状态表示。2. 状态计算2.1状态表示（抽象点）背包模型，可以表示成二维的一个表示在哪几个物品里面选一个表示背包的体积多少如： dp[i][j] 其中的 i 表示为从i个物品中选择。j表示选择的物品的题解不超过j动态规划需要用到的数据结构是数组，用来记忆之前的属性从而推出下一个的属性的过程。用数组的下标，记录当前的状态，一个状态表示的是当前状态所约束下的集
2021-04-12 23:14:15
62
原创 全平台pip换源教程
更换pip源在linux下更换pip源在用户目录下创建**.pip**目录在**.pip**目录下创建pip.conf配置文件mkdir ~/.pipvim ~/.pip/pip.conf在配置文件下编写一下内容[global]index-url = https://pypi.tuna.tsinghua.edu.cn/simple[install]trusted-host=mirrors.aliyun.com在windows下更换pip源在文件夹的地址栏输入
2021-04-12 15:11:48
149
1
转载 virtualbox中arch全屏
linux操作系统具有天生的优势,今天被推荐看中了manjaro发行版,于是乎在Vbox里安装试了一下,中间填了的坑在下(1)Vbox窗口太小,操作系统无法全屏这个问题百度了下,主要是安装增强功能,win版Vbox的安装目录里有一个叫做VBoxGuestAdditions.os的文件,这个就是用来安装增强功能的,按照下列步骤安装:(1)在linux操作系统里点击菜单栏的设备,选中安装增强功能,这是虚拟机会寻找到VBoxGuestAdditions.os并把它挂载到系统盘旁边,这个不容易发现它的位置
2020-12-19 21:32:32
500
1
原创 模拟队列
模拟队列变量解释：t指向尾指针，h指向头指针初始化的时候h要比t大1，因为第一个插入（只有一个元素）的时候h和t应该指向同一个位置代码：#include<iostream>using namespace std;const int N = 100010;//初始化的时候尾要比头少1，当h = t 的时候只有一个元素，当h > t 的时候为空int h=1,t,que[N];int main(){ int M; cin>>M; w
2020-10-08 19:47:47
71
原创 模拟栈
模拟栈用数组模拟栈，只需要维护一个指针，因为栈的数据是单方向进入的，所以只需要维护一个指针。入栈：stk[++head] = x;出栈：head–查询栈顶元素：stk[head]判断是否为空if(!head)#include<iostream>using namespace std;const int N = 100010;int head,stk[N];void push(int x){ stk[++head] = x;}void pop()
2020-10-08 19:47:14
82
原创 双向链表
双向链表双向链表数据结构具有前后指针的链表结构题目链接https://www.acwing.com/problem/content/829/操作分析注意： 插入操作默认是从k的后面插入0 和 1 是左右边界，不是具体的值0是左边界， 1 是右边界以idx == 1 为结束条件代码：#include<iostream>using namespace std;const int N = 100010;int idx,e[N],L[N],R[N];void ini
2020-10-08 17:44:56
135
原创 模拟单链表
单链表单链表：只有数值跟后指针的数据结构题目地址：https://www.acwing.com/problem/content/828/变量表示：head ： 头指针，始终只想链表的头节点e[N] ： 数值数组，存放每个节点数值，下标表示存储地址，存放的值为节点的值ne[N] ： 指针数组，存放每个节点的指针，下标表示当前节点的存储地址，存放的值是下个节点的地址idx ： 地址，分配的地址，就是各个数组的下标，相当于内存中的0x3fde..之类的。这边的数组相当于为这个链表分配的存储空间
2020-10-08 16:30:34
75
原创 递归
递归递归函数：非常重要的一点就是不要在意他的过程是怎么实现的而是要选择去相信他，这是一定可以实现的。能得到我们想要的结果，并且将它当做结论来使用使用递归函数：1.确定这个函数的功能。2.确定这个函数的返回值。3.相信这个函数可以得到我们想要的。4.在我们的递归函数中怎么使用到这个递归函数本身，也就是他的子问题。5.他的终止条件是什么。（我们递归所变化的参数当为什么值时不用递归就可以明确知道他的返回值）6.在调用递归函数之后我们可以继续进行操作，我们只需要知道他返回的值是什么，无需关心他是怎么
2020-09-23 16:43:18
63
原创 约数之和笔记
约数之和题目链接：https://www.acwing.com/problem/content/99/题目简介：假设现在有两个自然数A和B，S是ABAB的所有约数之和。请你求出S mod 9901的值是多少。输入格式在一行中输入用空格隔开的两个整数A和B。输出格式输出一个整数，代表S mod 9901的值。数据范围0≤A,B≤5×1070≤A,B≤5×107输入样例：2 3输出样例：15注意: A和B不会同时为0。数学知识分析：名词解释：**约数（因数）：**可以被
2020-09-23 16:42:57
205
原创 二叉树
二叉树树的遍历树的遍历顺序，都是以根为主体如果根作为第一个访问的结点 那就是前序遍历前序遍历是最简单的一个遍历，在拿到一个结点后先判断是不是空结点，如果不是空结点，直接访问自身，依次再判断有无左右结点。如果根放在第二个访问的结点 那就是中序遍历中序遍历相对麻烦，其操作过程是在拿到一个结点之后先判断有无左子树如果有左子树先访问左子树直至到没有左子树。再进行访问自身，之后考虑右子树。访问结点的条件：确定以身为根节点，左子树下的所有结点包括左子树结点本身全访问完的情况下才访问自身结点如
2020-09-23 16:42:43
77
原创 动态规划
动态规划动态规划题目类型特点计数有多少种方式走到右下角有多少种方法选出k个数使得和是sum求最大最小值从左上角走到右下角路径的最大数字和最长上升子序列长度求存在性去石子游戏，先手是否必胜能不能选出k个数使得和是sum类型一：求最大最小值例题：LintCode 669：Coin Change[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qBemezGl-1600575649334)(动态规划.assets/15713647269
2020-09-23 16:42:29
148
原创 排列
递归全排列分析实现全排列的思路(两种思路)第一种思路:用函数功能的角度去分析递归、实现排列！举一个例子:全排列 1,2,3他的结果有6种情况:1 2 31 3 22 1 32 3 13 2 13 1 2分析：可以发现第一个数为不同数的时候都有两种情况，当然这里的两种情况是因为我们全排列的数为3所导致的，如果将数的范围增大你会发生其排列的情况也会随之增加。称之为n-1全排列种情况更为合适。试想一下，如果第一个数保持不变，后面的数进行全排列，也就是后面的排列顺序都是不同的，
2020-09-23 16:42:05
225
原创 高精度加法
高精度加法题目链接https://www.acwing.com/problem/content/793/思路输入的时候使用字符串string存储将char类型转换成int类型，使用vector<int> 逆序存储模拟手算加法的过程判断位数，循环最大位数定义一个累加器 t每一次循环t += A[i]因为A始终是最大位数，但是在累加B[i]的时候要判断当前位数是否小于B的位数，如果小于才相加。每次结果都取 t%10，并且t /= 10 如果t大于时则t
2020-09-23 16:41:14
74
原创 高精度减法
高精度减法题目链接https://www.acwing.com/problem/content/794/步骤对大数的处理仍然是用vector<int> 数组进行存储判断哪个数大（始终用大的那个数减去小的那个数，如果是负数，就在结果前面添加负号）如果位数不相等，则位数大的数大如果位数相等，从大的位数开始比较，大的大，如果循环结束则相等相减操作，从低位开始减，不够的借位，t表示是否想前面借位先减去t表示先减掉借位的数t = A[i] - t;然后判断：如果当前位数小于B的
2020-09-23 16:41:02
84
原创 递归实现指数型枚举
递归实现指数型枚举做题思路创建一个空间存储要便利的个数状态如要枚举3个数的所有排列组合，那要创建三个空间，来存储每个数的状态开始枚举要枚举三个数的所有组合，那么就要便利所有的情况，那么每一个数都有选和不选两种情况所以每一个数都要分两种情况进行递归最后终止的条件是枚举的个数不超过三个（三个数进行枚举，可选可不选，所以所选择的个数可以是1~3个）理解采用递归的思路，就是：看要枚举几个数，几个数他递归的层数就是几层因为每个数只有选和不选两种情况，所以他的分支只有两个，是一个二叉
2020-09-23 16:40:31
157
原创 高精度除法
高精度除法原题链接https://www.acwing.com/problem/content/796/步骤倒序用vector 存储大数定义一个int r用于存储余数用引用r做参数，函数里面可以修改r的值模拟除法先判断当前位数上的数够不够除如果够直接除，并取模除下一个如果不够在原本数的基础上乘以10 再加上下一位数变成实现除法操作：累加器（余数r）初始化为0，所以一开始就r = r * 10 + A[i]因为如果不够除当前位数上的值为0，所以不管够不够除直
2020-09-22 17:17:33
67
原创 子矩阵的和
子矩阵和原题链接https://www.acwing.com/problem/content/798/作用快速求某一矩阵区间的和公式子矩阵前缀和公式s[i][j] += (s[i-1][j] + s[i][j-1] - s[i-1][j-1])子矩阵和公式res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]注意点左上方的那个点上的数也包括，所以公式上面的x1,y1都要减一代码#include<iostre
2020-09-22 17:17:03
225
原创 完全背包
完全背包完全背包：每个物品有无限表，表示每新增一个物品可以选取无限次。思维导图完全背包跟01背包的区别：相同点：将集合划分成两部分：未包含新增物品i 的集合 （已知f[i-1][j]）包含新增物品i 的集合**（新增，未知）**求集合的最大值的方式相同：分别求出两部分集合的最大值，再求这两个最大值的最大值求新增的集合最大值的方式相同：对背包容量进行划分第一部分：划分出所有选法中共同拥有的物品（新增物品）第二部分：剩下的都是不一样的物品新增集合的最大值 = 第一部分的最
2020-09-22 17:16:36
122
原创 前缀和
前缀和原题链接https://www.acwing.com/problem/content/797/作用可以快速求某一个区间的和公式初始化前缀和s[i] = s[i-1] + a[i]**求某一段区间的和[l,r] **s[r] - s[l-1]注意点在初始化前缀和以及输入的时候，数组使用1开始可以解决边界问题并且后面求区间的时候也可以直接套用公式代码#include<iostream>using namespace std;const int N =
2020-09-22 17:15:23
72
原创 快排
快排原题链接思路想法：取一个分界值，然后将当前序列按照这个值，分成两个部分，一个部分是小于这个值的，一部分是大于这个值的这个时候已经将一个乱序的序列分成了两个部分，然后同时再对这两个部分同样进行相同的排序操作依次递归下去，直到只剩一个数的时候就不用遍历了，这时候所有的数都已经排列好了实现步骤：设置递归停止条件：if(l >= r)return;这个是停止的条件，就是当需要排序的时候这时只有一个数，所以并不需要排序，直接结束定义一个分界线mid（值）：int mid = a[
2020-09-22 17:14:52
107
原创 归并排序
归并排序题目链接https://www.acwing.com/problem/content/789/思路归并排序也是使用递归，不过其思路更好理解一点，因为理解起来不用理解那么细致。我们按照中间的位置将这个序列分成两个部分，并分别进行排序，这时候这个序列是由两个有序的序列组合起来的然后只要将这个两个序列合并成一个序列就完成了。所以，归并排序就是将一个乱序的序列，分成两个有序的序列再将其合并起来！步骤同样这是个递归，要设置终止条件if(l >= r) return;定义从哪个点
2020-09-22 17:14:21
111
原创 高精度乘法
高精度乘法原题链接https://www.acwing.com/problem/content/795/步骤倒序，用vector存储大数模拟手动乘法将乘数看成一个整体（一位数）每次相乘哪一位就加上前一位相乘所得的值模10取得当前这位的值除10 表示当前位的数已经取了去除前位零注意存在乘完大数的最后一位，但是仍有进位的情况，所以总之条件不仅仅是i < A.size()而是i < A.size() || t t 表示: 累加器去除前位零代码：#inc
2020-09-22 17:13:49
69
原创 二分查找
二分查找整数二分https://www.acwing.com/problem/content/791/思路思路跟平时猜价格的游戏差不多，给你一个商品，再给你一个范围，让你从这个范围里面猜价格每次都选择这个范围的中点，然后判断价格是比中点大还是比中点小，然后再根据这个判断结果缩小范围，以此类推最后剩下一个数的时候肯定就是答案步骤先定义范围int l = 0,r = n-1;然后开始二分(进入循环)，寻找中间点int mid = l + r >> 1;进行判断，根据判断改变范围i
2020-09-22 17:13:19
82
原创 差分
差分矩阵原题链接https://www.acwing.com/problem/content/800/初始化的公式差分跟前缀和的关系，差分是前缀和的逆运算前缀和是将原本所有的数列都当成是一堆差分，然后对其进行求前缀和差分是将原本所有的数列每一个数都当成一个前缀和，然后求他们的差分而他们所使用的公式是一样的，只是所求的变量是不一样的，前缀和是根据原数列的数求前缀和，而现在是根据前缀和求原数列的数差分矩阵初始化公式由上图的前缀和公式可得，s[x][y] = (s[x][y-1] - s[x-
2020-09-22 17:12:42
95
原创 01背包
动态规划 （01背包模型）1、基本的背包模型2、动态规划的理解方式2.1状态表示部分（抽象点）背包模型基本表示成二维的：一个表示在哪几个物品里面选一个表示背包的体积多少动态规划需要用到的数据结构是数组，用来记忆之前的属性推出下一个的属性的过程用数组的下标，记录当前的状态，一个状态表示的是当前状态所约束下的集合，属性：数组的值表示的是属性属性有最大值最小值，和数量等，属性是指当前状态下集合的属性，是基于当前状态的基础上的属性正如上面所说，集合是受状态约束的，约束的变量是数组的
2020-09-22 17:12:18
118
原创 STLgrasp
use frequently STL graspstring（字符串）所有的字符串函数都已经在上面了，下面列几个比较常用的函数：vector(不定长数组)1.导入函数库#include<vector> using namespace std;2.构造函数vector<int> v1 ( nums，value);nums：容量大小 value：值3.赋值v1 = v2;如果v1的容量>=v2的容量，可以将v2的值copy到v1中assign
2020-09-20 12:18:23
90
原创 STL list迭代器
STL list中迭代器1.链表的结构链表的结构：每一个链表上的节点都有三个部分：前指针，值，后指针分别说明一下这三者的作用：前指针(pre)：指向前一个节点的值后指针(next)：指向后一个节点的值值：节点上保存的东西链表是线性结构，由此我们可以知道链表上的各个节点的连接方式就是通过前后指针相连接，要想查找到某个节点只有通过前面的节点或者后面的节点。缺点：所以要查找链表中的某一个节点的值只有通过遍历的方式去查找！优点：插入删除某一个节点非常的方便例如：现在又nod1，nod2，
2020-09-20 12:17:53
388
1
原创 C++ cin输入不支持空格
C++ 的字符输入1. 使用cin输入，遇到空格后或者换行符结束一个字符数组的输入#include<iostream>using namespace std;int main(){ int n = 10; char arr[n]; cin>>arr; for(int i = 0; i < 10; i++){ printf("%c",arr[i]); } cout<<endl; cout
2020-09-20 12:17:29
4192
原创 Boxes_in_a_Line做题笔记
Boxes_in_a_Line 解题笔记题目描述:Background 背景You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands:你在一个线盒在桌子上编号1 … n 从左到右。你的任务是模拟4种命令：• 1 X Y : move box X to the left to Y (ignore this if
2020-09-20 12:16:13
220
原创 VB初步入门
VB 入门记录（一）一、Visual Basic 界面简介打开题目进入界面是这个样子的 图一我们的题目信息在这里 图二然后当你双击那个产生按钮的时候 图三OK，这个时候我们需要用到的窗口界面就基本已经呈现出来了。工程在图的右上角那边...
2020-09-20 11:31:04
20394
7
原创 奇怪汉诺塔笔记
奇怪的汉诺塔普通的汉诺塔问题问题解释：借助B将A上面的圆盘串到C上面，大的圆盘不能放小的圆盘上面。每次只能移动一块圆盘。怎么样移动才能完成任务？思路分析：最简单的情况：当A上面的圆盘只有一块的时候：直接将A上面的圆盘放到C上面即可A——>C其次：当圆盘数量等于2的时候：将第一个圆盘放到B上面，再将A上面最底下的圆盘放到C上，再将B上面的圆盘放到C上A——&g...
2020-09-20 11:30:42
174
原创 多种组合算法对比
组合算法（二进制辅助法）1.什么是数学中的组合组合和排列不同，组合不需要考虑选择的元素的顺序，而排列需要。组合：从n个数中选择k个数组成一个组合，看有多少种不同的组合，每个数选择的先后顺序不受限制Cnk=Ankk!=n!k!(n!−k!)C^k_n = \frac{A_n^k}{k!} = \frac{n!}{k!(n!-k!)}Cnk=k!Ank=k!(n!−k!)n!...
2020-09-20 11:30:11
533
原创 C++实现组合算法
组合算法（二进制辅助法）1.什么是数学中的组合组合和排列不同，组合不需要考虑选择的元素的顺序，而排列需要。组合：从n个数中选择k个数组成一个组合，看有多少种不同的组合，每个数选择的先后顺序不受限制Cnk=Ankk!=n!k!(n!−k!)C^k_n = \frac{A_n^k}{k!} = \frac{n!}{k!(n!-k!)}Cnk=k!Ank=k!(n!−k!)n!...
2020-03-26 20:58:42
2764
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人