1. 原理插入排序是顾名思义是将未进行排序的元素不断插入到已排序序列中的排序方法。如下图所示: 插入排序说白点就是在以排序的序列中找到未排序元素的位置,并将元素插入行程新的已排序序列的过程。2.排序过程及算法设计排序过程以一个实际的例子为例:设有序列{7,9,6,12,15,11},使用插入排序对上述的序列按从小到大进行排序,排序的过程可描述如下: 算法设计插入排序是将元素插入已排序序列的过程,排序过程需要将元素与已排序...
KM算法 1 #include <bits/stdc++.h>2#define N 15003#define inf 9999999994usingnamespace std;5int a[N],bs[N],nx=0,ny=0,k;6int linky[N],lx[N],ly[N],slack[N];7int visx[N],visy[N],w[N][N];8int min(int a,int b){return (a<b)?a:b;}9int find(int x){
10 visx[x]=1;
11for(int y=1;y<=ny;y++){
12if(visy[y]) continue;
13int t=lx[x]+ly[y]-w[x][y];
14if(t==0){visy[y]=1;
15if(linky[y]==-1||find(linky[y])){
16 ...
最近阅读了一篇关于观点挖掘的KDD论文(Mining and Summarizing Customer Reviews,KDD04),其挖掘算法很经典,特此做记录。 该论文要解决的问题是,识别用户评论的情感(positive or negative),并作归纳,为用户购买产品提供真实有效的参考。归纳的形式如下(以数码相机为例):
数码相机: 特征: 照片质量 Positive: 253 <用户评论的句子> Negative:...
目录JDK 初步ArrayListLinkedListVectorStackHashMapHashtableLinkedHashMapTreeMapHashSetLinkedHashSetTreeSetPriorityQueueConcurrentLinkedQueue第三方类库Apache HttpComponents Clientspring-corejettythoughtworks xstreamfastjsoncommons 组件logback日志组件cache组件附录JDK 初步ArrayList底层就是一个Object数组,初始容量为10,每当元素要超过容量时,重新创建一个更大的数组,并把原数据拷到新数组中来。ArrayList实现...
简介求最小生成树一共有两种算法,一个是就是本文所说的Kruskal算法,另一个就是Prime算法。在详细讲解Kruskal最小生成树算法之前,让我们先回顾一下什么是最小生成树。我们有一个带权值的图,我们要求找到一个所有生成树中具有最小权值的生成树。如下图所示,T是图G的生成树。但不是具有最小权值的生成树。我们可以把他们想象成一组岛屿和连接它们的可能的桥梁。当然修桥是非常昂贵和费时的,所以我们必须要知道建设什么样的桥梁去...
原创作品,可以转载,但是请标注出处地址:https://www.cnblogs.com/V1haoge/p/9104582.htmlLeetCode算法第83题(难度:简单)题目:给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。(English:Given a sorted linked list, delete all duplicates such that each element appear only once.)示例 1:输入: 1->1->2
输出: 1->2示例 2:输入: 1->1->2->3->3
输出: 1->2->3简述实现思路:这种题目涉及到链表操作,需...
1.实践题目7-3编辑距离问题2.问题描述设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离,记为d(A,B)。 对于给定的字符串A和字符串B,计算其编辑距离 d(A,B)。输入格式:第一行是字符串A,文件的第二行是字符串B。提示:字符串长度不超过2000个字符。...
深度优先搜索使用的策略是,只要与可能就在图中尽量“深入”。DFS总是对最近才发现的结点v出发边进行探索,知道该结点的所有出发边都被发现为止。一旦v的所有出发边都被发现了,搜索就回溯到v的前驱结点(v是经该结点才被发现的),来搜索该前驱结点的出发边。该过程持续知道从源结点可以到达的所有结点都被发现为止。此后若还存在未被发现的结点,则DFS将从从未被发现的结点中任选一个结点作为新的源节点,并重复同样的过程。 ...
一:背景平衡二叉树(又称AVL树)是二叉查找树的一个进化体,由于二叉查找树不是严格的O(logN),所以引入一个具有平衡概念的二叉树,它的查找速度是O(logN)。所以在学习平衡二叉树之前,读者需要了解二叉查找树的实现,具体链接:二叉查找树那么平衡是什么意思?我们要求对于一棵二叉查找树 ,它的每一个节点的左右子树高度之差不超过1。(对于树的高度的约定:空节点高度是0;叶子节点高度是1。)例如下图:如果我们的二叉查找树是...
题目:输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。 之前一直对JS实现链表理解不了,被算法大牛指点了一下豁然开朗。function ListNode(x){this.val = x;this.next = null;
}
在JS中,this.val代表当前节点的值,this.next指向下一个节点,若this.next为null(对象),则说明该节点为链表的最后一个节点。PS:把下一个节点赋值给当前对象的next属性,通过这样的方式连接。通过代码:function printListFromTailToHead(h...
高速分拣,因为相同的排序效率O(N*logN)几个订购流程更高效,因此,经常使用,再加上高速分拣思想----分而治之的方法也是非常有用的,如此多的软件公司书面采访。它包含了腾讯,微软等知名IT企业宁愿测试此,的考试如软考,考研中也经常出现高速排序的身影。总的说来,要直接默写出高速排序还是有一定难度的。因为本人就自己的理解对高速排序作了下白话解释,希望对大家理解有帮助,达到高速排序,高速搞定。 高速排序是C.R.A.Hoar...
整数线性规划求解----分枝定界法什么是整数规划?? 线性规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。整数规划的分类 - 变量全限制为整数时,称(完全)整数规划- 变量部分限制为整数时,称混合整数规划 什么是分枝定界法? 原理如下:? 设...
基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 1.设置 low=0, high=N-1。 2.选择一个基准元素赋值给temp,即temp=a[low]。 3.从high开始向前搜索,即由后开始向前搜索(high--),找到第一个小于temp的值,将a[high]和a[low]交换。 4.从...
堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性:1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总...
题目最长公共子序列分析有两个字符串S1和S2,求一个最长公共子串,即求字符串S3,它们同时是S1和S2的子串,且要求它们的长度最长,并确定这个长度。这个问题我们称之为最长公共子序列问题。
与求最长递增子序列一样,我们首先将原问题分割成一些子问题,我们用dp[i][j]表示S1中前i个字符和S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度。显然的,当i,j较小时我们可以直接给出答案,如dp[0][j] 必等于0。那么,假设我们...