Welcome

首页 / 软件开发 / 数据结构与算法

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

2017-02-05 13
图的匹配问题与最大流问题（三）最大流问题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...

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

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

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

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

二叉树的层序遍历概述

2017-02-05 14
二叉树的层序遍历概述2015-09-04前面有篇博客详细分析了二叉树三种遍历（前序、中序、后序）方式的递归与非递归实现，参见：http://blog.csdn.net/ns_code/article/details/12977901，但把二叉树的层序遍历算法给漏掉了，实际上也不能说漏掉了，毕竟层序遍历的实现方法与这三种遍历的实现方法有所不同，因此单独拿出来分析比较合适。二叉树的层序遍历的实现还是比较简单的，由于其层级的关系，很明显要用到队列来辅助实现，主要...

二叉树递归和非递归遍历

2017-02-05 15
二叉树递归和非递归遍历2015-09-04二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先简要介绍三种遍历方式的递归实现，再详细介绍三种遍历方式的非递归实现。一、三种遍历方式的递归实现（比较简单，这里不详细讲解）...

求一天中时针和分针会相遇多少次

2017-02-05 15
求一天中时针和分针会相遇多少次2015-09-04如标题题目：数学分析请看：http://www.planetseed.com/node/18560程序：#include <iostream>#include <vector>#include <string>#include <algorithm>#include <map>#include <math.h>using namespa...

如何求两个数组的交集

2017-02-05 15
如何求两个数组的交集2015-09-04题目意思大概是这样的：给定两个大数组（1w以上1亿以下），用最有效的方法找出来两个数组的交集。对于这道题，我有一个思路就是，先对数组进行排序，然后用两个指针在已排序的数组上轮流指向头结点，进行比较。比较亮的地方，就是在于这个比较的方式了。首先，比较的时候，要先确定两个指针指向的内用是否一致。如果一致，那么这个点，就是交集的一个元素，没问题吧？这里有一个问题就是，接下来如何比较？步骤是这样的：先比较两个指针指向内容的大...

产生下一个排列数的算法

2017-02-05 13
产生下一个排列数的算法2015-09-06全排序：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。例如n=3，全排序为：123、132、213、231、312、321共6种。字典序法：对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是：从左到右逐个比较对应的字符大小。字符集{1,2,3}，较小的数字较先，这样按字典序生成的全排列即：1...

可持久化的数据结构

2017-02-05 16
可持久化的数据结构2015-09-06 cnblogs BLADEVIL可持久数据结构主要指的是我们可以查询历史版本的情况并支持插入，利用使用之前历史版本的数据结构来减少对空间的消耗（能够对历史进行修改的是函数式）。在这里只讲下比较常用的可持久化线段树和trie。对于线段树我们记录每个节点的左右儿子，如果空间允许的话我们也可以记录每个数代表的区间，对于打标签操作我们则需要新建两个节点表示新的历史，比较常用的是用可持久化线段树来维护权值，然后维护不同区间的权...

二叉排序树的C语言实现

2017-02-05 14
二叉排序树的C语言实现2015-09-06二叉排序树简介二叉排序树（Binary Sort Tree，简称BST），又称二叉查找树，是红黑树、AVL树等的基础。它或是一棵空树，或者是具有下列性质的一棵二叉树：1、若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2、若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；3、它的左右子树也分别为二叉排序树。下面的一棵树即为二叉排序树：很明显，对二叉排序树进行中序遍历，便可得到一个有序序列，...

编程算法之合并有序链表

