SPOJ Problem Set 2. Prime Generator 求某区间质数题解

2016年07月27日 41 阅读

SPOJ Problem Set 2. Prime Generator 求某区间质数题解2015-02-25题目大意： 给定两个数，要求产生这两个数之间的所有质数。两个数位m和n，其范围如下：The input begins with the number t of test cases in a single line （t<=10）. In each of the next t lines there are two numbers m and ...

Codeforces B. Taxi 算法题解

2016年07月27日 35 阅读

Codeforces B. Taxi 算法题解2015-02-25简单总结题意：有一个数组，数组中的数值不会大于4，即只能是1,2,3,4，要把这些数值装进一个容量最大为4的容器里面，使得所用到这样的容器的个数最小。经测试数据很大，会有10万个数据，所以这里我并不用排序数据，而是使用counting sort的思想，根据特定的数据优化，使得题解时间复杂度为O（n）。程序如下：#include <iostream>#include <vec...

UVa 1422：Processor 任务处理问题

2016年07月27日 36 阅读

UVa 1422：Processor 任务处理问题2015-02-25题目大意：有n个任务送到处理器处理，每个任务信息包括r，d，w，r代表开始时间，w代表必须要结束的时间，w指需要多少时间处理。其中处理器的处理速度可以变速，问处理器最小需要多大速度才能完成工作？输入：3 5 1 4 2 3 6 3 4 5 2 4 7 2 5 8 1 6 1 7 25 4 8 10 7 10 5 8 11 5 10 13 10 11 13 5 8 15 18 10 20 ...

浅谈算法和数据结构 一 栈和队列

2016年07月27日 34 阅读

浅谈算法和数据结构 一 栈和队列2015-02-27最近晚上在家里看Algorithems，4th Edition，我买的英文版，觉得这本书写的比较浅显易懂，而且“图码并茂”，趁着这次机会打算好好学习做做笔记，这样也会印象深刻，这也是写这一系列文章的原因。另外普林斯顿大学在Coursera 上也有这本书同步的公开课，还有另外一门算法分析课，这门课程的作者也是这本书的作者，两门课都挺不错的。计算机程序离不开算法和数据结构，本文简单介绍...

浅谈算法和数据结构 二 基本排序算法

2016年07月27日 36 阅读

浅谈算法和数据结构 二 基本排序算法2015-02-27本篇开始学习排序算法。排序与我们日常生活中息息相关，比如，我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间或者时长排序、买东西会按照销量或者好评度排序、查找文件会按照修改时间排序等等。在计算机程序设计中，排序和查找也是最基本的算法，很多其他的算法都是以排序算法为基础，在一般的数据处理或分析中，通常第一步就是进行排序，比如说二分查找，首先要对数据进行排序。在Donald Knut...

浅谈算法和数据结构 三 合并排序

2016年07月27日 35 阅读

浅谈算法和数据结构 三 合并排序2015-02-27合并排序，顾名思义，就是通过将两个有序的序列合并为一个大的有序的序列的方式来实现排序。合并排序是一种典型的分治算法：首先将序列分为两部分，然后对每一部分进行循环递归的排序，然后逐个将结果进行合并。合并排序最大的优点是它的时间复杂度为O（nlgn），这个是我们之前的选择排序和插入排序所达不到的。他还是一种稳定性排序，也就是相等的元素在序列中的相对位置在排序前后不会发生变化。他的唯一缺点是，需要利用额外的N的...

浅谈算法和数据结构 四 快速排序

2016年07月27日 34 阅读

浅谈算法和数据结构 四 快速排序2015-02-27上篇文章介绍了时间复杂度为O（nlgn）的合并排序，本篇文章介绍时间复杂度同样为O（nlgn）但是排序速度比合并排序更快的快速排序（Quick Sort）。快速排序是20世纪科技领域的十大算法之一 ，他由C. A. R. Hoare于1960年提出的一种划分交换排序。快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中，对数组，列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序...

浅谈算法和数据结构五 优先级队列与堆排序

2016年07月27日 33 阅读

浅谈算法和数据结构五 优先级队列与堆排序2015-02-27在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列（Priority Queue） 。本文首先介绍优先级队列的定义，有序和...

浅谈算法和数据结构 六 符号表及其基本实现

2016年07月27日 34 阅读

浅谈算法和数据结构 六 符号表及其基本实现2015-02-27前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。一符号表在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他...

浅谈算法和数据结构 七 二叉查找树

2016年07月27日 36 阅读

浅谈算法和数据结构 七 二叉查找树2015-02-27前文介绍了符号表的两种实现，无序链表和有序数组，无序链表在插入的时候具有较高的灵活性，而有序数组在查找时具有较高的效率，本文介绍的二叉查找树（Binary Search Tree，BST）这一数据结构综合了以上两种数据结构的优点。二叉查找树具有很高的灵活性，对其优化可以生成平衡二叉树，红黑树等高效的查找和插入数据结构，后文会一一介绍。一 定义二叉查找树（Binary Search Tree），也称有序二...

浅谈算法和数据结构 八 平衡查找树之2-3树

2016年07月27日 33 阅读

