算法 - 技术教程文章
编程算法 - 快速排序(QuickSort)和二分查找(BinarySearch)【图】
快速排序(QuickSort)和二分查找(BinarySearch)本文地址: http://blog.csdn.net/caroline_wendy快速排序和二分查找的定义, 网上书上都有, 本文主要是讲解如何写出这两个经典算法.程序员必须掌握的两种算法, 使用任何语言, 使用纸都是必须的.快速排序(C):/** main.cpp** Created on: 2014年9月10日* Author: Spike*/#include <stdio.h> #include <stdlib.h> #include <iostream> #include <exception>int RandomInRange(int st...
动态规划算法之：最长公共子序列 & 最长公共子串（LCS）
1、先科普下最长公共子序列 & 最长公共子串的区别：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。2、最长公共子串其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab") b a bc 0 0 0a 0 1 0b ...
余数算法【代码】
一筐鸡蛋：1个1个拿，正好拿完。2个2个拿，还剩1个。3个3个拿，正好拿完。4个4个拿，还剩1个。5个5个拿，还剩4个。6个6个拿，还剩3个。7个7个拿，正好拿完。 8个8个拿，还剩1个。 9个9个拿，正好拿完。问筐里最少有多少鸡蛋？先简化算法：第一个条件忽略，是8的倍数一定是4的倍数，也一定是2的倍数是9的倍数一定是3的倍数，是3的倍数，而且是奇数，被6除一定余3， 所以，可以归纳为：5个5个拿，还剩4个。7个7个拿...
23、查找算法-插值法查找【代码】
来源：https://www.bilibili.com/video/BV1B4411H76f?p=77一、思路插值法查找：序列还是需要有序，思路跟二分法是一致的，但是寻找中间坐标mid的方法不同。对于二分法mid=1/2(low+high)=low+1/2*(high-low)插值法中mid的求法是这样的：mid=low+((finalVal-arr[low])/(arr[high]-arr[low]))(high-low)利用目标值finalVal的大小，大体确定一下它的位置例如：一个1-100的数组，要找1那二分法：mid = 0+1/2(99-0)=49,从49开始找插值法：...
算法：计算十进制数字在二进制表示1的个数【代码】
题目一计算十进制数字在二进制表示 1 的个数举个例子:十进制数字为 1 时，它的二进制表示是 001，二进制表示 1 的个数为 1；十进制数字为 2 时，它的二进制表示是 010，二进制表示 1 的个数为 1；十进制数字为 3 时，它的二进制表示是 011，二进制表示 1 的个数为 2；十进制数字为 4 时，它的二进制表示是 100，二进制表示 1 的个数为 1；十进制数字为 5 时，它的二进制表示是 101，二进制表示 1 的个数为 2；十进制数字为 6 时，它...
HDU 2586 How far away LCA的离线算法 Tarjan【代码】
链接:How far away ？Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11204 Accepted Submission(s): 4079Problem DescriptionThere are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily...
LinkedHashMap 和 LRU算法实现【代码】
个人觉得LinkedHashMap 存在的意义就是为了实现 LRU 算法。publicclass LinkedHashMap<K,V> extends HashMap<K,V>implements Map<K,V> {public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}....1、LinkedHashMap 的 <K,V>用HashMap存储。2、LinkedHashMap 的Key 用双向链表维护。 当用get 和 set 方法的时候，内部维护key的...
BitMap算法【代码】
一、bitmap算法思想 32位机器上，一个整形，比如int a; 在内存中占32bit位，可以用对应的32bit位对应十进制的0-31个数，bitmap算法利用这种思想处理大量数据的排序与查询. 优点：1.运算效率高，不许进行比较和移位；2.占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。 缺点：所有的数据不能重复。即不可对重复的数据进行排序和查找。 比如： 第一个4就是 000000000000000000...
感知器算法--python实现【代码】【图】
写在前面： 参考：1 《统计学习方法》第二章感知机【感知机的概念、误分类的判断】 http://pan.baidu.com/s/1hrTscza2 点到面的距离3 梯度下降4 NumPy-快速处理数据 属性shape：表示几行几列； dot(a,b) 计算数组、矩阵的乘积 感知器算法：Python实现：#coding:utf-8 import numpy as npclass Perceptron(object):def __init__(self):self.study_step = 1 #学习步长即学习率self.study_total = 11 #学习次数即...
C++泛型线性查找算法——find【代码】
C++泛型线性查找算法——find《泛型编程和STL》笔记及思考。线性查找可能是最为简单的一类查找算法了。他所作用的数据结构为一维线性的空间。这篇文章主要介绍使用 C++ 实现泛型算法 find的过程。C 版本首先介绍 C find 算法的实现，用以引入 C++ 版本。char *find1(char *first,char *last,int c) {while(first != last && *first != c)++first;return first; }该版本的算法循环检查每个元素，尾后指针(last)作为结束标识。使用举...
排序算法
一、经典冒泡法。1、初始实现：lst = [9,5,1,2,6]length = len(lst)for i in range(length): for j in range(length-1-i): if lst[j] > lst[j+1]: st[j], lst[j+1] = lst[j+1], lst[j] print(lst)2、优化实现： lst = [9,5,1,2,6]length = len(lst)for i in range(length): flag = False for j in range(length-1-i): if lst[j] > lst[j+1]: lst[j], lst[j+1] = lst[j+1],...
看到一个等差数列求和的算法，秀得我头皮发麻【代码】【图】
我下意识的反应是递归求解：1int sum(int n) 2{ 3if(n==1) return1; 4return n+sum(n-1); 5 } 跟这个比起来真的是小巫见大巫~~1int sum(int n) 2{ 3bool a[n][n+1] 4returnsizeof(a)>>1; 5 } 秀得我头皮发麻，，鬼才操作~ 原文：https://www.cnblogs.com/yinhao-ing/p/10666120.html
算法题——翻转链表中的一段【代码】
题目：给出一个链表中的两个指针p1和p2，将其之间的结点翻转。 思路：可以通过交换结点内的值来实现结点的翻转，空间为O(N)；如果要求不能交换值，那么仅凭p1和p2是无法翻转的，只能交换两个指针之间的链表。 代码：交换值： 1struct ListNode 2{3int val;4 ListNode *next;5};6 7void reverseNodes(ListNode *p1, ListNode *p2) {8if ( p1 == NULL || p2 == NULL ) 9return; 1011 vector<ListNode*> nodes; 12for(vector<...
一致性哈希算法及其在分布式系统中的应用【图】
摘要本文将会从实际应用场景出发，介绍一致性哈希算法（Consistent Hashing）及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景，借此介绍一致性哈希算法以及这个算法如何解决此问题；接下来会对这个算法进行相对详细的描述，并讨论一些如虚拟节点等与此算法应用相关的话题。分布式缓存问题假设我们有一个网站，最近发现随着流量增加，服务器压力越来越大，之前直接读写数据库的方式不太给力了，于是...
数据结构与算法问题 判断两序列是否为同一二叉搜索树序列【代码】
题目描述：判断两序列是否为同一二叉搜索树序列输入：开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。输出： 如果序列相同则输出YES，否则输出NO样例输入：2 567432 543267 576342 0样例输出...
字符串算法大全【代码】【图】
1、LCSdef lcs(a,b):lena=len(a)lenb=len(b)c=[[0 for i in range(lenb+1)] for j in range(lena+1)]flag=[[0 for i in range(lenb+1)] for j in range(lena+1)]for i in range(lena):for j in range(lenb):if a[i]==b[j]:c[i+1][j+1]=c[i][j]+1flag[i+1][j+1]=‘ok‘elif c[i+1][j]>c[i][j+1]:c[i+1][j+1]=c[i+1][j]flag[i+1][j+1]=‘left‘else:c[i+1][j+1]=c[i][j+1]flag[i+1][j+1]=‘up‘return c,flagdef printLcs(flag,a,i,j...
快速排序算法(Quicksort)【代码】
快速排序算法是对集合中元素进行排序最通用的算法，俗称快排，其算法的时间复杂度为O(nlgn)，空间复杂度为O(1)。我们举例来对其算法思路进行理解，譬如数组 A = { 4, 8, 1, 2, 9, 7, 3, 0, 5, 6 };第一步，以最后一个数6为基准，把小于等于6的数挪到数组左边，把大于6的数挪到数组右边。那么结果为 { 4, 1, 2, 3, 0, 5, 8, 9, 7, 6 }，这个时候再做一步，把8和6进行交换，得到{ 4, 1, 2, 3, 0, 5, 6, 9, 7, 8 }把6的最新位置返回。...
次小生成树的两种算法【代码】【图】
一、“换边”算法用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。可以证明：最小生成树与次小生成树之间仅有一条边不同。这样相当于运行m次Kruskal算法。复杂度O(m^2)示例代码：int Kruskal_MinTree() {int u,v;init();int i,flag,cnt;minedge = 0;flag = cnt = 0;int tmp = 0;for(i=0;i<m;i++){u = edge[i].s;v = edge[i].t;...
PHP实现各种经典算法
<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找（数组里查找某个元素） function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = intval(($low+$high)/2 ); if ($array[$mid] == $k){ return $mid; }elseif ( $k < $array[$mid]){ return bin_sch($array, $low, $mid-1, $k); }else{ ...
一些算法的实现代码【代码】
1.斐波那契数列 Fibonacci class fab{ public static void main(String args[]){ // fab(47) int 溢出 for(int i=0;i<47;i++) System.out.print(fab(i)+" "); System.out.println(); } public static int fab(int n){ if(n==0) return 0; if(n==1) return 1; int fa=0; int fb=...
算法复习——1D/1Ddp优化【代码】【图】
搬讲义~~~~题目1：玩具装箱(bzoj1010)DescriptionP教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，...
算法笔记_093:蓝桥杯练习 Problem S4: Interesting Numbers 加强版（Java）【代码】【图】
目录1 问题描述2 解决方案 1 问题描述Problem Description We call a number interesting, if and only if: 1. Its digits consists of only 0, 1, 2 and 3, and all these digits occurred at least once. 2. Inside this number, all 0s occur before any 1s, and all 2s occur before any 3s. Therefore, the smallest interesting number according to our definition is 2013. There are two more interseting nu...
PHP排序算法的复习和总结【代码】
对于PHP中对数组的元素进行排序，这个是很经常用到的，之前的项目中也有，而且对于几种排序我们都是用的是asort arsort 等PHP原生函数，没有自己去实现，所以就对一下的几个函数进行总结，这个会不断的进行补充，自己也可以好好的复习和总结。直接上代码吧！ 1 <?php2/* 3 * 插入排序（一维数组）4 * 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当的位置，使数列依然有序；直到待排序的数据元素全部插入完成...
C前序遍历二叉树Morris Traversal算法【代码】
首先来递归算法，简单易懂：#include <stdio.h> #include <stdlib.h> #include <stdbool.h>typedef struct TreeNode{char data;struct TreeNode *lchild, *rchild; }TreeNode;void PreOrderTraverse(TreeNode *t){if( NULL == t ) return;printf("%c",t->data);PreOrderTraverse(t->lchild);PreOrderTraverse(t->rchild); } 然后是栈模拟递归：typedef struct StackNode{TreeNode *pdata;struct StackNode *next; }StackNode; t...
数据结构与算法系列——排序(7)_堆排序【代码】【图】
1. 工作原理（定义） 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：每个节点的值都小于或等...
C语言之广度优先算法【代码】【图】
广度优先算法又称宽度优先搜索，是一种简便的图的搜索算法之一。搜索方式大致是这样的：直到搜索到目标节点（节点就是那些圆球球，其中有一个或者多个是目标节点）或者搜完了整个图都没找到目标节点就停止搜索。实现这个要是想用像深度优先算法那样函数套函数那样是难以实现的（至少我实现不了）。像这样的：求问从A到B的最短路径的节点数是多少？ 这道题很简单嘛，肯定是A-C-B啊，答案是3啊。那怎样用C语言实现呢？深搜的话：一条...
（算法）并查集及其应用【代码】
题目：某国家有N个小岛组成，经过多年的基础设施累积，若该岛屿之间建立若干桥梁，先重新完善该国的行政区划，规定只要有桥梁连接的岛屿则归属于同一个城市（可以通过其他岛屿中转），问该国可以划分为多少个城市？思路：并查集代码：#include<iostream> #include<set> usingnamespace std;class UnionFindSet{private:int m_nN;int* m_pParent;public:UnionFindSet(int n);~UnionFindSet();void Union(int i,int j);int Find(int ...
刷算法题学到的一些思考问题的方式（动态更新）
1、看解的性质，然后构造解，遍历所有可能的解，找出最优http://blog.csdn.net/u011026968/article/details/46282001原文：http://blog.csdn.net/u011026968/article/details/46282241
Dijkstra算法与Prim算法辨析
这两个算法真的很像，尽管它们的用处截然不同。Dijkstra是找单源非负的最短路径。Prim是找最小生成树。Dijkstra算法都是找当前标记集合点再扩一条边所形成的最短路径，然后更新标记点集，外扩路径集。Prim是找当前标记集合点再扩一条边中所形成的的最短边，然后更新标记点集，外扩边集。所以细节上是有不同的。Dijkstra复杂度O（N2）, Prim O(eloge).原文：http://www.cnblogs.com/zqiguoshang/p/6688132.html
获取数组排序后的index算法实现【代码】
需求：一个数组var arr = [4,7,2,9],排序后的新数组var newArr = [2,4,7,9]或者[9,7,4,2]我们要得到的是排序后元数组的每一项在新数组中的位置所构成的数组：[2,4,7,9]对应[1,2,0,3]/[9,7,4,2]对应[2,1,3,0]方案一： 1 Array.prototype.getIndex = function () {2var orderLength = this.length;3var temp, tp;4var c = [];5for(var l = 0; l < orderLength; l++) {6 c[l] = l;7 }8for(var u = 0; u < orderLength; u++...