AgCl_LHY的博客

原创 使用CUDA实现的积分图/二维前缀和计算

使用CUDA实现的积分图计算，在Intel i9, RTX4090上运行，未使用stream流的情况下，可以做到单通道1080P单帧处理0.874ms，改写自NVIDIA官方库cuda-samples中的shfl_scan，其使用shfl操作实现了scan，或者说前缀和/累积和的计算。shfl_scan中有二维前缀和计算的例子，在二维层面通常称为积分图integral image或总和面积表summed area table。

原创 导向滤波 Guided Filter 的 CUDA GPU版本

导向滤波/引导滤波的一种GPU实现，经测试，在i9, RTX4090上运行，包括malloc和memcpy操作，**1080P单帧处理可以达到9.8ms**，可以直接或经过Resize缩放后加入到实时视觉任务中

原创 Keras预训练模型转Pytorch

Weights_Keras_2_Pytorch最近想在Pytorch项目里使用一下谷歌的NIMA，但是发现没有预训练好的pytorch权重，于是整理了一下将Keras预训练权重转为Pytorch的代码，目前是支持Keras的Conv2D, Dense, DepthwiseConv2D, BatchNormlization的转换。需要注意的是在Pytorch模型内需要给每一层命名为与Keras每一层相同的名字，才能对应转换。代码地址：https://github.com/AgCl-LHY/Weights

原创 六步实现课程倍速播放

中间的js代码：document.getElementById('video_html5_api').playbackRate=16

原创 算法分析与设计——图的M着色问题

文章目录一、问题二、解析三、设计四、分析五、代码一、问题给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色。如果要求G的每条边的两个顶点着不同颜色。给出所有可能的着色方案；如果不存在，则回答“NO”二、解析三、设计四、分析五、代码#include<iostream>#include<vector>#include<cmath>#include<time.h>#include<cstring>#in

原创 算法分析与设计——哈夫曼树

文章目录一、问题二、解析三、设计四、分析五、代码一、问题二、解析哈夫曼树构造：根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.在F中删除这两棵树,同时将新的二叉树加入F中.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)三、设计void SetHuffTree

原创 算法分析与设计——过载问题（0-1背包）

