为您找到搜索结果：1674个
算法笔记_049:奇偶数排序（Java）
/目录1问题描述2解决方案2.1一头一尾指针往中间扫描法2.2一前一后两个指针同时往后扫描法给定一个整数数组，请调整数组中数的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。具体代码如下：packagecom.liuzhen.array_2;publicclassOddEvenSort{//解法1：一头一尾指针往中间扫描publicvoidgetOddEvenSort1(int[]A){if(A.length==1)return;intbegin=0;intend=A.length-1;while(begin<end){if(A[begin]%2==1)//当A[begin]为奇数时begin++;elseif(A[end]%2==0)//当A[end]为偶数时end--;else//当A[begin]不是奇数且A[end]不是偶数时swap(A,begin,end);}}//交换数组A的m位置和n位置上的值publicvoidswap(int[]A,intm,intn){inttemp=A[m];A[m]=A[n];A[n]=temp...
算法笔记_050:硬币收集问题（Java）
/目录1问题描述2解决方案2.1动态规划法在n*m格木板中放有一些硬币，每格的硬币数目最多为一个，在木板左上方的一个机器人需要收集尽可能多的硬币并把它们带到右下方的单元格。每一步，机器人可以从当前的位置向右移动一格或向下移动一格。当机器人遇到一个有硬币的单元格时，就会将这枚硬币收集起来。设计一个算法找出机器人能找到的最大硬币数并给出相应的路径。本文编码思想参考自《算法设计与分析基础》第三版，具体如下： 具体代码如下：packagecom.liuzhen.chapter8;publicclassRobotCoinCollection{//输出找到最大硬币数的路径publicvoidgetMaxPath(int[][]A){introwA=A.length;intcolumnA=A[0].length;//在数组A最上面一行添加一行元素0，在最左边一列添加一列元素0int[][]changeA=newint[rowA+1][columnA+1];//初始化，各个元素均为0int[][]maxA=newint[rowA+1][columnA+1];//用于计算从A[0][0]到达各...
算法笔记_051:荷兰国旗问题（Java）
/目录1问题描述2解决方案现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右的球依次为红球、白球、蓝球。这个问题之所以叫荷兰国旗，是因为将红白蓝三色的小球弄成条状物，并有序排列后正好组成荷兰国旗。为了方便编码与讨论，用数字0表示红球，数字1表示白球，数字2表示蓝球，所以最后生成的排列为0,1,2。解决该问题，只需先设定三个用于指定元素的下标指针（PS：在Java中没有指针，此处方便描述）:一个前指针begin，一个中指针current，一个后指针end。Current指针遍历整个数组序列：（1）当current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++；（2）当current指针所指元素为1时，不做任何交换，而后current++；（3）当current指针所指元素为2时，与end指针所指的元素交换，而后current指针不动，end--.那么，为什么在上述第（3）步中，current指针不动？因为如果end所指元素为0时，此时current指针就不能动。具体代码如下：packagecom.liuzh...
算法笔记_052:蓝桥杯练习Multithreading（Java）
/目录1问题描述2解决方案问题描述 现有如下一个算法： repeatnitimes yi:=y y:=yi+1 endrepeat 令n[1]为你需要算加法的第一个数字，n[2]为第二个，...n[N]为第N个数字（N为需要算加法的数字个数）， 并令y初始值为0，先令i=1运行这个算法（如上所示，重复n[i]次），然后令i=2运行这个算法。。直到i=N。注意y值一直不要清零。最后y的值就是你需要的加法答案。 你想知道，有没有某种运算顺序能使答案等于W。 一个循环中的全部语句，是不能改变在总的语句排列中的相对顺序的。 （这里的第i个循环是指这n[i]*2条语句。就是你把属于第i个循环的语句抽出来看，它们需要按照原顺序排列。在你没有运行完这个循环的最靠前一条未完成的语句的时候，你是不能跳过它先去完成这个循环后面的语句的。你能做的仅是把若干个循环按照你所规定的顺序“归并”起来。） 举个例子，n[1]=2,n[2]=1,W=1.一种可行的运算顺序是“211112”，数字为几表示运行第几个算法的下一条语句（你可以看到&rdqu...
算法笔记_053:最优二叉查找树（Java）
/目录1问题描述2解决方案在了解最优二叉查找树之前，我们必须先了解何为二叉查找树？引用自百度百科一段讲解：二叉排序树（BinarySortTree）又称二叉查找树（BinarySearchTree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）左、右子树也分别为二叉排序树；在二叉查找树的基础上，引出了一个最优二叉查找树的问题：它在查找树中所有节点的平均键值比较次数是最低的。（PS：如若对于最优二叉查找树的定义理解还是有点模糊，可以参考本文最后给出的参考资料中的链接）本文具体编码思想参考自《算法设计与分析基础》第三版，具体如下（PS：对于文中的具体思想，楼主自己是前后看了三四遍才整明白其具体思想，竟无语吟噎......，如若对于下面贴出的书中介绍无法理解，可以参考文末给出的参考资料的链接中，一位网友的博客讲解哦）： 具体代码如下：packagecom.liuzhen.chapter8;public...
算法笔记_054:Prim算法（Java）
/目录1问题描述2解决方案2.1贪心法何为Prim算法？此处引用网友博客中一段介绍（PS：个人感觉网友的这篇博客对于Prim算法讲解的很清楚，本文与之相区别的地方在于具体实现代码的不同，该网友是使用C++实现，而本文是使用Java实现。其他理论讲解可以参考该网友的博客哦，具体链接看文末参考资料） 普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex(graphtheory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：VojtěchJarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：RobertC.Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。 原理简单介绍：1).输入：一个加权连通图，其中顶点集合为V，边集合为E；2).初始化：V...
算法笔记_055:蓝桥杯练习 Tricky and Clever Password （Java）
/目录1问题描述2解决方案问题描述 在年轻的时候，我们故事中的英雄——国王Copa——他的私人数据并不是完全安全地隐蔽。对他来说是，这不可接受的。因此，他发明了一种密码，好记又难以破解。后来，他才知道这种密码是一个长度为奇数的回文串。 Copa害怕忘记密码，所以他决定把密码写在一张纸上。他发现这样保存密码不安全，于是他决定按下述方法加密密码：他选定一个整数X，保证X不小于0，且2X严格小于串长度。然后他把密码分成3段，最前面的X个字符为一段，最后面的X个字符为一段，剩余的字符为一段。不妨把这三段依次称之为prefix,suffix,middle。显然，middle的长度为一个大于0的奇数，且prefix、suffix的长度相等。他加密后的密码即为A+prefix+B+middle+C+suffix，其中A、B、C是三个由Copa选定的字符串，且都有可能为空，+表示字符串相连。 许多年过去了。Copa昨天找到了当年写下加密后字符串的那张纸。但是，Copa把原密码、A、B、C都忘了。现在，他请你找一个尽量长的密码，使得这个密码有可能被当...
算法笔记_056:蓝桥杯练习 未名湖边的烦恼（Java）
/目录1问题描述2解决方案2.1递归法2.2递推法 问题描述 每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。 每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）输入格式 两个整数，表示m和n输出格式 一个整数，表示队伍的排法的方案数。样例输入32样例输出5数据规模和约定 m,n∈［0,18］ 问题分析 共有m个人还鞋，n个人借鞋，记最终排列数为f(m,n)。现在求m和n的排队情况，具体理解如下：起始，要去一人还鞋(PS:此时，m=m-1)，还完后，可以选一人还鞋(PS：m=m-1)或者一人借鞋(PS:n=n-1)。那么，f(m,n)=f(m-1,n)+f(m,n-1)。这就是求取f(m,n)的递推公式，那么轻易可知当m<n时，f(m,n)=0；当n=0时，f(m,0)=1。&n...
算法笔记_057:蓝桥杯练习 最大的算式 （Java）
/目录1问题描述2解决方案问题描述 题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如： N=5，K=2，5个数字分别为1、2、3、4、5，可以加成： 1*2*(3+4+5)=24 1*(2+3)*(4+5)=45 (1*2+3)*(4+5)=45 ……输入格式 输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15,0<=K<=N-1）。第二行为N个用空格隔开的数字（每个数字在0到9之间）。输出格式 输出文件仅一行包含一个整数，表示要求的最大的结果样例输入5212345样例输出120样例说明 (1+2+3)*4*5=120 当时自己第一次做的时候，得分44分，而且感觉是碰对的..，后来百度了一下，具体编码思想是采用深度优先搜索递归法思想解决了此问题，具体解释可以参考本文文末的参考资料。 具体代码如下：packag...
算法笔记_058:蓝桥杯练习 2的次幂表示（Java）
/目录1问题描述2解决方案问题描述 任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。 将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0 现在约定幂次用括号来表示，即a^b表示为a（b） 此时，137可表示为：2（7）+2（3）+2（0） 进一步：7=2^2+2+2^0（2^1用2表示） 3=2+2^0 所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0） 又如：1315=2^10+2^8+2^5+2+1 所以1315最后可表示为： 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）输入格式 正整数（1<=n<=20000）输出格式 符合约定的n的0，2表示（在表示中不能有空格）样例输入137样例输出2(2(2)+2+2(0))+2(2+2(0))+2(0)样例输入1315样例输出2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)提示 ...
算法笔记_059:蓝桥杯练习 Anagrams问题（Java）
/目录1问题描述2解决方案问题描述 Anagrams指的是具有如下特性的两个单词：在这两个单词当中，每一个英文字母（不区分大小写）所出现的次数都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。编写一个程序，输入两个单词，然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符，而且是大小写无关的。 输入格式：输入有两行，分别为两个单词。 输出格式：输出只有一个字母Y或N，分别表示Yes和No。 输入输出样例样例输入UnclearNuclear样例输出Y 具体代码如下：packagecom.liuzhen.systemExe;importjava.util.Scanner;publicclassMain{publicvoidprintJudge(StringA,StringB){if(A.length()!=B.length()){System.out.println...
算法笔记_060:蓝桥杯练习 出现次数最多的整数（Java）
/目录1问题描述2解决方案问题描述 编写一个程序，读入一组整数，这组整数是按照从小到大的顺序排列的，它们的个数N也是由用户输入的，最多不会超过20。然后程序将对这个数组进行统计，把出现次数最多的那个数组元素值打印出来。如果有两个元素值出现的次数相同，即并列第一，那么只打印比较小的那个值。 输入格式：第一行是一个整数N，N£20；接下来有N行，每一行表示一个整数，并且按照从小到大的顺序排列。 输出格式：输出只有一行，即出现次数最多的那个元素值。输入输出样例样例输入5100150150200250样例输出150 感觉这题有点坑啊...重点在于加范围判断 具体代码如下：packagecom.liuzhen.systemExe;importjava.util.Scanner;publicclassMain{publicvoidprintResult(int[]A){intcountMax=1;intcounti=0;inttempCount=1;for(inti=1;i<A.length;i++){if(A[i-1]==A[i])++...
算法笔记_061:蓝桥杯练习 字串统计（Java）
/目录1问题描述2解决方案问题描述 给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式 第一行一个数字L。 第二行是字符串S。 L大于0，且不超过S的长度。输出格式 一行，题目要求的字符串。 输入样例1： 4 bbaabbaaaaa 输出样例1： bbaa 输入样例2： 2 bbaabbaaaaa 输出样例2： aa数据规模和约定 n<=60 S中所有字符都是小写英文字母。提示 枚举所有可能的子串，统计出现次数，找出符合条件的那个 前三次提交只得了40分，只怪自己把KMP模式匹配算法写错了，冒汗... 本题主要考查KMP模式匹配算法，思想比较简单，具体可以理解可以看注释哦具体代码如下：packagecom.liuzhen.systemExe;importjava.util.Scanner;publicclassMain{//KMP算法求取next函数值publicint[]getNext(...
算法笔记_062:蓝桥杯练习 最小乘积(基本型)(Java)
/目录1问题描述2解决方案问题描述 给两组数，各n个。 请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。 例如两组数分别为:13 -5和-241 那么对应乘积取和的最小值应为： (-5)*4+3*(-2)+1*1=-25输入格式 第一个行一个数T表示数据组数。后面每组数据，先读入一个n，接下来两行每行n个数，每个数的绝对值小于等于1000。 n<=8,T<=1000输出格式 一个数表示答案。样例输入2313-5-24151234510101样例输出-256 解决此题关键的思想，就是先找出数组A中最大值和最小值，数组B中最大值和最小值。然后，用两个最大值中的最大值和另一个数组中的最小值相乘，再把所有元素对的乘积累加就可以得到题目要求的最终结果。在第一次提交时，忘记注释掉输入提示语句，结果判分0分，当时心一沉，再仔细一看，天啊噜，下次绝对不能再犯这样的错误...具体代码如下：packagecom.liuzhen.systemExe;importjava.util.Scanner;publ...
算法笔记_063:蓝桥杯练习 送分啦（Java）
/目录1问题描述2解决方案问题描述 这题想得分吗？想，请输出“yes”；不想，请输出“no”。输出格式 输出包括一行，为“yes”或“no”。 初步一看，这题竟然没有输入输出示例，不过也不难吧。好吧，第一次，代码长这样：importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);StringA=in.nextLine();if(A.equals("想"))System.out.println("yes");elseif(A.equals("不想")){System.out.println("no");}}} 然后，结果评分为0分，查看一下输入输出示例：输入为空，输出yes。ＯＫ，那我再改改代码：importjava.util.Scanner;publicclassMain{publicstaticvoid...