浅谈算法和数据结构 八 平衡查找树之2-3树2015-02-27前面介绍了二叉查找树（Binary Search Tree），他对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率，要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态，这就是平衡查找树（Balanced Search Tree）。在一棵具有N 个节点的树中，我们希望该树...

浅谈算法和数据结构 九 平衡查找树之红黑树

2016年07月27日 33 阅读

浅谈算法和数据结构 九 平衡查找树之红黑树2015-02-27前面一篇文章介绍了2-3查找树，可以看到，2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，本文介绍一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）定义红黑树的主要是像是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信...

浅谈算法和数据结构 十 平衡查找树之B树

2016年07月27日 33 阅读

浅谈算法和数据结构 十 平衡查找树之B树2015-02-27前面讲解了平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O（log n）的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平...

浅谈算法和数据结构 十一 哈希表

2016年07月27日 33 阅读

浅谈算法和数据结构 十一 哈希表2015-02-27在前面的系列文章中，依次介绍了基于无序列表的顺序查找，基于有序数组的二分查找，平衡查找树，以及红黑树，下图是他们在平均以及最差情况下的时间复杂度：可以看到在时间复杂度上，红黑树在平均情况下插入，查找以及删除上都达到了lgN的时间复杂度。那么有没有查找效率更高的数据结构呢，答案就是本文接下来要介绍了散列表，也叫哈希表（Hash Table）什么是哈希表哈希表就是一种以 键-值（key-indexed） 存储...

浅谈算法和数据结构 十二 无向图相关算法基础

2016年07月27日 34 阅读

浅谈算法和数据结构 十二 无向图相关算法基础2015-02-27从这篇文章开始介绍图相关的算法，这也是Algorithms在线课程第二部分的第一次课程笔记。图的应用很广泛，也有很多非常有用的算法，当然也有很多待解决的问题，根据性质，图可以分为无向图和有向图。本文先介绍无向图，后文再介绍有向图。之所以要研究图，是因为图在生活中应用比较广泛：无向图图是若干个顶点（Vertices）和边（Edges）相互连接组成的。边仅由两个顶点连接，并且没有方向的图称为无向图...

图的匹配问题与最大流问题（一） 基本的概念

2016年07月27日 37 阅读

图的匹配问题与最大流问题（一） 基本的概念2015-09-02从今天开始，准备写个系列，关于图的匹配，最大流，线性规划等这些图论中的重要而且有着千丝万缕连续的问题，顺便介绍求图的最大匹配问题的著名的匈牙利算法。算是对前段时间学习的一个小结吧。Ps：本人自认很水，多多见谅。（对内容进行了部分修改，原来使用Word编辑的公式这里无法显示，只能截图了）首先这次就先从基本的概念介绍起，顺便说说这之间的一些联系，接下来再开始一一上算法。一、图的匹配问题我们日常中听过...

图的匹配问题与最大流问题（二） 最大流问题Ford-Fulkerson方法

2016年07月27日 35 阅读

图的匹配问题与最大流问题（二） 最大流问题Ford-Fulkerson方法2015-09-02本篇承接上一篇文章，主要讲解最大流问题的Ford-Fulkerson解法。可是说这是一种方法，而不是算法，因为它包含具有不同运行时间的几种实现。该方法依赖于三种重要思想：残留网络，增广路径和割。本文将会详细介绍这些内容，下一篇文章我们提供一种该方法的Java实现。在介绍着三种概念之前，我们先简单介绍下Ford-Fulkerson方法的基本思想。首先需要了解的是Fo...

图的匹配问题与最大流问题（三）最大流问题Ford-Fulkerson方法Java实现

2016年07月27日 38 阅读

图的匹配问题与最大流问题（三）最大流问题Ford-Fulkerson方法Java实现2015-09-02上篇文章主要介绍了Ford-Fulkerson方法的理论基础，本篇给出一种Java的实现。先借助伪代码熟悉下流程FORD-FULKERSON（G，t，s）1 for each edge（u,v）属于E（G）2 do f[u,v]=03 f[v,u]=04 while there exists a path p from s to t in t...

图的匹配问题与最大流问题（四）计算图的边连通度和点连通度

2016年07月27日 34 阅读

图的匹配问题与最大流问题（四）计算图的边连通度和点连通度2015-09-02最近有点忙，好久没跟进了，有兴趣的朋友可以先熟悉下前三篇文章内容，（一）讲述了基础概念；（二）介绍了最大流算法的实现原理以及证明；（三）用Java语言予以了实现，欢迎大家批评指正。回到正题，首先介绍下什么是图的边连通度和点连通度。一般来说，点连通度是指对应一个图G，对于所有点集U属于V（G），也就是V（G）的子集中，使得G-U要么是一个非连通图，要么就是一个平凡图（即仅包含一个独立...

图的匹配问题与最大流问题（五）计算二分图的最大匹配

2016年07月27日 38 阅读

图的匹配问题与最大流问题（五）计算二分图的最大匹配2015-09-02二分图的最大匹配问题第一篇已经说过，下面看看百度百科给的一些解释：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。极大匹配（Maximal Matching）是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配（maximum matching）是所有极大匹配当中边数最大的一个匹配。选择这样的边数...