算法 - 技术教程文章

Manacher算法【代码】【图】

求回文子串 O(n) manacher 算法注:此处引用他人的文章题目:解答:publicclass LongestPalindromicSubstring {public String longestPalindrome(String s) {StringBuilder sb = new StringBuilder(s); int[] p = newint[2*s.length()+3]; //p数组用来保存每个字符的回文半径sb.insert(0, ‘?‘); //这里在开头和结尾设置两个不同的字符,是为了向两边扫描的时候设置字符对比结束,sb最终结果为(?#...#!)for(int i=0;i<=s.length()...

贪心算法【代码】

1 贪心算法1.1 简介贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。也就是说,不从整体最优上加以考虑,做出的只是在某种意义上的局部最优解。注意 贪心算法不是对所有问题都能得到整体最优解1.2 分配问题455. 分发饼干(Easy)分析每个孩子按照胃口的大小从小到大依...

区间贪心算法 结合优先队列使用效果更佳——以POJ 2376、1328、3190为例【代码】【图】

贪心算法题目很多本质上都是区间贪心,这次就主要讨论以区间为载体进行的贪心算法。目录POJ 2376: Cleaning Shifts题目DescriptionInputOutputSample InputSample OutputHint题解题目大意思路代码POJ 1328: Radar Installation题目DescriptionInputOutputSample Input:Sample Output题解题目大意思路代码POJ 3190: Stall Reservations题目DescriptionInputOutputSample InputSample OutputHint题解题目大意思路代码 我们以POJ上的这...

Cookie中存放数据l加密解密的算法【代码】

public class CookieUtil {/*** * @param response HttpServletResponse类型的响应* @param cookie 要设置httpOnly的cookie对象*/public static void addHttpOnlyCookie(HttpServletResponse response,Cookie cookie) {// 判断对象是否存在null的情况if (checkObjIsNull(response) || checkObjIsNull(cookie)) {return;}//依次取得cookie中的名称、值、最大生存时间、路径、域和是否为安全协议信息String cookieName = cookie.getN...

关于删除数组任意数值的算法【代码】

Array.prototype.indexNew =function(val){ for(var i=0;i<this.length;i++){ if(this[i]== val){ return i; } } return -1;};//在数组的原型对象上添加了indexNew方法,主要用来查找传入的数值是否存在于数组中。如果存在就返回该数值,不存在则返回-1Array.prototype.remove = function(val){ var index = this.indexNew(val); if(index > -1){ this.splice(index,1); }};//数...

TextRank算法提取关键词的Java实现【代码】【图】

谈起自动摘要算法,常见的并且最易实现的当属TF-IDF,但是感觉TF-IDF效果一般,不如TextRank好。TextRank是在 Google的PageRank算法启发下,针对文本里的句子设计的权重算法,目标是自动摘要。它利用投票的原理,让每一个单词给它的邻居(术语称窗口) 投赞成票,票的权重取决于自己的票数。这是一个“先有鸡还是先有蛋”的悖论,PageRank采用矩阵迭代收敛的方式解决了这个悖论。TextRank也 不例外:PageRank的计算公式: 650) thi...

第15章动态规划------算法导论【代码】

15.1钢条切割#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<ctime> #include<string> using namespace std; int p[1000]{ 0,1,5,8,9,10,17,17,20,24,30 };//钢条价格。长度i的价格为p[i] int ordinary(int *p, int n)//递归法 {if (n == 0)return 0;else{int q = -1;for (int i = 1; i <= n; ++i){q = max(p[i] + ordinary(p, n - i), q);}return q;} } int top_down_memory(int *p, int n)/...

从分治算法到 MapReduce【代码】【图】

从分治算法说起要说 MapReduce 就不得不说分治算法,而分治算法其实说白了,就是四个字 分而治之 。其实就是将一个复杂的问题分解成多组相同或类似的子问题,对这些子问题再分,然后再分。直到最后的子问题可以简单得求解。要具体介绍分治算法,那就不得不说一个很经典的排序算法 -- 归并排序。这里不说它的具体算法代码,只说明它的主要思想。而归并排序的思想正是分治思想。归并排序采用递归的方式,每次都将一个数组分解成更小的...

python数据结构与算法第七天【链表】【图】

1.链表的定义如图:注意:(1)线性表包括顺序表和链表(2)顺序表是将元素顺序地存放在一块连续的存储区里(3)链表是将元素存放在通过链构造的存储快中 原文:https://www.cnblogs.com/liuzhiqaingxyz/p/9439814.html

算法导论——拓扑排序【代码】

package org.loda.graph;import org.loda.structure.Stack; import org.loda.util.In;/*** * @ClassName: Topological * @Description: 拓扑排序是所有节点dfs的逆后序,也就是每个节点任务完成的时间的逆序排序 * @author minjun * @date 2015年5月24日 下午7:17:53 **/ public class Topological {/*** 由于拓扑排序是df获取所有节点的逆后序排序* 这里利用Stack后序存储元素,那么获取出来就是反向(逆)后序排列的拓顺序*/...

分类与监督学习,朴素贝叶斯分类算法【图】

1.理解分类与监督学习、聚类与无监督学习。简述分类与聚类的联系与区别。简述什么是监督学习与无监督学习。 分类与聚类都是分开几类,分类是根据历史经验,已知类别,监督学习,聚类是自己分析现有数据,无监督学习监督学习利用历史数据分类,把已有数据代入。无监督学习是没有样本,将已有数据分类2.朴素贝叶斯分类算法 实例利用关于心脏病患者的临床历史数据集,建立朴素贝叶斯心脏病分类模型。有六个分类变量(分类因子):性别,...

【LeetCode-面试算法经典-Java实现】【070-Set Matrix Zeroes(矩阵置零)】【代码】【图】

【070-Set Matrix Zeroes(矩阵置零)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题  Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. 题目大意  给定一个m*n的矩阵,如果某个位置是0。将对应的行和列设置为0。 解题思路  先对矩阵进行扫描,标记要进行置0的行和列,对要进行置0的行在第0列上进行标记,对置0的列在第0行上进行标标记。同时还要两变量记录...

冒泡排序算法与选择排序算法【代码】

1数组高级以及Arrays(掌握)2 (1)排序3 A:冒泡排序4 相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处。同理,其他的元素就可以排好。5 6publicstaticvoid bubbleSort(int[] arr) {7for(int x=0; x<arr.length-1; x++) {8for(int y=0; y<arr.length-1-x; y++) {9if(arr[y] > arr[y+1]) {10int temp = arr[y];11 arr[y] = arr[y+1];12 ...

opencv2对读书笔记——使用均值漂移算法查找物体【图】

一些小概念1.反投影直方图的结果是一个概率映射,体现了已知图像内容出如今图像中特定位置的概率。2.概率映射能够找到最初的位置,从最初的位置開始而且迭代移动,便能够找到精确的位置,这就是均值漂移算法做的事情。3.均值漂移算法是以迭代的方式锁定函数的局部最大值的。关于均值漂移算法的过程(opencv)事实上均值漂移算法就是寻找提前定义寻找区域中数据点的重心,或者说加权平均值。将寻找区域中心移动到数据点的重心处,并反...

数据结构 算法【代码】【图】

#include<iostream> usingnamespace std;/* 算法算法概念 算法是特定问题求解步骤的描述 在计算机中表现为指令的有限序列 算法是独立存在的一种解决问题的方法和思想。 对于算法而言,语言并不重要,重要的是思想。算法和数据结构区别 数据结构只是静态的描述了数据元素之间的关系 高效的程序需要在数据结构的基础上设计和选择算法 程序=数据结构+算法总结: 算法是为了解决实际问题而设计的 数据结构是算法需要处理的问题载体 数据...

HDU 2255 KM算法 二分图最大权值匹配【代码】

奔小康赚大钱Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10760 Accepted Submission(s): 4765Problem Description传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须...

堆排序算法【代码】【图】

一、堆排序算法的基本特性时间复杂度:O(n*lgn)最坏:O(n*lgn)空间复杂度:O(1)不稳定。堆排序是一种选择排序算法,与关键字的初始排列次序无关,即就是在最好,最坏,一般的情况下排序时间复杂度不变。对包含n个数的输入数组,平均时间为O(nlgn),最坏情况(已经排好序)也是是O(nlgn),最好情况(完全无序)也是O(nlgn)。由于不但时间复杂度少,而且空间复杂度也是最少的,所以是用于排序的最佳选择。因为,基于比较...

JAVA的六大经典算法,代码案例简化分析【图】

java八大经典算法:冒泡、选择、快速、插入、希尔、堆、归并、基数1.算法实现类package com.algorithm;/*** * @Title: BubbleSort.java* @Copyright: Copyright (c) 2005* @Description: <br>* <br>* JAVA六大经典算法<br>* 冒泡、选择、快速、插入、希尔、堆* @Created on 2015年6月29日 下午12:48:14* @author yangkai*/ public class AlgorithmClassic {/*** 冒泡排序* * @return*/public static i...

KPM算法初步理解

一个字符串“FBCABCDABABCDABCDABYW”中是否包含另外一个字符串“ABCDABY”?  上面这道题目是一个经典的字符串匹配的题目,对于字符串匹配,比较好的算法里很容易想到KPM算法,那KPM算法是干什么的?为什么说KPM比较优秀? 给定一个字符串O和F,长度分别是m、n,判断F是否在O中出现,如果出现则返回出现的位置。常规方法是遍历O的每一个字符,与F的每一个字符进行比较,但是这种方法的时间复杂度是T(m*n),但是KPM算法使得时...

关于SVM数学细节逻辑的个人理解(三) :SMO算法理解【图】

第三部分:SMO算法的个人理解 接下来的这部分我觉得是最难理解的?而且计算也是最难得,就是SMO算法。SMO算法就是帮助我们求解:s.t. 这个优化问题的。虽然这个优化问题只剩下了α这一个变量,但是别忘了α是一个向量,有m个αi等着我们去优化,所以还是很麻烦,所以大神提出了SMO算法来解决这个优化问题。关于SMO最好的资料还是论文《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machi...

算法笔记之归并排序

4、归并排序4.1算法思想——将数组分为两半,对每部分递归地应用归并排序,直到最后的子数组只包含一个元素。在每部分都排好序后,对它们进行合并。4.2 时间复杂度——假如用T(n)表示使用归并排序对n个元素构成的数组进行排序而使用的时间,用mergeTime来表示将两个子分组合并起来而花费的时间。那么T(n)= T(n/2)+T(n/2) + mergetime而megeTime就是归并两个子数组所耗费的时间,以最大时间来算,最多需要n-1次来比较两个子数组...

图像锐化算法(Image sharpening):拉普拉斯增强和Unsharp Masking(附代码)【代码】【图】

图像锐化算法(Image sharpening):拉普拉斯增强和Unsharp Masking(附代码)\(y(m,n)=x(m,n)+\lambda*z(m,n)\) 其中\(x(m,n)\)是处理前图片,\(y(m,n)\)是锐化后,\(z(m,n)\)代表增强图像的边缘和细节(高频部分),\(\lambda\)是增强因子,如下图所示:1.laplacian 增强def laplacianSharpen(im, alpha):k = np.array([[0, 0, 0, ], [0, 1, 0], [0, 0, 0]])+alpha * np.array([[0, -1, 0], [-1, 4, -1], [0, -1, 0]])# k = np.arra...

Java算法

我们常见的排序分为以下几类:插入排序(直接插入排序,希尔排序)交换排序(冒泡排序,快速排序)选择排序(直接选择排序,堆排序)归并排序分配排序(箱排序,基数排序)  对于以上的排序有什么不同呢?  需要的辅助空间组多的:归并排序, 需要的辅助空间最小的:堆排序,平均速度最快的:快速排序时间复杂度:O(nlogn): 快速排序, 堆排序, 归并排序O(n2): 直接插入排序, 冒泡排序, 直接选择排序O(n): 基数排序空间复杂度...

poj 1274(最大匹配,匈牙利算法,注意数据污染!)【代码】

#include<iostream> #include<cstdio> #include<cstring> usingnamespace std; int data[205][205],link[205],visit[205],count,n,m; bool dfs(int x){for(int j=1;j<=m;j++){if(data[x][j]&&!visit[j]){visit[j] = 1;if(link[j]==0||dfs(link[j])){link[j] = x;returntrue;}}}returnfalse; } void hungery(){for(int i=1;i<=n;i++){memset(visit,0,sizeof visit);if(dfs(i)){count++;}} } int main(){int i,j,p,q;while(scanf("%d...

HDU1548——A strange lift(最短路径:dijskstra算法)【代码】

A strange liftDescriptionThere is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to ...

生理周期 枚举算法问题

趁着寒假抓紧自学C++.....生理周期问题是比较简单的算法问题,运用到了 枚举 的思想。 人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为 23 天、28 天和33 天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度集中。因为三个周期的周长不同,所以通常三个周期的高峰不会落在同一天。对于每个人,我们想知道何时三个高峰落在同一天。 ...

php概率算法【代码】【图】

这是一个很经典的概率算法函数:function get_rand($proArr) { $result = ‘‘; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as $key => $proCur) { $randNum = mt_rand(1, $proSum); //抽取随机数 if ($randNum <= $proCur) { $result = $key; //得出结果 break; ...

php算法

1、首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半。思路:多少行for一次,然后在里面空格和星号for一次。123456<?phpfor($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo ‘<br/>‘;}2、冒泡排序,C里基础算法,从小到大对一组数排序。思路:这题从小到大,第一轮排最小,第二轮排第二小,第三轮排第三小,依次类推……12345678910111213<?php$arr = array(1,3,5,32...

原子变量与CAS算法【代码】【图】

上一节讨论了 volatile关键字,volatile关键字修饰的作用是不具有 "原子性" 和 "互斥性的"例如 i++ 操作 就不是一个原子性的操作,i++ 其实分为3个步骤进行 "读-改-写"int temp = i;i = i + 1;i= temp;先看一段代码:package com.java.juc;publicclass TestAtomicDemo {publicstaticvoid main(String[] args) {AtomicDemo ad = new AtomicDemo();for(int i = 0;i<10;i++){new Thread(ad).start();}} }class AtomicDemo implements ...

算法第3章作业

1.对动态规划算法的理解:动态规划算法的基本思想同分治法类似,即将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解中得到原问题的解。与分治法不同的是,这若干个子问题不是相互独立的,而是有交集的,如果用分治法的思想去解决的话,会因为重复操作而浪费时间,所以需要采用动态规划的思想。动态规划可分为四步:1.找出最优解的性质,刻画其结构特征;2.递归定义最优值;3.以自底向上的方式计算最优值;4.根...