- 浏览: 338696 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
pacoson:
感谢楼主。请受小生一拜。
ANT预编译JSP -
zhuhongming123:
一楼的同学Lucene4.* 以上的 已经改成了Numeric ...
Lucene日期排序及组合查询 -
ywjk520:
RangeQuery在哪个包里?
Lucene日期排序及组合查询 -
willwen:
有个疑问,楼主,为何初始化bits 从txt读取已有的网址是直 ...
布隆过滤器(Bloom Filter)之java实例 -
yu_226528:
还不如没有呢
jFreeChart 在jsp页上实现简单的折线图、柱状图
原题如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求: "4 "不能在第三位, "3 "与 "5 "不能相连.
我看了回贴都没有很好解决,主要是没有排除重复。
解决思路:强化题目,用1、2、2、3、4、5这六个数字排列“递增”序列。其他要求不变。
算法思路:显然是递归,初始序列122345,先从末两位(45)变化(45,54),然后末三位(345) ... 直到最后六位.怎样解决重复问题?很简单,由于是递增序列,每生成新序列可与前一生成序列比较,如 <放弃当前序列。当然有更好效率,如预先预测。
方法一代码如下:
class test { // 当前固定部分 private String CurFixPart; private String PreGenNum; public static void main(String[] args) { test t=new test(); t.GenControll( "122345 "); } // 调整字符串s位置pos字符到最前 private String shift(String s, int pos) { String newStr; if (s.length()> pos+1) newStr=s.substring(pos, pos+1) +s.substring(0, pos) +s.substring(pos+1); else newStr=s.substring(pos) +s.substring(0, pos); return newStr; } protected int Validate(String newNum) { String newGenNum=CurFixPart+newNum; if (Integer.valueOf(newGenNum) <=Integer.valueOf(PreGenNum)) return 0; if (newGenNum.substring(2,3).equals( "4 ") || (newGenNum.indexOf( "35 ")!=-1) || (newGenNum.indexOf( "53 ")!=-1)) return 0; PreGenNum=newGenNum; System.out.println(newGenNum); return 0; } public void GenControll(String Base) { PreGenNum= "0 "; CurFixPart= " "; GenNext(Base, 0); } void GenNext(String varPart, int curPos) { if (varPart.length()==2) { Validate(varPart); Validate(shift(varPart, 1)); return; } // Next Layer String newGen=shift(varPart, curPos); String SavedFixPart=CurFixPart; CurFixPart=CurFixPart+newGen.substring(0,1); GenNext(newGen.substring(1), 0); CurFixPart=SavedFixPart; // 同层递增 if (curPos==varPart.length()-1) return; GenNext(varPart, curPos+1); } } 序列122345测试通过。
方法二
其中输入的数组长度和重复的数字可以调整。但是规则是固定的。以后再考虑怎么完善成可以处理任意的字符串,规则也可以考虑用一个可配置的数组来表示。
大体的思路就是先对原始数组排序。并生成重复数字的标记数组。
在主算法的每一层循环对原始数组中的某一位数字的所有可能的位置做全枚举,同时当该位数字不是第一次出现的时候,其位置只能是上一位数字(重复数字)右侧。然后递归调用。
用 122345 和 1222345 测试 OK
import java.util.ArrayList; import java.util.Arrays; /** * @author Owen Luo * @version Created at 2008-11-6 下午12:51:48 用 ArrayList 和 StringBuffer 来实现较少的资源占用。 */ public class CSDN_ArrayQuest_081106 { public static void main(String[] args) { // TODO Auto-generated method stub long beginTime = System.currentTimeMillis(); CSDN_ArrayQuest_081106 newProcess = new CSDN_ArrayQuest_081106(); newProcess.preJobs(); for (int a = 0; a < newProcess.arrayLength; a++) { newProcess.process(newProcess.posAL, a, 0); } long endTime = System.currentTimeMillis(); System.out.println(newProcess.counter); System.out.println( "Computation time: "+ (endTime-beginTime)); } // pozAL 剩下的位置列表,从小到大,顺序排列 // pozIndex 位置列表中遍历的起始位置 // digitIndex 目前正在遍历处理的数字在原始排序数组中的位置 public void process(ArrayList<Integer> pozAL, int pozIndex, int digitIndex) { // make a copy of pozAL ArrayList<Integer> tempAL = new ArrayList<Integer>(pozAL.size()); for (int i = 0; i < pozAL.size(); i++) { tempAL.add(Integer.valueOf(pozAL.get(i).intValue())); } posArray[digitIndex] = tempAL.get(pozIndex).intValue(); tempAL.remove(pozIndex); int nextPozIndex; if (digitIndex != arrayLength - 1) { if (flagArray[digitIndex + 1] == 1) { nextPozIndex = 0; } else { nextPozIndex = pozIndex; //如果是重复对象,只放右边 } for (int i = nextPozIndex; i < tempAL.size(); i++) { process(tempAL, i, digitIndex + 1); } } else { genResult(posArray); //这里用一个 StringBuffer 对象,避免String类型的变量占用过多资源。 // 条件筛出 “35”,“53”,“4”在第二位的情况 if (result.indexOf("35") == -1 & result.indexOf("53") == -1 & result.indexOf("4") != 2) { counter++; System.out.println(result.toString()); } } } public void preJobs() { // sorting original number array Arrays.sort(numArray); // initialize posArray posArray = new int[arrayLength]; for (int i = 0; i < arrayLength; i++) { posArray[i] = i; } posAL = new ArrayList<Integer>(arrayLength); for (int i = 0; i < arrayLength; i++) { posAL.add(Integer.valueOf(i)); } // initialze flagArray flagArray = new int[arrayLength]; for (int i = 0; i < arrayLength; i++) { if (i == 0) { flagArray[i] = 1; } else { flagArray[i] = (numArray[i - 1] == numArray[i]) ? 0 : 1; } } } public void genResult(int[] pozIndex) { result.ensureCapacity(arrayLength); for (int i = 0; i < arrayLength; i++) { result.insert(pozIndex[i],numArray[i]); result.delete(pozIndex[i]+1,pozIndex[i]+2); } } int[] numArray = { 1, 2, 2, 2 ,3, 4, 5 }; int[] posArray; int[] flagArray; int arrayLength = numArray.length; StringBuffer result = new StringBuffer(""); int counter = 0; int counterALL = 0; ArrayList<Integer> posAL; }
方法三
对于任意一个串利用递归进行排列时,我们是循环串中的每个字符到第一个字符进行递归。如果串中字符出现重复的话,则重复的字符只可以利用递归算法一次,即只要与前面相同的字符循环到第一个字符时不调用递归就可以避免重复,为此,我们只需要按如下方式修改算法:
import java.util.*; public class test { static int count=0; public static void main(String[] arg) { Scanner r=new Scanner(System.in); String s=r.nextLine(); Pailie(s, " "); System.out.println( "Total: "+count); } static void Pailie(String s,String p) { if(s.length() <1) { System.out.println(p);//字符串长度小于1,换行 count++; } else { int index[]=new int[s.length()]; for(int i=0; i <s.length(); i++)//该循环将所有字符的第一次出现的位置记录在数组index中 index[i]=s.indexOf(s.charAt(i)); for(int i=0; i <s.length(); i++) { if(i==index[i])//只有当循环数与第一次记录数相等时才递归,保证相同字符中的第一个调用 Pailie(s.substring(1),p+s.substring(0,1));//递归,打印其它字符 s=s.substring(1)+s.substring(0,1);//循环移位 } } } } 这样,由于相同的字符只递归调用了一次,则避免了重复串的排列。下面是几个典型的运算结果: 2222222(输入。当串中的所有字符相同时,应该递归调用1次) 2222222 Total:1 122222(输入。当串中只有一个字符不同时,该字符应该循环所有不同位置) 122222 222221 222212 222122 221222 212222 Total:6 1223(输入。szlhj的例子) 1223 1232 1322 2231 2213 2312 2321 2123 2132 3122 3221 3212 Total:12 122345(输入。本题的要求,最后结果为360个,其它的我就不列出来了,大家可以自己测试) 122345 122354 122453 122435 122534 …… 543221 543212 Total:360
发表评论
-
约瑟夫
2010-02-23 09:31 1226约瑟夫出圈问题 两种方法实现,数据和链表 n个人围成一个圈,一 ... -
int转byte[],byte[]转int
2009-10-10 14:51 1555public byte[] intToByte(int i) ... -
不使用任何循环和递归,输出打印n条(n>1) "Hello World"
2009-07-07 21:09 1008String str="Hello"; ... -
金额转换,阿拉伯数字的金额转换成中国传统的形式如:(¥1011)->(一千零一拾一元整)输出。
2009-06-17 22:29 2387package test.money; import j ... -
求出现次数最多的那个字母及次数,如有多个重复的则都求出。〔金山公司面试题〕
2009-06-17 22:28 1528import java.util.ArrayList; ... -
编程实现统计文本文件中某个单词的出现频率,并输出统计结果
2009-06-17 21:55 3113用HashMap来解决假设单词不存在跨行的,每个单词用,. ; ... -
创建一个静态方法,给它传入一个对象,请循环的打印出该对象所在类的类名和所实现的方法名(华为笔试)
2009-06-17 20:42 2012import java.lang.reflect.*; ... -
在ORACLE大数据量下的分页解决方法
2009-06-17 19:05 1626在ORACLE大数据量下的分页解决方法。 一般用截取ID方法 ... -
编写一个截取字符串的函数
2009-06-17 11:34 936编程:编写一个截取字符串的函数,输入为一个字符串和字节数,输出 ... -
用插入法进行排序
2009-06-17 10:34 1221import java.util.*; class I ... -
用JAVA SOCKET编程,读服务器几个字符,再写入本地显示
2009-06-17 09:41 1169Server端程序: import java.net.*; ... -
java实现B树(二叉树)插入,删除
2009-06-17 07:50 2645B树(二叉搜索树)定义: 1)、每个非叶子节点至多有两个子节点 ... -
java读取(删除)文件夹下的所有文件夹和文件
2009-06-16 15:30 1738import java.io.FileNotFoundExce ... -
500人(小孩)围成一个圈,数到3的人下个人就从1开始数,问最后一个人的位置在那里?
2009-06-16 14:57 1768小孩玩游戏,手拉手围成 ... -
写一个java程序实现线程连接池的功能
2009-06-16 14:44 1185线程池: import java.util.lin ... -
用java写二叉树算法,实现添加数据形成二叉树功能,并打印
2009-06-16 14:27 838public class MyTest { private ...
相关推荐
Java笔试题.docx Java重点面试题 – 针对java面试过程中经常遇到的一些试题进行总结.docx JAVA面试基础知识点总结.docx Java面试笔记.docx 写出正则表达式,从一个字符串中提取链接地址.docx 出现几率最高和覆盖范围...
JAVA笔试面试资料 NET面试题笔试题 web开发 中兴资料 微软笔试面试 数据库面试题笔试题 百度笔试面试 算法 数据结构 网易搜狐新浪笔试面试 腾讯笔试面试 计算机基础 计算机网络 软件测试 阿里巴巴笔试面试
JAVA笔试面试资料 NET面试题笔试题 web开发 中兴资料 微软笔试面试 数据库面试题笔试题 百度笔试面试 算法 数据结构 网易搜狐新浪笔试面试 腾讯笔试面试 计算机基础 计算机网络 软件测试 阿里巴巴笔试面试 C++基础...
中兴笔试题 包括java笔试题,C++笔试题 ,软件工程笔试题等等
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 2015届阿里巴巴校招测试开发工程师在线笔试题.pdf 2015年欢聚时代校园招聘C++笔试题目.pdf ... 浙江大华2015届校园招聘算法、软件类笔试题.pdf
Java笔试题目汇总.pdf Java面试宝典_2010.doc 面试全攻略100题.doc 智力题和答案.doc C语言面试题大汇总.doc 计算机专业必备笔试面试锦囊.doc 笔试.rar 面试题集合.zip C语言面试题大汇总1.doc 面试题集合 java面试...
华勤java笔试题 最近需要从文本中抽取结构化信息,用到了很多github上的包,遂整理了一下,后续会不断更新。 很多包非常有趣,值得收藏,满足大家的收集癖! 如果觉得有用,请分享并star,谢谢! 涉及内容包括:中...
2018秋招java笔试题 Java Review 1. 数据结构和算法 红黑树 代码: ) 图解: 2. 面试题 2021.4.10 英礡Improbable笔试题 (2021 Improbable Intern Online Test) 括号匹配 约瑟夫环 2021.03.31 华为校园招聘软件笔试题...
│ JAVA笔试题(上海释锐).pdf │ MIME简介.txt │ SCJP试题详解.pdf │ SQL面试题_心灵深处.htm │ Struts+Hibernate+Spring轻量级J2EE企业应用实战.pdf │ Struts中文手册.pdf │ Struts配置文件详解.txt │ 上海...
初级java笔试题编程面试大学 我最初创建它是为了成为一名软件工程师的学习主题的简短待办事项列表,但它增长到您今天看到的大列表。 完成这个学习计划后,! 你可能不需要像我一样学习。 总之,你需要的都在这里。 ...
字节跳动java笔算法试题 程序员应该访问的最佳网站 一些对程序员有用的网站。 在学习 CS 时,您必须了解一些有用的网站,以便随时了解最新信息,以便更好地掌握技术并学习新事物。 这是您应该访问的一些网站的非详尽...
java笔试题算法印尼OSS项目列表 想做出贡献吗? 寻找灵感来源? 想在社区中合作吗? 查看以下列表。 注意:你想把你的 OSS 项目放到这里吗? 请发送 PR(拉取请求)。 请保持字母顺序。 公司OSS项目 以下是由公司...
亚信java笔试题 JobInterviewInAction this is the collection of my codes for job interview 面试的公司 寒武纪:一面挂,(岗位不匹配,自己一个做软件的,问我计算机组成原理,高性能计算,我当时心都凉了) ...
java笔试题算法基于朴素贝叶斯的文本分类 方法 开发环境 我们的项目将使用Java编写,使用lucene进行文本分析,使用log4j记录统计信息,以便我们可以专注于不同文本分类算法的实现。 这个软件是如何工作的? 我们的...
字节跳动java笔算法试题 初创企业 程序员应该访问的最佳网站 一些对程序员有用的网站。 在学习 CS 时,您必须了解一些有用的网站,以便随时了解最新信息,以便更好地掌握技术并学习新事物。 这是您应该访问的一些...
软件大数据面试笔试复习资料面试技巧HR面试常问的问题总结面试笔试题整理资料合集: 01大数据面试复习----Java基础---集合类、多线程、JVM 02大数据面试复习----画重点----常问问题分析 03大数据面试复习----画重点--...
│ JAVA笔试题(上海释锐).pdf │ MIME简介.txt │ SCJP试题详解.pdf │ SQL面试题_心灵深处.htm │ Struts+Hibernate+Spring轻量级J2EE企业应用实战.pdf │ Struts中文手册.pdf │ Struts配置文件详解.txt │ 上海...
│ JAVA笔试题(上海释锐).pdf │ MIME简介.txt │ SCJP试题详解.pdf │ SQL面试题_心灵深处.htm │ Struts+Hibernate+Spring轻量级J2EE企业应用实战.pdf │ Struts中文手册.pdf │ Struts配置文件详解.txt │ 上海...