配对方案问题 问题分析 先了解几个概念。 二分图：又称二部图。设G=(V,E)是一个无向图，如果结点集V客分割为两个互不相交的子集（V1,V2），并且图中的每条边（i,j）所关联的两个结点i和j分别属于这两个不同的结点集（i∈V1，j∈V2），则称图G是一个二分图。 匹配：在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共结点。 最大匹配：一个图所有匹配中，边数最多的匹配，成为这个图的最大匹配。 最佳推销员配对方案要求两个推销员男女搭配，相当于男女推销员形成了两个不相交的集合，可以配合工作的男女推销员有连线…

优化扩展——重贴标签算法ISAP 首先对所有的结点标记到汇点的最短距离，称之为高度。标高从汇点开始，用BFS方式，汇点的邻接点高度为1，继续访问的结点高度是2，一直到源点结束。 贴好标签之后，就可以从源点开始，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进。我们找到了1-2-4-6。 我们再次从源点开始搜索，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进，h(1)=3,h(2)=2，走到这里无法走到4号结点，因为没有邻接边，3号结点不近没有邻接边，而且高度…

题目4 和为S的两个数字 题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 题目解析 我们知道，两个数字，距离越远，乘积越小，距离越近乘积越大。所以我们可以设置两个指针，一个指向开头，一个指向末尾，然后他们不断移动，同时相加看是不是等于所制定的值。移动的条件是： 若和大于指定值，则将右指针左移； 若和小于指定值，则将左指针右移； 若到最后左指针和有指针位于一个位置，那么直接返回。 代码 vector<int> Fi…

题目1 二叉树的深度 题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 题目解析 如果一棵树只有一个结点，那么深度为1.如果根节点只有左子树而没有右子树，那么深度就是左子树深度+1；同理，对于右子树也是如此。如果既有左子树，也有右子树，那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。 代码 int TreeDepth(TreeNode* pRoot) { int Hl, Hr, MaxH; if(pRoo…

最大网络流——最短增广路算法 问题描述 设有向带权图G=(V,E)，V={s,v1,v2,v3,...,t}。在G中有两个特殊的结点s和t。s称为源点，t为汇点。图中各边的方向表示允许的流向，边上的权值表示该边允许通过的最大可能流量cap，且cap≥0，称它为边的容量。而且如果边集合E含有一条边(u,v)，则比如不存在反方向的(v,u)，我们称这样的有向带权图为网络。 网络是一个有向带权图，包含一个源点和一个汇点，没有反平行边。 网络流：网络流即网络上的流，是定义在网络边集E上的一个非负函数flow={flow(u…

题目6 第一次只出现一次的字符 题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。 题目解析 只要这种问题，就可以想到HashTable，但是由于这个问题很简单，而且字符串全部由字母组成，那么每个字母的ASCII码肯定不一样，我们就可以用一个长度为52的数组来记录他们出现的次数，对于字母每出现一次，就对它加1。 当然我们这里为了通用性，可以使用对任意字符进行判断，那么我们就可以考虑实现一个简单的…

题目1 数组中出现次数超过一半的数字 题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 题目解析 最简单的想法就是我们这个数组进行排序，由于数字超过了一半，那么中间的数字（中位数）肯定是我们所需要找的数字。代码实现如代码1所示，但是排序使用快速排序，时间复杂度为O(nlogn)，并没有达到最好的速度。因此参考《剑指offer》一书，我们还可以有两…