大数乘法:模拟乘法手算累加:和小学生一样竖式计算,逐位相乘,结果相加(很麻烦)改进:先不算任何进位,只保存每一位结果,最后从右到左相加int result[num1.length+num2.length]; //结果不会比俩数长度加起来还长 for(int i=0; i<num1.size(); i++) {for(int j=0; j<num2.size(); j++) { //不考虑进位,先乘了再说result[i+j+1] += num1[i] * num2[j];//+1位给最后最高位进位留空间} }//单独处理进位 for(int k = result.size()-...
LinkSolution随便状压就可以了,设f[S]为答案,g[S]为S的最大独立集点数。对于每个S,枚举其点集内每个点作为p[1],那么选了这个点之后与其相连的所有点(记作rel[i])都不能选,是个递归过程。 转移有 \(f_S=\frac{\sum\limits_{i\in S}f_{S-rel[i]}\times [g[S-rel[i]]+1==g[S]]}{|S|}\)Code原文:https://www.cnblogs.com/fruitea/p/12023944.html
该题是求两点间的最短路问题,用Dijkstra算法比较快 ,跑了0.003s 。方法很简单,将圆看成结点,直接判断两个圆是否相交,如果相交距离为0,否则距离为圆心间距离减去两圆半径。 起点和终点也可以看成是一个半径为0的圆 。这样就变成了两点间的最短路问题,适合用Dijkstra算法求解。 比较坑的是该题说了数据范围n最大100,但是我开了105竟然RE ,看成505就过了 。 所以在占用内存不多的情况下还是开大一点好 。细节参见代码:#in...
#include<iostream> usingnamespace std;/*交换排序--冒泡排序 基本思想:在要排序的一组数中,对当前还未排序的全部数,自上而下对相邻的两个数依次进行比较和调整, 让较大的数往下沉淀,较小的数往上冒对冒泡排序法的改进方法是加入一标志性变量exhange,用于标志某一趟排序中是否有数据交换,如果进行某一趟排序 没有进行数据交换,则说明数据已经按要求排列好了,可立即结束排序。//设置一标志性变量pos,用于记录每趟排序中最...
一、图像梯度算法1、图像梯度-Sobel算子 dst = cv2.Sobel(src, ddepth, dx, dy, ksize)ddepth:图像的深度dx和dy分别表示水平和竖直方向ksize是Sobel算子的大小 1# *******************图像梯度算法**********************开始 2import cv23# import numpy as np 4 5 img = cv2.imread(‘pie.png‘,cv2.IMREAD_GRAYSCALE)6 cv2.imshow("img",img)7cv2.waitKey()8cv2.destroyAllWindows()910# 显示图像函数11def cv_show(img,name):...
#include <stdio.h>#include <stdlib.h>#include <string.h>void get_next(char T[100],int *next);int Index_KMP(char S[100],char T[100],int pos);int main(){ int n; char S[100],T[100]; gets(S);//直接用字符串决定了字符数组从0开始而非1 gets(T); n=Index_KMP(S,T,2); printf("%d",n); return 0;}void get_next(char T[100],int *next){ int j,i; int t; next[0]=-1;//因为next函数定义中当...
关于字符串匹配算法有很多,之前我有讲过一篇 KMP 匹配算法:图解字符串匹配 KMP 算法,不懂 kmp 的建议看下,写的还不错,这个算法虽然很牛逼,但在实际中用的并不是特别多。至于选择哪一种字符串匹配算法,在不同的场景有不同的选择。在我们平时文档里的字符查找里采用的就是 Boyer-Moore 匹配算法了,简称BM算法。这个算法也是有一定的难度,不过今天,我选用一个例子,带大家读懂这个字符串匹配 BM 算法,看完这篇文章,保证你...
关于配对堆的一些小姿势:1、配对堆是一颗多叉树。2、包含优先队列的所有功能,可用于优化Dijkstra算法。3、属于可并堆,因此对于集合合并维护最值的问题很实用。4、速度快于一般的堆结构(左偏树,斜堆,随机堆……),具体时间复杂度:合并(Merge):$O(1)$;插入(Insert/Push):$O(1)$;修改值(Change):$O(1) \sim O(\log n)$;取出维护的最值(Top):$O(1)$;弹出堆顶元素(Pop):$O(\log n)$; 我们依然拿洛谷的P4779 【...
题目链接:https://www.acwing.com/activity/content/punch_the_clock/6/Dijkstra算法用于求解单源最短路问题。常见的技巧有:反向建图:源点为整个点击,汇点却只有单个,这时可能把边反向。分层建图:指定某些边可以使用一些特殊性质,比如可以使用一些魔法降低边的权值,但是魔法力量有限。这种问题一般魔法力量的范围不会太大,刚刚好可以把原图的每个点都拆成魔法力量的范围这么多,注意提取边的公共性质来减少边的存储。多个...
机器学习实战学习笔记(二)-KNN算法(2)-KNN算法改进约会网站的配对效果情景概要某个妹子交往过三种类型的人:不喜欢的人魅力一般的人.极具魅力的人这个妹子想要知道自己到底喜欢哪一类男人,于是提供了她收集的约会数据(1000行,吐槽一波,手动狗头),并希望能创建一种分类机制来帮她完成这件事情。数据表格如下:实际数据集是这样的:datingTestSet.txtdatingTestSet2.txt导入数据# 判断分类 def isWhichClass(className):if className...
题目:http://acm.hdu.edu.cn/showproblem.php?pid=3549模板题,白书上的代码。。。 1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <algorithm>5 #include <queue>6usingnamespace std;7 8constint INF=1<<28;9int cap[30][30],flow[30][30],n; 1011int Edmonds_Karp(int s,int t) 12{ 13int a[30],p[30]; 14int f; 15 queue<int>q; 16 memset(flow,0,sizeof(flow)); 17 f=0; 18while(1) 1...
堆结构简述 了解过数据结构的人,应该对堆结构不陌生,堆的底层是使用数组来实现的,但却保持了二叉树的特性。堆分为两种,最大堆和最小堆,以最大堆为例,最大堆保持了根结点大于两个左右两个孩子,同时所有子树一次类推。由于堆底层是数组结构,这里从跟结点开始,按照层序依次走到最后一个结点,结点下标分贝为0~N-1。结构如下图:650) this.width=650;" src="/upload/getfiles/default/2022/11/9/20221109112752756.jpg" ti...
1. SVM基本知识SVM(Support Vector Machine)是一个类分类器,能够将不同类的样本在样本空间中进行分隔,分隔使用的面叫做分隔超平面。比如对于二维样本,分布在二维平面上,此时超平面实际上是一条直线,直线上面是一类,下面是另一类。定义超平面为:f(x)=w0+wTx可以想象出,这样的直线可以有很多条,到底哪一条是超平面呢?规定超平面应该是距离两类的最近距离之和最大,因为只有这样才是最优的分类。假设超平面是w0+wTx=0,那么...
转自:http://blog.csdn.net/u012160689/article/details/15341303 余弦距离,也称为余弦相似度,是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫"余弦相似性"。上图两个向量a,b的夹角很小可以说a向量和b向量有很高的的相似性,极端情况下,a和b向量完全重合。如下图:如上图二:可以认为a和b向量是相等的,也即a,b向量代表的文本是完...
关于KMP算法的原理网上有很详细的解释,我总结一下理解它的要点: 以这张图片为例子 这里我们匹配到j=5时失效了,接下来就直接比较T[2](next[5]=2)和S[5]那为什么可以跳过朴素算法里的几次比较,而直接用T[next[j]]比较就可以呢?我们匹配过S0S1S2S3S4=T0T1T2T3T4,next[5]=2,2是公共序列的最大长度了,也就是说:T0T1=T3T4,但是T0T1T2≠T2T3T4,T0T1T2T3≠T1T2T3T4,那么就有S3S4=T3T4=T0T1,而S2S3S4=T2T3T4≠T0T1T2,S1S...