本文主要介绍解决动态连通性一类问题的一种算法，使用到了一种叫做并查集的数据结构，称为Union-Find。更多的信息可以参考Algorithms 一书的Section1.5，实际上本文也就是基于它的一篇读后感吧。原文中更多的是给出一些结论，我尝试给出一些思路上的过程，即为什么要使用这个方法，而不是别的什么方法。我觉得这个可能更加有意义一些，相比于记下一些结论。 关于动态连通性我们看一张图来了解一下什么是动态连通性： 假设我们输入了一组整数对，即上图中的(4,3)(3,8)等等，每对整数代表这两个points/sites是连通的。那么随着数据的不断输入，整个图的连通性也会发生变化，从上图中可以很清晰的发现这一点。同时，对于已经处于连通状态的points/sites，直接忽略，比如上图中的(8,9)。 动态连通性的应用场景：网络连接判断：如果每个pair中的两个整数分别代表一个网络节点，那么该pair就是用来表示这两个节点是需要连通的。那么为所有的pairs建立了动态连通图后，就能够尽可能少的减少布线的需要，因为已经连通的两个节点会被直接忽略掉。变量...

【起】ACM类下为过往所做过的部分算法题目几百道题，日后细细品味。 ...

http://blog.csdn.net/w200221626/article/details/52064976C#实现Snowflake算法///<summary>///动态生产有规律的IDSnowflake算法是Twitter的工程师为实现递增而不重复的ID实现的///http://blog.csdn.net/w200221626/article/details/52064976///C#实现Snowflake算法///</summary>publicclassSnowflake{privatestaticlongmachineId;//机器IDprivatestaticlongdatacenterId=0L;//数据IDprivatestaticlongsequence=0L;//计数从零开始privatestaticlongtwepoch=687888001020L;//唯一时间随机量privatestaticlongmachineIdBits=5L;//机器码字节数privatestaticlongdatacenterIdBits=5L;//数据字节数...

#机器学习分类算法的评价指标#二分类问题的算法评价指标importnumpyasnpimportmatplotlib.pyplotaspltimportpandasaspdfromsklearnimportdatasetsd=datasets.load_digits()x=d.datay=d.target.copy()#防止原来数据改变print(len(y))y[d.target==9]=1y[d.target!=9]=0print(y)print(pd.value_counts(y))#统计各个数据出现的个数fromsklearn.model_selectionimporttrain_test_splitx_train,x_test,y_train,y_test=train_test_split(x,y,random_state=666)fromsklearn.linear_modelimportLogisticRegressionlog_reg=LogisticRegression(solver="newton-cg")#使用逻辑回归算法进行数据的分类log_reg.fit(x_...

#逻辑回归算法是一个二分类的算法，但是通过变形可以解决多分类的任务#逻辑回归将数据的特征转变为数据的发生概率，然后与阈值作比较，判断是0还是1，所以也可以叫做回归算法importnumpyasnpimportmatplotlib.pyplotasplt#定义概率转换函数sigmoid函数defsigmoid(t):return1/(1+np.exp(-t))x=np.linspace(-10,10,100)y=sigmoid(x)plt.figure()plt.plot(x,y,"r",label="Sigmoid")plt.legend(loc=2)plt.show()#定义逻辑回归算法的损失函数，与线性回归算法比较一致#逻辑回归算法的数学原理底层实现编写defJ1(theta,x_b,y):#损失函数的定义y_hat=sigmoid(x_b.dot(theta))returnnp.sum(y*np.log(y_hat)+(1-y)*np.log(1-y_hat))/len(x_b)defDJ2(theta,x_b,y):res=np.empty(len(theta))res[0]=...

