/目录1问题描述2解决方案2.1位置置换算法2.2走环算法有一个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后变成{a1,b1,a2,b2,a3,b3,...,an,bn}，请考虑有没有时间复杂度为O(n)而空间复杂度为O(1)的解法。  下面算法的时...

/目录1问题描述2解决方案2.1比较计数排序2.2分布计数排序给定一组数据，请使用计数排序，得到这组数据从小到大的排序序列。  下面算法的时间复杂度为O(n^2)，空间复杂度为O(n)。此方法对于任意一组数据均可排序。具体代码如下：packagecom.liuzhen.practice;public...

/目录1问题描述2解决方案2.1定位法在一个m行n列的二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。现在输入这样的一个二维数组和一个整数，请完成一个函数，判断数组中是否含有该整数。  下面算法的时间复杂度为O(m+n)，空间复杂度为O(1)。具体代码如下：pac...

/目录1问题描述2解决方案2.1 每次删除两个不同的数2.2 记录两个值数组中有一个数出现的次数超过了数组长度的一半，请找出这个数。具体代码如下： packagecom.liuzhen.practice;publicclassMain{publicintgetResult(int[]A){...

/目录1问题描述2解决方案何为最大流量问题？给定一个有向图，并为每一个顶点设定编号为0~n，现在求取从顶点0(PS：也可以称为源点)到顶点n(PS:也可以称为汇点)后，顶点n能够接收的最大流量。图中每条边的权值为该边的容量，从顶点0到顶点n的某一条路径中最大流量不能超过该路径中任何一条边剩下的容量。 &nbs...

/目录1问题描述2解决方案2.1蛮力法2.2动态规划法 给定一个浮点数组，任意取出数组中的若干个连续的数相乘，请找出其中乘积最大的子数组。  该方法的时间复杂度为O(n^2)。具体代码如下：packagecom.liuzhen.practice;publicclassMain{public...

/目录1问题描述2解决方案给定一个源串和目标串，能够进行如下操作：在任意位置上插入一个字符；替换掉任意字符；删除任意字符。写一个程序，实现返回最小操作次数，使得对源串进行上述这些操作后等于目标串。此处采用动态规划法，可以较大的提高时间效率。具体代码如下：packagecom.liuzhen.practice;publi...

/目录1问题描述2解决方案有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右走，一共走两次(即从左上角往右下角走两趟)，把所有经过的格子里的数加起来，求总和的最大值。如果两次经过同一个格子，则最后求得的总和中该格子中的数只加一次。此处采用动态规划法，可以较大的提高时间效率。具体代码如下：&n...

/目录1问题描述2解决方案输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成且不改变s1和s2中各个字符原有的相对顺序。此处采用动态规划法，可以较大的提高时间效率。具体代码如下： packagecom.liuzhen.practice;publicclassMain{pu...

/目录1问题描述2解决方案何为二分图的最大匹配问题？引用自百度百科：首先得说明一下何为匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。极大匹配(MaximalMatching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最...

/目录1问题描述2解决方案何为稳定婚姻问题？有一个男士的集合Y={m1,m2,m3...,mn}和一个女士的计划X={n1,n2,n3,...,nn}。每一个男士有一个排序的列表，把女士按照潜在的优先级进行排序。同样，每一个女士也有一个男士的优先级列表。现在，把男士和女士进行配对，要求尽可能的符合优先级的要求。使得最终...

/目录1问题描述2解决方案何为二分图的最大权匹配问题？最大权二分匹配问题就是给二分图的每条边一个权值，选择若干不相交的边，得到的总权值最大。  对于此问题的讲解，引用文末参考资料1：解决这个问题可以用KM算法。理解KM算法需要首先理解“可行顶标”的概念。可行顶标是指关于二分图...

/目录1问题描述2解决方案在最大流有多组解时，给每条边在附上一个单位费用的量，问在满足最大流时的最小费用是多少？  下面代码所使用的测试数据如下图： 具体代码如下：packagecom.liuzhen.practice;importjava.util.ArrayList;importjav...

/目录1问题描述2解决方案ProblemDescription欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N(1<N<1000)和边数M；随后的...

/目录1问题描述2解决方案 John'stripTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 8998 Accepted: 3018 SpecialJudgeDescripti...