2017-02-05 14
编程算法之合并有序链表2015-09-06题目:合并有序链表, 给定两个升序的链表, 返回一个合并之后的升序链表.节点结构:struct Node{int val;Node *next;};要求实现的函数:Node* mergeList（Node *list_a, Node* list_b）代码:/** test.cpp**Created on: 2014.04.24*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#in...

如何把数组排成最小的数

2017-02-05 14
如何把数组排成最小的数2015-09-08题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。输入：输入可能包含多个测试样例。对于每个测试案例，输入的第一行为一个整数m （1<=m <=100）代表输入的正整数的个数。输入的第二行包括m个正整数，其中每个正整数不超过10000000。输出：对应每个测试案例，输出m...

求树中两个结点的最近公共祖先

2017-02-05 13
求树中两个结点的最近公共祖先2015-09-08剑指offer上的最后一题了，一个递归函数调了一下午，才得到正确的结果。题目描述：给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。输入：输入可能包含多个测试样例。对于每个测试案例，输入的第一行为一个数n（0<n<1000），代表测试样例的个数。其中每个测试样例包括两行，第一行为一个二叉树的先序遍历序列，其中左右子树若为空则用0代替，其中二叉树的结点个数node_num<10000。...

哈夫曼树以及哈夫曼编码

2017-02-05 14
哈夫曼树以及哈夫曼编码2015-09-08哈夫曼树简介哈夫曼树（哈夫曼树），又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,...,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,...,wn}，则所构造出的带权路径长度最小的二叉树就被称为哈夫曼树。这里补充下树的带权路径长度的概念。树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和，如果在一棵二叉树中共有n个叶子节点，用...

排序算法之快速排序

2017-02-05 13
排序算法之快速排序2015-09-08快速排序算法，以升序为例操作系统：ubuntu编译软件：gcc结果截图：源代码：#include<stdio.h>void quickSort（int *,int,int）;int findPoss（int *,int,int）;int main（）{int i;int arry[] = {8,9,0,-3,6,7,-11};quickSort（arry,0,6）;printf（"After so...

输出斐波那契数列的算法

2017-02-05 13
输出斐波那契数列的算法2015-09-10斐波那契数列（Fibonacci polynomial），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……要求编程输出这样的一组数，比如输出10个数的序列/*** @param i 第n个数* @param j 第n+1个数* @param n 输出个数*/public static void ff（ int i,int j,int n）{int m=1...

如何递归处理多层嵌套列表

2017-02-05 14
如何递归处理多层嵌套列表2015-09-10建立一个多层列表（即列表中存储列表）并输出列表项如下图：可以看出输出的只是输出了外列表当然也可以多次循环输出每一个子项：如下图所示注：isinstance（object, classinfo）为python的内置函数，用来判断对象的类型这是三层循环，如果是很多次循环再用for循环输出就太麻烦了，对于这种情况需要建立一个函数，递归循环输出子项如下图所示：只需建立函数print_lol（），如果内置函数isinsta...

字典树概述

2017-02-05 13
字典树概述2015-09-10字典树简介字典树（Trie Tree），又称单词查找树，是键树的一种，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。字典树有3个基本性质：1、根节点不包含字符，其余的每个节点都包含一个字符；2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；3、每个节点的所有子节点包含的字符都不相同。字典树的结构一般如下图所示：以字符串为例，我们可以将其存储结构写成...

内部排序算法的总结

2017-02-05 13
内部排序算法的总结2015-09-10内部排序总结这篇博文我们简要地总结下各种内部排序方法。这10种排序算法中，前面7种属于建立在“比较”基础上的排序算法，通过决策树已经证明，任何基于比较进行的排序算法的时 间复杂度不可能再优于O（n*logn）。后面3种不是建立在比较的基础上的，因此，可以达到线性运行时间。下面我们给出各种排序方法的时空复杂度的表格（属于自己总结，有不对的地方，希望大家指正或补充）。关于各种排序，给出如下几点总结：...

关于数组中的逆序对

2017-02-05 13
关于数组中的逆序对2015-09-12题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。输入：每个测试案例包括两行：第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。第二行包含n个整数，每个数组均为int类型。输出：对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。样例输入：47 5 6 4样例输出：5思路：最简单的方法是顺序...
<< 121 122 123 124 125 126 127 128 129 130 >>
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图