顺序表的储存分为一体式结构和分离式结构，但总的来说存储数据的内存是一块连续的单元，每次申请前都要预估所需要的内存空间大小。这样就不能随意的增加我们需要的数据了。链接就是为了解决这个问题。它的数据存储方式是每插入一个数据，就在内存中申请一块存储空间来保存，那么新增加的数据如何和之前的数据保持关联呢？解决方法就是在原来的数据内存里保存新增加的数据的内存地址，这样就相当于用“一根线”把它们都串了起来，因此每次新插入一个数据，就要在内存中申请两个连续的空间，一个用来储存数据，一个用来储存下一个数据的地址。寻址方式就是从第一个数据开始依次往下寻找。（ps:图画的有点丑2333）另外，链表和顺序表统称为线性表。同时，我们需要一个内存空间，用来保存链表第一个数据的地址，因此，完整的结构应该是 了解是链表的概念后，我们就要想办法来实现它，那么，用什么方式实现呢？我们知道，链表的实现需要把数据以及所支持的结构放到一起形成一个整体，这样才构成链表。这时就要用到面向对象中类的概念了。但因为链表其中还保存数据地址这个功能，我们就先要来学习先python中有关变量地址的一点知识...

栈可以用顺序表实现，也可以用链表实现。栈的操作Stack()创建一个新的空栈push(item)添加一个新的元素item到栈顶pop()弹出栈顶元素peek()返回栈顶元素is_empty()判断栈是否为空size()返回栈的元素个数这里我们用python的list来实现栈的操作classStack(object):"""栈"""def__init__(self):self.__list=[]defis_empty(self):"""判断是否为空"""returnself.__list==[]　　　　#returnnotself.__listdefpush(self,item):"""加入元素"""self.__list.append(item)#可以选择从栈顶或栈底推入，这里我们选择从list尾部插入，时间复杂度为O(1);从头部则要改为.append(0,item)O(n)defpop(self):"""弹出元素"""returnself.__list.pop()defpeek(self):"""返回栈顶元素"""　　ifself__list:　　　　　returnself.__l...

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。根据线性表的实际存储方式，分为两种实现模型：顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。链表，将元素存放在通过链接构造起来的一系列存储块中。图a表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc(e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：Loc...

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。算法是独立存在的一种解决问题的方法和思想。对于算法而言，实现的语言并不重要，重要的是思想。算法可以有不同的语言描述实现版本（如C描述、C++描述、Python描述等），我们现在是在用Python语言进行描述实现。输入:算法具有0个或多个输入输出:算法至少有1个或多个输出有穷性:算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成确定性：算法中的每一步都有确定的含义，不会出现二义性可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成对于同一问题，我们给出了两种解决算法，在两种算法的实现中，我们对程序执行的时间进行了测算，发现两段程序执行的时间相差悬殊（214.583347秒相比于0.182897秒），由此我们可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。假设我们将第二次尝试的算法程序运行在一台配置古老性...

1.直接插入排序在插入第i个记录的时，R1,R2...已经排好序，这时将关键字R依次与R1...比较，从而找到应该插入的位置，插入位置以及其后的记录依次往后移动。时间复杂度O(n^2)    空间复杂度O(1) 2.冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个和第三个记录的关键字，以此类推，知道第n-1个记录和第n个记录比较过为止。上述为第一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置，然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果关键字次大的记录被交换到第n-1个记录的位置，最多进行n-1趟，所有的记录有序排列。时间复杂度O(n^2)    空间复杂度O(1)packagealgorithm;/***@time2019年5月19日下午12:20:59*@authorlll*@describe排序*/publicclassBubbleSort{/***@time2019年5月19日下午1:05:07*@...

用寻路算法写的一个小项目地址 https://a1115040996.github.io/arithmetic/html/寻路应用.html 没来得及仔细优化，后面再优化 代码如下<!DOCTYPEhtml><html><head><metacharset="UTF-8"><title></title><linkrel="stylesheet"type="text/css"href="../css/way-finding.css"/></head><body><ulid="ul-table"></ul><scriptsrc="../js/plugin/jquery-2.1.0.js"type="text/javascript"charset="utf-8"></script><scripttype="text/javascript">/****************************...

https://www.qbitai.com/2020/03/12245.htmlAlphaGo战胜了人类最强棋手，但前提是它先学会了人类棋谱，离不开人类指导。接着谷歌又推出了AlphaGoZero，只让AI知道围棋规则，从零开始学下棋，结果再次登上棋艺顶峰。AI既然能从零学习围棋，是否可以从零开始摸索机器学习算法？当然可以，谷歌大脑团队最新的研究成果已经做到了。谷歌将这种技术称之为AutoML-Zero，意为“从零开始的自动机器学习”，已经在GitHub开源，并在Arxiv上提交了论文。而且这一研究还是来自谷歌大脑的QuocV.Le大神之手。AutoML-Zero仅使用基本数学运算为基础，从一段空程序开始，即可自动发现解决机器学习任务的计算机程序。AutoML是一种实现从数据集到机器学习模型的自动化方法，让你无需高深专业知识，就能自动部署ML模型。虽说是自动，但现阶段的AutoML还要对搜索空间进行很大的限制，这使我们在使用AutoML的时候仍然需要一些专业知识去设计神经网络的层。谷歌的目标是让AutoML可以走得更远，仅仅使用基本的数学运算作为构建块，就可以...

一，问题介绍最近一直在看贪心算法的正确性证明（如何证明贪心算法获得的解一定是最优解），感觉“剪枝”技巧用得比较多。再看了下《算法导论》中贪心算法一章里面的一个练习---找换硬币问题。这个问题对于某些面值的硬币是有最优解的，故记录下其中的一些证明思路。考虑用最少的硬币数来找n分钱的问题，假设每个硬币的值都是整数。如果可换的硬币的单位是c的幂，也就是c0，c1，...，ck,其中整数c>1，k>=1证明贪心算法总可以产生一个最优解。 二，找换硬币的贪心策略这里的贪心策略很容易想到：总是优先选择大面值的硬币去找。比如，现有1分、5分、25分的硬币可用来找钱，现在我们需要找n=32分的零钱，如何找？优先选择大面值的嘛，那就是先选25分；选完之后，还要找32-25=7，那就再选5分的，最终再先2个1分的。即可。这里：32=25+5+1+1，一共用了4枚硬币。那么，问题来了！！！还有没有其他策略只需要3枚硬币？或者更少的硬币？这就需要证明贪心策略有没有最优解了？对于这个问题而言，如果用来找换的硬币的面值满足某种性质，该贪心策略是有最优解的。这里说的某种...

一，部分背包问题介绍首先介绍下0-1背包问题。假设一共有N件物品，第i件物品的价值为Vi，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，请问：他应该选择哪些物品？0-1背包问题的特点是：对于某件（更适合的说法是：某类）物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况。而部分背包问题则是：可以带走一部分。即，部分背包问题可带走的物品是可以无限细分的。（连续与离散的区别）可以把0-1背包问题中的物品想象的一个金子，你要么把它带走，要么不带走它；而部分背包问题中的物品则是一堆金粉末，可以取任意部分的金粉末 二，部分背包问题的贪心算法部分背包问题可以用贪心算法求解，且能够得到最优解。贪心策略是什么呢？将物品按单位重量所具有的价值排序。总是优先选择单位重量下价值最大的物品。单位重量所具有的价值：Vi/Wi举个例子：假设背包可容纳50Kg的重量，物品信息如下：物品i     重量(Kg)    价值  &nb...

一，介绍分治算法主要包含两个步骤：分、治。分，就是递归地将原问题分解成小问题；治则是：在解决了各个小问题之后(各个击破之后)合并小问题的解，从而得到整个问题的解 二，分治递归表达式分治算法一般都可以写出一个递归表达式；比如经典的归并排序的递归表达式：T(N)=2T(N/2)+O(N)T(N)代表整个原问题，采用了分治解决方案后，它可以表示成：①分解成了两个规模只有原来一半(N/2)的子问题:T(N/2)②当解决完这两个子问题T(N/2)之后，再合并这两个子问题需要的代价是O(N)递归表达式的解就是该算法的时间复杂度。关于某些特定形式的递归表达式，求解时，是可以直接套公式的：T(N)=aT(N/b)+Θ(N^K)表示将原问题分解成a个规模大小为N/b的子问题，合并这a个子问题的代价是Θ(N^K) （N^k表示N的k次方）T(N)的解有以下三种情况：1)T(N)=O(N^logba)  当a>bk时2)T(N)=O(NklogN)  当a=bk时3)T(N)=O(Nk)  当a&l...