基础算法:高精度

发布时间:2022-10-27 C++ 基础算法
1.高精度加法 AcWing 791. 高精度加法  原题如下 给定两个正整数(不含前导 0),计算它们的和。 输入格式 共两行,每行包含一个整数。 输出格式 共一行,包含所求的和。 数据范围 1≤整数长度≤100000 输入样例: 1223 输出样例: 35 代码如下: #include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;string a,b;vector<int>A,B;vector<int...

前缀和 - 一维与二维

发布时间:2022-10-29 C++ 基础算法 算法
一维前缀和 一、概述 对于一维数组A,下标从1开始,包含元素a[1]、a[2]、a[3]、a[4]、a[5]…… ​​​​对于一维数组A的前缀和数组S,下标从1开始(S[0]为0) S[n] == a[1]+a[2]+a[3]+a[4]+a[5]+……+a[n] 常用公式: S[i] == S[i-1]+a[i] a[l]+a[l+1]+a[l+2]+……+a[r-2]+a[r-1]+a[r] == S[r]-S[l-1] 二、题目 前缀和 三、代码段 #include<iostream>us...

二叉树相邻节点最小绝对差值(likou530)、二叉树中的众数(liou501)

发布时间:2022-10-28 LEETCODE 基础算法 算法 深度优先
二叉树相邻节点最小绝对差值这题的解题方式和判断二叉搜索树是一样的。取出上一个数据和本次数据进行相减然后取绝对值判断。 class Solution { List<Integer> ans=new ArrayList<>(); public int getMinimumDifference(TreeNode root) { dfs(root); return min; } int min=Integer.MAX_VALUE; ...

二叉树的公共祖先likou236

发布时间:2022-10-31 基础算法 算法 数据结构
这是一个很不错的题目,让我复习了从叶子节点遍历到根节点的方法。 在说着提之前,我们来说说后续遍历: 后序遍历是一个左右中的方式,当我们画好二叉树的 图,更着遍历一遍的时候,就会发现: 左边完了去右边,右边完了再去中间。 是不是有一种从写往上遍历的感觉!!! 咱们来仔细分析一下这个题: 公共祖先是啥? 就是同一个或间接的根节点。  我们第一个想到的就是头部根节点,它是所有节点的公共祖先。 这题说,求最近的公共祖先。 也就是可以这样认为: 一个根节点,左边有p或者q,右边有p或者。 题目说了,所有元...

HNUCM新生赛汇总

花了一些时间把以前的新生赛全部做了一下,稍微写了一下题解,不算很详细,但也不算很简陋,因为是面向新生的,所以全部使用C语言而没有使用C++书写,有些代码可能看着比较臃肿,有些代码是我看了题目后发现以前做过觉得没必要再写一遍了,各位做借鉴即可,可优化的部分还是要尽量优化。 写题解主要还是一时兴起吧,当初还是个小萌新的时候,看学长们的新生赛题解,学长们都是使用C++写的,阅读代码还是有一定阻碍的。恰逢新生赛,蓝桥杯选拔快要开始,在备战湖南省赛期间每晚抽一些时间,给各位写一份C的题解,希望能给大家带来一些帮助。...

线性DP基础

发布时间:2022-11-03 算法 ACM练习 C++ 动态规划 基础算法
线性dp hdu—1712:分组背包 ACboy needs your help Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 12505 Accepted Submission(s): 6818 Problem Description ACboy has N courses this term, and he plans to spend at mo...

HNUCM2018年新生赛重现赛——2020新生赛

发布时间:2022-11-22 基础算法 算法 贪心算法 C语言
HNUCM2018年新生赛重现赛——2020新生赛 签到题:J 简单题:A,B,C,G,H 中等题:I(代码),E,F 困难题:I(证明),D A: XP的素数 题目描述 XP最近对素数很痴迷,特别是那些特殊的素数,其中有一类素数被称为孪生素数。其定义如下:如果一个数k是素数,k+2也是素数,那么k和k+2成为一对孪生素数。请计算一个给定区间m和n(0<m<n)中孪生素数对的个数。 输入 单组输入数据 m n (0<m<n<1000) 输出 请输出一行结果:区间[...

代码实现如何将yolov5数据格式转换为coco格式

很多训练算法使用coco格式,而原版的数据集可能采用yolov5的数据格式,故写个简单的教程; yolov5数据集的目录格式:  images存放的图像,例如 1.jpg,2.jpg. labels存放的是对应图片的标注信息,例如 1.txt,2.txt. txt 中信息是这样的: (框高)每一行对应一个bbox框信息,分别是class_id ,xc(框的中心x坐标),yc(框的中心x坐标),w(框宽),h (框高) coco数据集的目录如下: instances_test2017.json的格式如下...

数位区间DP+组合数学

发布时间:2022-11-04 笔记 算法 ACM练习 C++ 动态规划 基础算法
数位区间DP+组合数学 hdu2089:数位dp 不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 91160 Accepted Submission(s): 38144 Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有...

Python语法入门(一)

发布时间:2022-11-05 基础算法 开发语言 PYTHON
Python语言是比C和C++语言更高级的语言,Python不像C/C++那样,Python有系统自带的大整数模式,而且Python没有那么多的头文件,其中的一些模块使用起来比C/C++方便,本篇将会概述Python的·一些入门(1),包括一些基本的块、数据类型、函数的使用等。 目录 一.输入和输出 1.字符串的读入 2.字符串定义时读入 3.整型的读入...

二叉搜索树的最近公共祖先likou235、二叉搜索树的插入元素likou701

发布时间:2022-11-05 基础算法 算法 深度优先
我发现只要是带了二叉搜索树的,都需要使用它的特性: 左节点比根节点小 右节点比根节点大 首先判断p、q是否有其中一个在根节点上: 这样就会造成本身就是最近公共祖先 判断根节点下是否有p,q子节点,可以使用p<root.val&&q>root.val,不过在这里有一个坑,题目并没有指定p一定是左节点、q一定是右节点,所以一定要多加一个q<root.val&&p>root.val,这样就会避免。 什么情况p,q在左节点呢: p、q都小于root.val时...

算法入门(快排,归并,二分详解!)

编码之路,道阻且艰 目录 一、快速排序  二、归并排序  三、整数二分  四、浮点数二分 总结 一、快速排序 思路:分治思想,先随机从数组中取一个数x,然后通过数组中的数与x比较划分左右两个区间,然后递归处理左右两个区间,完成快排。时间复杂度o(n*logn)  暴力求解做法:用a,b数组分别存小于等于x和大于x的数,然后在各自数组里排序,然后依次将a,b数组的内容存入q中。 题目: 代码: #include<stdio.h>void my_qsort(int a[] , int l ...

找到一个最小的数,其十进制、八进制、二进制都是回文数C++

发布时间:2022-11-08 数据结构 算法 C++ 基础算法 重交题库
【问题描述】 所谓回文数是指一个数从左向右和从右向左看数字顺序是一样的,如121,4994等。有些数其十进制数、八进制数和二进制数都是回文数。请设计程序找出大于10且其十进制数、八进制数和二进制数都是回文数的最小正整数。 【输入形式】 本题无输入 【输出形式】 输出一个整数 #include<iostream>#include<vector>#include<cmath>#include<algorithm>...

reverse函数反转字符数组getline

发布时间:2022-11-04 C++ 基础算法 算法 数据结构
reverse函数反转字符数组 #include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() {     char a[101];     cin.getline(a,sizeof(a));     int m=strlen(a);     reverse(a,a+m);     puts(a); }  ...

洛谷题单 Part 2.7高精度

发布时间:2022-11-09 C++ 基础算法 算法 康复训练
复习大半个月其中,终于回来了。贪心做到一个题要用高精度,所以来这把高精顺便写了,因为 A C M ACM ACM可以带板子进考场,所以我在网上找了一个板子。 高精度的具体思路就是,因为 c ...

ACM区域赛冲击练习第一周题单

数据结构模拟题——uva 周一模拟 周二模拟 周三模拟 周四模拟 周五模拟 周六模拟 周日模拟 复习题:——poj,hdu 线段树 状态压缩dp 扩展欧几里得 拓扑排序专题: hdu,poj 拓扑排序1 拓扑排序2 并查集+拓扑排序 拓扑排序4 洛谷 p1113普及 p1347提高 p1685省选 p3243提高 p1983提高 p1038提高 p4934省选 p4017普及 p2597省选 最短路径: Floyd—Warshall: hdu 模板 Floyd Floyd变形 Floyd优化 打印最短路 ...

Acwing779. 最长公共字符串后缀(模拟)

发布时间:2022-11-10 基础算法 算法 JAVA 开发语言
思路:1、对于输入的每一组字符串,对字符串进行反转            2、比较该组中第一个字符串的所有字符和剩余字符串的字符匹配个数,如果第i个字符和剩余字符串都匹配成功,则加入结果字符串中。不匹配则直接终止输出。   import java.util.*;public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (!sc.hasN...

DP基础模板

发布时间:2022-11-02 基础算法 算法 动态规划 图论
DP基础模板 基础dp hdu2182:Frog Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3060 Accepted Submission(s): 1363 Problem Description A little frog named Fog is on his way home. The path’s length is N (1 <=...

洛谷题单 Part 2.5 贪心

发布时间:2022-11-10 算法 C++ 贪心算法 基础算法 康复训练
前一阵子在准备高数月考 作息有点不太正常 所以最近的进度比较慢 虽然马上就要线代离散高数期中了 但是我也会尽量多学 C + + C++ C++ 不要拖累队友 贪心算法 指的是决策时都采取当前最优解的算法。有的时候,这样做确实可以获得最优解。 这类算法都要具体问题具体分析 上题 P1208 ...

[数据结构]DFS——全排列

发布时间:2022-11-11 数据结构 算法 C++ 基础算法 深度优先
1.DFS 图的深度优先搜索算法:先一条路走到黑,走不下去了再返回到上一顶点,直到遍历完所有顶点。 1.1 全排列 Subject:输入一个正整数n,输出1~n的全排列。 Steps:u:位数;i:1~n的数字。1.创建path[u]数组储存排列。当u==n时输出。2.创建state[i]判断数字i是否被使用。0未用,1已用。3.定义函数dfs(int u)表示给第u位赋值,并改变i的状态(赋1)。4.在函数dfs(u)中,完成第u位赋值后,递归给第u+1位赋值。5.回溯后改变i的状态(赋0)。 #i...

Acwing 蛇形矩阵

发布时间:2022-11-12 基础算法 算法 深度优先
 方法1:采用dfs搜索的思想 从当前点走到下一个点,有上下左右四种可能,可以设置一个方向属性,表示该点应该按照哪个方向走,如果走到的下一个点,不满足在矩阵的条件或者该点已经填充过了,则需要换方向了。   public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] a = new ...

基础算法:归并排序

发布时间:2022-10-27 基础算法 排序算法
Acwing 787.归并排序 给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 n。 第二行包含 n 个整数(所有整数均在 1∼10e9 范围内),表示整个数列。 输出格式 输出共一行,包含 n 个整数,表示排好序的数列。 数据范围 1≤n≤100000 输入样例: 53 1 2 4 5 输出样例: 1 2 3 4 5 代码如下:  #include <iostream>using nam...

高精度加法(C++基础算法)

发布时间:2022-10-31 算法 位运算算法 C++ 开发语言 基础算法
大整数:位数在  级别 首先将大整数用字符串存下来,按照从个位到最高位进行存储到数组中; 然后遍历两个数组,从个位开始累加,并将结果存储到新的 vector 中; 最后从后往前输出和的各个位 题目描述 给定两个正整数(不含前导 ),计算它们的和。 输入格式 共两行,每行包含一个整数。 输出格式 共一行,包含所求的和。 数据范围  整数长度  输入样例: 1223 输出样例: 35  代码如下: #include<iostream>#include<algorithm>#includ...

高精度算法and vector

发布时间:2022-11-09 C++ 基础算法 算法 数据结构
一.高精度 【高精度数】 ​ 在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加、减、乘、除、乘方、阶乘、开方等运算。 【思想】 高精度算法本质上是用字符串模拟数字进行计算,再利用类似于数学里的竖式的形式,一位一位进行相关计算 。 【数据存储】  当输入的数很长时,可采用字符串方式输入,这样可输入位数很长的数,利用字符串函数和操作运算,将每一位取出,存入数组中(记得减去 '0' )。 111 ...

搞懂图论中的中心性

0. 前言 中心性(Centrality)表示的是图(Graph)中,每个节点的重要度。图在越来越多的领域中被应用,甚至在图像小样本分类中,也有了应用,比如2022年的一篇CVPR论文《Learning to Affiliate: Mutual Centralized Learning for Few-shot Classification》就用了中心性来解决小样本分类的问题。 本文就是对目前比较主流的几种求图中心性的方法进行的梳理。 在进行算法的说明之前,首先要搞清楚,什么是“节点的重要度”。不同的...

深度学习基础-2

0 前言 本文是公司组内分享的课程笔记,主要参考了北邮鲁鹏老师的《计算机视觉与深度学习》课程,课程视频链接在这里。 上一讲:深度学习基础-1 本讲在上一讲的基础上,更近一步,将分类器替换为了全连接分类器,并围绕全连接分类器介绍了实际训练模型时,常用的知识点。 图0-1 本讲总体框架图 1 全连接神经网络 首先来回顾一下上一讲的线性分类器 f ( x ...

刷题系列之二叉树-104二叉树的最大深度

发布时间:2022-11-20 基础算法 算法
Problem: 104. 二叉树的最大深度 思路 这道二叉树的题目,让求二叉树的最大深度,显然需要通过遍历二叉树来解决。当然你可以采用层序遍历,通过维护一个全局变量,来更新最大深度。但这里就采用遍历二叉树的方法求解 解题方法 首先思考一个问题,一个树的最大深度是怎么计算的?一棵树的深度就是计算这棵树的根节点的深度,根节点的深度是通过计算左子树的深度和右子树的深度来得到的。这个问题可以分为两个步骤来求解,第一步,找出计算根节点深度的方法:左子树的深度即为left,右子树的深度即为rig...

D. Vertical Paths

发布时间:2022-11-16 基础算法 算法
D. Vertical Paths time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are given a rooted tree consisting of nn vertices. Vertices are numbered from 11 to nn. Any vertex can be the root of a tre...

差分 - 一维与二维

发布时间:2022-10-29 C++ 基础算法 算法
往期文章:前缀和 - 一维与二维 一维差分 一、概述 对于数组a[N],有差分数组b[M]  (M > N) a为b的前缀和;  b为a的差分 下标从1开始,两者的联系如下: a[1] == b[1] a[2] == b[1] + b[2] a[3] == b[1] + b[2] + b[3] a[4] == b[1] + b[2] + b[3] + b[4] ………… a[N-1] == b[1] + b[2] + …… + b[N-2] + b[N-1] 根据两者的联系可知(一维差分的应用):...

letcode第319场周赛

letcode第319场周赛 6233. 温度转换 给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度,以 摄氏度(Celsius)为单位。 你需要将摄氏度转换为 开氏度(Kelvin)和 华氏度(Fahrenheit),并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。 返回数组 ans 。与实际答案误差不超过 10-5 的会视为正确答案**。** 注意: 开氏度 = 摄氏度 + 273.15华氏度 = 摄氏度 * 1.80 + 32.00 示例 1 : 输...

lower/upper_bound

发布时间:2022-11-12 基础算法 算法
一 lower_bound lower_bound(数组首地址,数组终地址,数值a) 两个地址是闭区间的 他能够返回大于等于a的第一个数的地址 二 upper_bound upper_bound(数组首地址,数组终地址,数值a) 区间是闭区间 他能够返回大于a的第一个数的地址 被操作的数组必须是有序的 ...

三种算法最小公约数

发布时间:2022-11-17 基础算法 算法
一、 经典法 int a,b,c; //先定义变量 printf(请输入:\n); scanf(%d%d,&a,&b); //输入两个整型数字 if(a<b) { c=a; a=b; b=c; //保证a≥b } int i = 0; for(i = b;i>0;i--) { if(a%i == 0 && b%i == 0) ...

c语言排序(快速排序,冒泡排序,选择排序,插入排序,桶排序)

发布时间:2022-11-20 基础算法 算法 排序算法 C语言
快速排序,冒泡排序,选择排序,插入排序,桶排序 什么是排序 排序其实就是把一组没有大小顺序的数据,排列成有大小顺序的一组数据。 例子: 学校发的成绩单排名 从矮到高排队 快速排序 快速排序,顾名思义,对比冒泡排序与其他的一些排序,它的速度是很快的。这个排序,是基与分治法思想的排序方法。 基本思想: 在无序的一组数据中,寻找一个基准值。把这组数据中,小于基准值的所有数放到它的左边,大于基准值的所有数放到它的右边。 实现流程 (1)寻找一个基准数:(一般为第一个数,理论上这个数可以是任...

基础算法用golang实现(部分用C++)

发布时间:2022-12-03 开发语言 基础算法 算法 GOLANG
1. 快速排序 分治思想 quicksort(A []int, _start, _end int) 双向指针分别开工,右边(从_end开始)找到比(base指针)baseValue大的值,覆盖左边,然后左边(从_start开始)找到比baseValue大的值,覆盖右边,左右指针重合时,本轮结束,basevalue放在左右指针重合处 分治用递归实现 base指针左边都比baseValue小,因此左边再次排序 quicksort(A,_start,start-1) base指针左边都比baseValue大,因...

6KMP6

发布时间:2022-11-23 基础算法 算法
【作用】maybe 在一个已知字符串中查找子串的位置,用于字符串查找与匹配 模板题 KMP字符串 【暴力匹配算法】 1.指针i,j 分别从0开始遍历字符串s和子串p,然后比较s[i]和p[j] 2.如果s[i]==p[j],说明匹配成功,i++,j++,匹配下一位 3.如果s[i] ! =p[j],说明失配,则令i=i-j+1,j=0,重新开始匹配 4.此时时间复杂度为 log (m*n) 【分析】 所以KMP就是对以上的优化…… 1.一些概念 前缀和后缀 对于一个字符串 abcabb  前缀 : a...

Prime 求最小生成树(C++基础算法)

发布时间:2022-11-23 算法 C++语法 C++ 开发语言 基础算法
题目条件: 给定一个  个点  条边的无向图图中可能存在重边和自环,边权可能为负数。 最小生成树:通过所给的边,将所有节点相连接,并且没有自环。 题目要求返回最小生成树边权之和。 算法流程: 1> 初始化:定义邻接矩阵  存储边和权重, 为 节点到集合的距离(集合含义:构成最小生成树的节点所构成的点集,该集合在遍历节点过程中逐渐将节点添加到集合中。) memset(g,0x3f,sizeof g);memset(dist,0x3f,sizeof dist);dist[1] = 0; 最开始时候,可以...

基础算法之快排、归并、二分

发布时间:2022-11-06 基础算法 算法 排序算法
一、快速排序 快速排序基于分治思想,时间复杂度(nlogn) 快排的步骤: 确定分界点:q[left]、q[(left + right) / 2]、q[right] 三个其中一个都行调整(划分)区间(快排的重点):把小于pivot的放在左区间,大于pivot的放在右区间递归处理左右两个区间算法思想: 在区间左右两端定义i和j两个指针,假设pivot为x,当i下标对应的元素小于x时i++,当i下标对应的元素不小于x时i不变,则开始移动j,当j下标对应的元素大于x时j--,当j下标对应的元素不大于x时j不变,...

归并排序求逆序对(C++基础算法)

发布时间:2022-10-31 C++ 基础算法 算法 排序算法
逆序对: 给定一个长度为 的整数数列,请你计算数列中的逆序对的数量。 逆序对的定义如下:对于数列的第 个和第 个元素,如果满足 且 ,则其为一个逆序对;否则不是。 输入格式 第一行包含整数,表示数列的长度。 第二行包含  个整数,表示整个数列。 输出格式 输出一个整数,表示逆序对的个数。 数据范围 , 数列中的元素的取值范围。 输入样例: 62 3 4 5 6 1 输出样例: 5  逆序对: { 2, 1 } 、 { 3, 1 } 、{ 4, 1 } 、{ 5, 1 }、 { 6, 1 } 归并排序是利用...

C++继承和派生(C++语法基础)

发布时间:2022-11-22 算法 C++ C++语法 开发语言 基础算法
继承与派生 如果头一次听到这个名字的话,就先要想想这两个词的意思了。先来说继承,这与现实生活中的继承意思差不多,比如一个人继承另一个人的财产、以及子承父业等等是一个意思,拥有的这个过程就叫做继承。同样,在C++中,比如有两个类,新类拥有原有类的全部属性叫做继承!原有类产生新类的过程叫做派生!而我们把原有的这个类称之为父类或基类,由基类派生出的类叫做派生类或者叫做子类。大家从名字上就可以看出他们的关系。 那么继承和派生有什么好处呢?为什么C++要有这种机制呢? 1. 体现面向对象的编程思想,更好的表达各类...

【数据结构】DFG——n皇后问题

发布时间:2022-11-12 C++ 数据结构 算法 基础算法
n皇后问题 Subject:n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n,请你输出所有的满足条件的棋子摆法。输出格式:每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后,输出一个空行。注意:行末不能有多余空格。输出方案的顺序任意,只要不重复且没有遗漏即可。 Steps:1...