文章目录一、问题二、解析三、设计四、分析五、代码一、问题二、解析有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有一件。令dp[i][j]来表示前i件物品装入容量为j的背包所能得到的最大总价值。对于dp[i][j]来说，i指的是前i件物品，j指的是还剩下多少背包空间。对于一件物品，我们有放进或者不放进背包两种选择：假如我们放进背包，f[i][j] = f[i - 1][j - weight

原创 算法分析与设计——矩阵链乘法

文章目录一、问题二、解析三、设计四、分析五、代码一、问题二、解析三、设计设A[i][j] 为 ∏jk = ia[k]设cnt[i][j]为A[i][j]的最少运算次数cnt[i][j] = min(cnt[i][k] + cnt[k + 1][j] + p[i - 1] * p[k] * p[j]) for (int len = 2; len <= n; ++len) { for (int i = 1; i + len - 1 <= n; ++i

原创 算法分析与设计——字符串编辑距离问题

文章目录一、问题二、解析三、设计四、分析五、代码一、问题给定一个源串和目标串，能够对源串进行如下操作：在任意位置上插入一个字符；替换任意字符；删除任意字符。写一个程序，实现返回最小操作次数，使得对源串进行上述这些操作后等于目标串（源串和目标串的长度都小于2000）二、解析假设目标串为s1，源串为s2，如果把源串s2的每个字符一个个对照目标串s1进行操作拟合，若 认 为s1的第i个字符为s1[i],s2的第j个字符为s2[j]，那么随着i和j的分别推移，可以把思路分成以下几种情

原创 算法分析与设计——LCS最长公共子串问题和完全背包问题

文章目录一、问题二、解析三、设计四、分析五、代码一、问题LCS（最长公共子序列问题）：给定序列X=<x1,x2,…，xm>, Y=<y1,y2,…，yj>,求X和Y的最长公共子序列基础背包问题：一个旅行者随身携带一个背包，可以放入n种物品，其中物品j的重量和价值分别是wj，vj，j=1，2，…，n，如果背包最大重量限制是b，怎么选择放入背包的物品使得背包的价值最大？二、解析LCS（最长公共子序列问题）：综上，状态转移方程如下：如果xi=yi，c[i][j] c[i

原创 算法分析与设计——投资问题（动态规划）

文章目录一、问题二、解析三、设计四、分析五、代码一、问题设有m万元，n项投资，函数f（x）表示将x万元投入第i项项目所产生的效益，i=1，2，3……，n，问：如何分配这m元钱，使得投资总效益最高？即：目标函数max{f1(x1)+ f2(x2)+…+ fn(xn)},约束条件x1+x2+…+xn=m，x∈N实例：二、解析设dp[i][t]为前i个项目总共花费t元能得到的最大收益，那么假设分配给第i个项目k元取得了最大收益，则实际上前i-1个项目共得到了j=t-k元，所以dp[i][t]的最

原创 算法分析与设计——选第k小的数

文章目录一、问题二、解析三、设计四、分析五、代码一、问题设L是n个元素的集合，从L中选取第k小的元素，即L按从小到大排序之后，排在第k个位置的元素，其中1<=k<=n，二、解析随意取一个子分治过程如下：假设m*表示当前集合中从小到大排列的中位数，|s| 表示s集合中的元素个数，则：若k=|s1|+1，那么此时的m*（即中位数）就是要找的第k小的数，因为按照m划分之后，比m小的有|s1|个，如果恰巧k=|s1|+1，则m*就是要找的第k小的数；若k<=|s1|，则说明第k小

原创 算法分析与设计——最近点对问题分治算法

文章目录一、问题二、解析三、设计四、分析五、代码一、问题最近点对问题要求在一个包含n个点的集合中，找出距离最近的两个点，本题只考虑二维平面上的最近点对问题。二、解析假设点在二维平面上以笛卡尔直角坐标系给出坐标pi(xi,yi)，那么两点间的距离是标准欧几里得距离，即d(pi,pj)=sqrt((xi-xj)2+(yi-yj)2)；最直接的思路是暴力求解所有点对之间的距离，找出最小的那一对，当然d(pi,pj)= d(pj,pi)，而且平方根函数是单调增的，所以我们可以只计算i<j的那部分点

原创 算法分析与设计——二分归并算法

文章目录一、问题二、解析三、设计四、分析五、代码一、问题二分归并排序：对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k二、解析二分归并排序是一种很经典的分治思想的排序算法，过程可以分为二分分解和归并两个过程：二分：为了让一个长序列有序，可以将长序列从中间拆分成两个子序列，让两个子序列有序，两个子序列又可以单独看成一个长序列，每个都可以继续分成两个子序列，以此类推，不断用同一个规则缩小子序列的长度，直到最后子序列只有两个数时进行比较排序，使其有序；归并：回溯上一个拆分的过程，把有序的

原创 算法分析与设计——线性检索和二分检索算法

文章目录一、问题二、解析三、设计四、分析五、代码一、问题写出两种检索算法：在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0.二、解析因为条件给出的是有序数组，所以检索思路相对清晰；第一种方法可以暴力检索，以线性的思路根据下标增长从头到尾搜索一遍，找到x即输出下标；第二种方法是二分查找，因为数组有序，所以根据大小进行二分比较是可行的。三、设计方法一：从下标0开始遍历数组，不断对比当前下标对应的值和需要找的x，若有则输出下标j，没有则最后输出

原创 算法分析与设计——任意两点间最短路Floyd算法

文章目录一、问题二、解析三、设计四、分析五、代码一、问题用Floyd算法求解下图各个顶点的最短距离，给出距离矩阵（顶点之间的最短距离矩阵）二、解析要求得任意两点之间的最短路，可以采用松弛操作，对在i和j之间的所有其他点进行一次松弛，即访问从i到j的所有可能路径，把i到经过若干个编号不超过k的点再到j的多种路径做对比，更短的路径保留。这本质上是一种动态规划，把从i到j的最短路问题分成：i经过编号不超过k-1的节点到j，以及i先到k再到j，两个子问题。这样k不断加大，就可以不断的通过子问题找到

原创 算法分析与设计——单源正权最短路Dijkstra算法

文章目录一、问题二、解析三、设计四、分析五、代码一、问题对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。二、解析由顶点a到顶点h可以看出这是在一个有向图内从一个固定源点出发，找到其他任意一点的最短距离的问题，即单源最短路问题。可以把a到h的各个顶点映射成1-8的编号，（x, y, z）表示从x出发到y的距离是z的边。维护一个记录a到任意一点i的最短路径的数组，初始默认都是无穷远。从a点开始，找到它出边到达的点中离a最近的一个点x去访问，并标记x，再以此从x点往它的出边到达的

原创 算法分析与设计——最小生成树Kruskal算法

文章目录一、问题二、解析三、设计四、分析五、实例六、代码一、问题给定一张带边权的无向图G=(V,E)，n=|V|，m=|E|。由V中全部n个顶点和E中n-1条边构成的无向连通子图被称为一颗生成树，而其中边权之和最小的生成树则是该无向图G的最小生成树，应该如何得到一张图G的最小生成树？二、解析首先，任意一颗最小生成树一定包含无向图中权值最小的边。否则通过反证法，最小生成树不含权值最小的边，则可以把这条最小边加到树上，n点n条边必定会构成一个环，把该环上任意另一条边去掉，剩下的仍是联通的生成树，且树

原创 算法分析与设计——最小生成树Prim算法

文章目录一、问题二、解析三、设计四、分析五、实例六、代码一、问题给定一张带边权的无向图G=(V,E)，n=|V|，m=|E|。由V中全部n个顶点和E中n-1条边构成的无向连通子图被称为一颗生成树，而其中边权之和最小的生成树则是该无向图G的最小生成树，应该如何得到一张图G的最小生成树？二、解析首先，任意一颗最小生成树一定包含无向图中权值最小的边。否则通过反证法，最小生成树不含权值最小的边，则可以把这条最小边加到树上，n点n条边必定会构成一个环，把该环上任意另一条边去掉，剩下的仍是联通的生成树，且树

原创 求最大公约数——欧几里德算法（辗转相除）

原创 裴蜀定理的简单证明

原创 欧拉定理&费马小定理&扩展欧拉定理（证明）

原创 扩展欧几里得算法的原理及其代码实现

引例：求满足ax+by+c=0的x的最小正整数解;扩展欧几里德给出的结论是：给定a,b,则一定存在整数x,y，使得ax+by=gcd(a,b);证明可以在看完引例求解之后随便找一篇讲证明的文章就能看懂，因为思路是一致的，是引例求解思路的逆用，用数学归纳法证明，这里不赘述；引例求解思路：代码实现：细节都在注释里了，上面理解了看完注释应该可以理解代码的写法//扩展欧几里德，给定a,b,则一定存在整数x,y，使得ax+by=gcd(a,b);可以用于二元一次方程求整数解//整个过程是，先得到了题

原创 得到互质数的个数——轻松认识欧拉函数

欧拉函数用来求 在小于x的正整数且与x互质（公约数只有1）的数的个数，一般用φ(x)表示，这个φ(x)就是欧拉函数，也就是用来解决 “在1-x之间有多少个数与x构成互质关系”的问题通式：特别的，φ(1)=1，∏ 是直积符号，表示连乘其中p1,p2…pi…pn为x的所有质因数，x是一个正整数证明：根据唯一分解定理，我们可以把一个整数唯一地分解为多个质数幂次的乘积，即找其中的特殊情况（或者理解成取出连乘因子中的其中一个也是满足唯一分解定理的形式），也就是一个数可以分解成一个质数的幂次的特殊情况，

原创 查找字符串子串——逐步理解字符串Hash算法

引出字符串hash一般应用在字符串匹配问题：给定一个长度为n的s串，以及一个长度为m的t串，求t串在s串出现的次数或者位置。因为查询整数有很多技巧，比字符串要快和丰富（比如二分），所以字符串hash的思路就是利用特殊的公式将一个字符串与一个整数对应，并且尽量保证互相唯一对应，这样只要查到对应的整数出现了，就表明字符串出现了，这对应整数叫字符串的hash值。有许多种构建字符串和整数对应公式的办法，通常情况下字符串很容易只对应一个整数，但是反过来很可能有一个整数对应了多个字符串的情况，这种不唯一对应的情况

原创 区间问题1——从零开始引出树状数组

首先要明确的是，树状数组和线段树都是用来解决规模相对较大的区间问题的，区间问题就是，给一串数据，他们都属于一个范围内，我们需要从这个大的范围内找到一个更小的范围，去查询，修改或者计算给出的数据在这个小范围内的相关信息（最大最小值，和等等）。例如：给出一个数列，让你求出该数列中第x项到第y项（x<y）之间的最小值，给某个数加上a，或者求x项到y项的和。简单的思路有两个：最暴力的方法自然是全部存入一个数组，然后根据下标来做到需要做的事：假设数列有n个数，如果是需要修改某个值，那只需要找到对应的

原创 线性的质数判断——欧拉筛法

素数本身这个概念很简单，要找因子只有1和它本身的数，最简单的求法就是1到根号n遍历判断因子如果要遍历1到n的话，复杂度是O(n3/2)，处理小规模的数据没问题，但是大规模就会比较慢。当然如果只要判断一个数，那直接用这个也很快；还能更快吗？蒋委员长说过一句名言：以空间换时间，这句话在历史上被人臭骂，但是在计算机领域确实是个很不错的思想，因为大部分情况时间复杂度比空间要宝贵的多。那么这里就有一种以空间换时间的方法，叫筛法；筛法的基础思想就是当我们遍历从2开始的数时，每遍历一个，把它的倍数全部标记了，

原创 O(n)解决查找回文串问题——马拉车manacher算法

通常的思路：按照字符串顺序选取一个字符作为中心，向两边遍历判断是否相同，时间复杂度O(n^2) ;Manacher的方法能在这个通常思路的基础上进行一些修改， 从而将时间复杂度降到O(n)。本篇文章是边学边写的，将每一个结论推导的背后原理尽力的说明了，有些文章直接给出了结论，我自己在学习的时候就纠结了很久这个公式为什么可以这么写。当然后文有结论总结，不想深入理解的或者只是复习的，可以直接记结论然后直接用，一般也是当作模板用的。简单介绍思路：基础思路是以一个字符为中心向两遍拓展判断是否相同，然后记录最

原创 带路径压缩的并查集

如字面理解，并是合并，查是可查，也就是这种构建方法可以很轻易的实现合并和查找几个元素是否属于同一个集合。原理如下：首先有若干个元素，每个元素之间可能存在着两两之间的直接联系，也可能存在间接联系，但只要存在联系就属于同一个集合。这可以形象化的理解为族谱/联盟，每个元素可能是另一个元素的祖先/首领（直接联系），也可能是另一个元素的隔代祖先/首领的首领（间接联系），但他们都属于一个家族/联盟，当然两个元素可能没有任何直接或间接的关系，即属于不同的集合。而并查集的目的，就是为了高效建立和区分这些元素之间的所属

原创 HZNUOJ 1601 方阵填数

HZNUOJ 1601 方阵填数（蛇形填法）题目描述Description在一个N x N的方阵中，填入1，2，……N，共N x N（N≤10）个数，并要求构成如下的格式：例：N=513 14 15 16 112 23 24 17 211 22 25 18 310 21 20 19 4 9 8 7 6 5N=616 17 18 19 20 115 30 31 32 21 214 29 36 33 22 313 28 35 34 23

原创 HZNUOJ 2003 矩阵乘法

HZNUOJ 2003 矩阵乘法题目描述解题思路和注意点本题是个简单的练习多层for循环以及二维数组读写的题目，难度不大，只需要运用线性代数中简单的矩阵乘法原理构建出结果的二维数组即可，需要注意的主要是输出的格式，以及C矩阵的大小是n*k，步骤如下：读取题目所给的两个矩阵A和B ，用两个两层for循环实现即可；定义出结果矩阵C，并初始化其中的值为0，以便后续的计算；运用3层循环实现对矩阵C中各个位置的求值；输出求得的矩阵C，输出注意换行和空格；矩阵乘法的代码实现原理在矩阵C中，C [