为您找到搜索结果：1674个
算法笔记_019:背包问题（Java）
/目录1问题描述2解决方案2.1蛮力法2.2减治法2.2.1递归求解2.2.2非递归求解（运用异或运算）2.3动态规划法给定n个重量为w1，w2，w3，...，wn，价值为v1，v2，...，vn的物品和一个承重为W的背包，求这些物品中最有价值的子集（PS：每一个物品要么选一次，要么不选），并且要能够装到背包。附形象描述：就像一个小偷打算把最有价值的赃物装入他的背包一样，但如果大家不喜欢扮演小偷的角色，也可以想象为一架运输机打算把最有价值的物品运输到外地，同时这些物品的重量不能超出它的运输能力。使用蛮力法解决包含n个物品的背包问题，首先得求出这n个物品的所有子集，对于每一个物品存在两种情况：选中（在程序中用1表示），未选中（在程序中用0表示）。该n个物品的所有子集数数量为2^n。下面请看一个简单示例： 此处，使用一个二维数组存放所有子集，数组的每一行代表一个子集，每一列代表一个具体物品。packagecom.liuzhen.chapterThree;publicclassKnapsack{publicintmaxSumValue=0;//定义满足背包问题子集的最大承重所得的总...
算法笔记_020:深度优先查找（Java）
/目录1问题描述2解决方案2.1蛮力法深度优先查找（depth-firstsearch，DFS）可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。这个过程一直持续，直到遇到一个终点——该顶点的所有邻接顶点都已被访问过。在该终点上，该算法沿着来路后退一条边，并试着继续从那里访问未访问的顶点。再后退到起始顶点上，并且起始顶点也是一个终点时，该算法最终停了下来。这样，起始顶点所在的连通分量的所有顶点都被访问过了。如果，未访问过的顶点仍然存在，该算法必须从其中任一点开始，重复上述过程。 总之，记住一句话，深度优先查找就是先尽可能达到当前遍历路径能够达到最长的路径，一旦达到该路径终点，再回溯，从原来已遍历过顶点（PS：该顶点包含多个分支路径）处开始新的分支路径遍历。此处借用算法设计与分析基础（第三版）上一段概念介绍，及说明图形介绍其具体遍历过程，下面的具体代码使用数据就是下图中相关数据。具体代码如下：packagecom.liuzhen.chapterThree;publicclassDept...
算法笔记_021:广度优先查找（Java）
/目录1问题描述2解决方案2.1蛮力法广度优先查找（Breadth-firstSearch,BFS）按照一种同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后是离它两条边的所有未访问顶点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都被访问过了为止。如果仍然存在未被访问的顶点，该算法必须从图的其他连接分量中的任意顶点重新开始。此处借用《算法设计与分析基础》（第3版）上一段文字介绍及其配图来讲解，下面程序中使用的图就是配图中所给的数据，在程序中，使用邻接矩阵来表示配图中图。 PS:下面所给程序的运行结果和配图中图（b）顺序在fb那两个位置不一致，下面程序运行结果顺序是acdebfghji，原因是在遍历的过程中，我所写代码是按照字母顺序来进行遍历的，课本上所讲可能是使用链表来存储顶点，具体怎么实现本人也未去仔细探讨...具体代码如下：packagecom.liuzhen.chapterThree;publicclassBreadthFirstSearch{publicintcount=0;//计算广度优先遍历总次数，初始化为0/**adjMatrix是待遍历图的邻接矩阵...
算法笔记_022:字符串的旋转（Java）
/目录1问题描述2解决方案2.1蛮力移位2.2三步反转给定一个字符串，要求将字符串前面的若干个字符移到字符串的尾部。例如，将字符串“abcdef”的前3个字符‘a’、‘b’和‘c’移到字符串的尾部，那么原字符串将变成“defabc”。请写一个函数实现此功能。此方法将需要移动的字符一个一个地移到字符串的尾部，具体代码如下：packagecom.liuzhen.string_1;publicclassStringRevolve{//方法1：蛮力移位/**参数s:给定字符串*返回每次移动一位后的结果字符串*/publicStringbruteOne(Strings){char[]A=s.toCharArray();chartemp=A[0];for(inti=1;i<A.length;i++)A[i-1]=A[i];A[A.length-1]=temp;returnString.valueOf(A);}/**参数s:给定字符串*参数m:字符串前面需要移动的字符个数*返...
算法笔记_023:拓扑排序（Java）
/目录1问题描述2解决方案2.1基于减治法实现2.2基于深度优先查找实现给定一个有向图，求取此图的拓扑排序序列。那么，何为拓扑排序？定义：将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。 实现原理：不断地做这样一件事，在余下的有向图中求取一个源（source）（PS：定义入度为0的顶点为有向图的源），它是一个没有输入边的顶点，然后把它和所有从它出发的边都删除。（如果有多个这样的源，可以任意选择一个。如果这样的源不存在，算法停止，此时该问题无解），下面给出《算法设计与分析基础》第三版上一个配图： 具体代码如下：packagecom.liuzhen.chapterFour;importjava.util.Stack;publicclassTopologicalSorting{//方法1：基于减治法：寻找图中入度为0的顶点作为即将遍历的顶点，遍历完后，将此顶点从图中删除/**参数adjMatrix:给出图的邻接矩阵值*参数source:给出图的每个顶点的入度值*该函数功能...
算法笔记_024:字符串的包含（Java）
/目录1问题描述2解决方案2.1蛮力轮询法2.2素数相乘法2.3位运算法给定一长字符串A和一短字符串B。请问，如何最快地判断出短字符串B中的所有字符是否都在长字符串A中？请编写一个判断函数实现此功能。为简单起见，假设输入的字符串只包含小写英文字母。下面举几个例子。（1）如果字符串A是”abcd”，字符串B是”bad”，答案是包含，因为字符串B中的字母都在字符串A中，或者说B是A的真子集。（2）如果字符串A是”abcd”，字符串B是”bce”，答案是不包含，因为字符串B中的字母e不在字符串A中。（3）如果字符串A是”abcd”，字符串B是”aab”，答案是包含，因为字符串B中的字母a包含在字符串A中。判断字符串B中的字符是否都在长字符串A中，最直观的思路则是：轮询B中每一个字符，逐个与A中每个字符进行比较，看是否都在字符串A中。具体代码如下：packagecom.liuzhen.string_1;publicclassStringContain{...
算法笔记_025:字符串的全排列（Java）
/目录1问题描述2解决方案2.1递归实现2.2字典序排列实现输入一个字符串，打印出该字符串的所有排列。例如，输入字符串”abc”，则输出有字符’a’,’b’,’c’所能排列出来的所有字符串”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。从字符串中选出一个字符作为排列的第一个字符，然后对剩余的字符进行全排列。如此递归处理，从而得到所有字符的全排列。具体代码如下：packagecom.liuzhen.string_1;publicclassStringArrange{//方法1：递归实现/**参数arrayA:给定字符串的字符数组*参数start:开始遍历字符与其后面各个字符将要进行交换的位置*参数end:字符串数组的最后一位*函数功能：输出字符串数字的各个字符全排列*/publicvoidrecursionArrange(cha...
算法笔记_026:折半查找（Java）
/目录1问题描述2解决方案2.1递归法2.2迭代法 首先，了解一下何为折半查找？此处，借用《算法设计与分析基础》第三版上一段文字介绍： 具体代码如下：packagecom.liuzhen.chapter4;publicclassBinarySearch{//方法1：递归求解publicvoidrecursionSearch(int[]A,intstart,intend,intnumber){intmid=(start+end)/2;if(A[mid]==number)System.out.println("使用递归法求取number="+number+"的数组下标结果："+mid);if(A[mid]>number)recursionSearch(A,start,mid-1,number);//递归调用if(A[mid]<number)recursionSearch(A,mid+1,end,number);//递归调用}publicstaticvoidmain(String[]args){Bin...
算法笔记_027:俄式乘法（Java）
首先，了解一下何为俄式乘法？此处，借用《算法设计与分析基础》第三版上一段文字介绍： 具体编码如下：packagecom.liuzhen.chapter4;publicclassRussianPeasant{//方法1：递归求解publicvoidrecursionRussian(intm,intn,intresult){if(m<1)return;if(m==1)System.out.println("使用递归求取m*n结果："+(result+n));if(m%2==0){m=m/2;n=n*2;recursionRussian(m,n,result);}else{result+=n;m=(m-1)/2;n=n*2;recursionRussian(m,n,result);}}//方法2：迭代求解publicintiterationRussian(intm,intn){intresult=0;while(m>0){if(m%2==0){m=m/2;n=n*2;}else{result+=n;m=(m-1)/2;n=n*2;}}return...
算法笔记_028:字符串转换成整数（Java）
输入一个由数字组成的字符串，请把它转换成整数并输出。例如，输入字符串“123”，输出整数123。请写出一个函数实现该功能，不能使用库函数。 解答本问题的基本思路：从左至右扫描字符串中的每个字符，把之前扫描得到的数字乘以10，再加上当前字符表示的数字。但是，基本思路是这样，还要注意以下几点：（1）最好判断一下输入是否为空。（2）如果字符串的第一个字符是‘-’号，最终得到的整数必为负整数。（3）输入的字符串中不能含有不是数字的字符。（4）输入的字符串不能太长，否则转换成整数后会导致整数溢出。具体实现代码如下：packagecom.liuzhen.string_1;importjava.util.Scanner;publicclassStringToInt{publicstaticintMax_INT=Integer.MAX_VALUE;publicstaticintMin_INT=Integer.MIN_VALUE;publicintgetStringToInt(StringA){char[]arrayA=A.toCha...
算法笔记_029:约瑟夫斯问题（Java）
/目录1问题描述2解决方案引用自《算法设计与分析基础》第三版：约瑟夫斯问题，是以弗拉瓦斯。约瑟夫斯（FlaviusJosephus）的名字命名的。约瑟夫斯是一个著名的犹太历史学家，参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫斯作为一个将军，设法守住了裘达伯特的堡垒达47天之久，但在城市陷落了以后，他和40名顽强的将士在附近的一个洞穴中避难。在那里，这些反抗者表决说“要投降毋宁死”。于是，约瑟夫斯建议每个人应该轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫斯有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降罗马。 上述是约瑟夫斯问题的起源，看完后个人感觉有点抽象，其实约瑟夫斯问题的本质为：n个人（编号由 1,2, ..., n）围成一圈，由编号为1的人从1开始报数，报到k的退出自杀，剩下的人继续从1开始报数，直到圈内只剩余1人，求胜利者的编号。(n>0,k>0) 例如：原n个人编号：1 2 3 ...
算法笔记_030:回文判断（Java）
/目录1问题描述2解决方案给定一个字符串，如何判断这个字符串是否是回文串？所谓回文串，是指正读和反读都一样的字符串，如madam、我爱我等。 解决上述问题，有两种方法可供参考：（1）从字符串两头往中间扫；（2）从字符串中间往两头扫。具体代码如下：packagecom.liuzhen.string_1;importjava.util.Scanner;publicclassStringPalindrome{//方法1：两头往中间扫publicbooleanIsPalindrome1(StringA){char[]arrayA=A.toCharArray();inttop=0;intend=arrayA.length-1;if(A.equals("")||A.equals(null))//非法输入returnfalse;while(top<end){if(arrayA[top++]!=arrayA[end--])returnfalse;}returntrue;}//方法2：中间往两头扫publicbooleanIsPalindrome2(StringA){char...
算法笔记_031:计算中值和选择问题（Java）
/目录1问题描述 2解决方案2.1计算中值问题2.2选择问题中值问题是求一个n个数列表中某一数组下标k，它要求该下标元素比列表中的一半元素大，又比另一半元素小，这个中间的值被称为中值。 选择问题是求一个n个数列表的第k个最小元素的问题。 本文使用Lomuto划分算法思想，此处引用《算法设计与分析基础》第三版上一段文字介绍及配图，具体如下： 具体实现代码如下：packagecom.liuzhen.chapter4;publicclassMedianProblem{//Lomuto划分/**参数A：给定的随机数数组*参数start：开始进行选择的数组元素位置*参数end：最后一个进行选择的数组元素位置*函数功能：返回A[start]到A[end]元素中间的某一元素位置result，使得左边部分元素<A[result]<=右边部分元素*/publicintLomutoPartition(int[]A,intstart,intend){intbegin=A[start];intresult=start;for(inti=start...
算法笔记_032:最长回文串（Java）
/目录1问题描述2解决方案2.1中心扩展法2.2Manacher算法给定一个字符串，求它的最长回文子串的长度。 此处，首先枚举出回文串的中心位置，然后，再在该位置上分别向左和向右扩展，记录并更新得到的最长回文串的长度。具体代码如下：packagecom.liuzhen.string_1;importjava.util.Scanner;publicclassStringLongestPalindrome{/**参数A：给定字符串*函数功能：返回字符串A中最长回文串的长度*/publicintgetLongestPalindrome(StringA){char[]arrayA=A.toCharArray();intmax=0;inttempMax=0;if(A.equals("")||A.equals(null))return0;for(inti=0;i<arrayA.length;i++){//i为回文串的中心位置//当回文串位数为奇数时for(intj=0;(i-j)>=0&&(i+j)<arrayA.length;j++){if...
算法笔记_033:十六进制转八进制（Java）
/目录1问题描述2解决方案2.1注意问题2.2具体实现代码 具体问题描述 给定n个十六进制正整数，输出它们对应的八进制数。输入格式 输入的第一行为一个正整数n（1<=n<=10）。 接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。输出格式 输出n行，每行为输入对应的八进制正整数。 【注意】 输入的十六进制数不会有前导0，比如012A。 输出的八进制数也不能有前导0。样例输入 2 39 123ABC样例输出 71 4435274 【提示】 先将十六进制数转换成某进制数，再由某进制数转换成八进制。解决方案： packagecom.liuzhen.systemExe;importjava.util.Scanner;publicclassMain{//把16进制字符串转成2进制字符串publicStringgetSixteenToTwo(StringA){StringBuilderresult=newStringBuilder("");char[]arrayA...