- 浏览: 347873 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
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 1267约瑟夫出圈问题 两种方法实现,数据和链表 n个人围成一个圈,一 ... -
int转byte[],byte[]转int
2009-10-10 14:51 1584public byte[] intToByte(int i) ... -
不使用任何循环和递归,输出打印n条(n>1) "Hello World"
2009-07-07 21:09 1049String str="Hello"; ... -
金额转换,阿拉伯数字的金额转换成中国传统的形式如:(¥1011)->(一千零一拾一元整)输出。
2009-06-17 22:29 2468package test.money; import j ... -
求出现次数最多的那个字母及次数,如有多个重复的则都求出。〔金山公司面试题〕
2009-06-17 22:28 1570import java.util.ArrayList; ... -
编程实现统计文本文件中某个单词的出现频率,并输出统计结果
2009-06-17 21:55 3156用HashMap来解决假设单词不存在跨行的,每个单词用,. ; ... -
创建一个静态方法,给它传入一个对象,请循环的打印出该对象所在类的类名和所实现的方法名(华为笔试)
2009-06-17 20:42 2041import java.lang.reflect.*; ... -
在ORACLE大数据量下的分页解决方法
2009-06-17 19:05 1649在ORACLE大数据量下的分页解决方法。 一般用截取ID方法 ... -
编写一个截取字符串的函数
2009-06-17 11:34 963编程:编写一个截取字符串的函数,输入为一个字符串和字节数,输出 ... -
用插入法进行排序
2009-06-17 10:34 1255import java.util.*; class I ... -
用JAVA SOCKET编程,读服务器几个字符,再写入本地显示
2009-06-17 09:41 1200Server端程序: import java.net.*; ... -
java实现B树(二叉树)插入,删除
2009-06-17 07:50 2675B树(二叉搜索树)定义: 1)、每个非叶子节点至多有两个子节点 ... -
java读取(删除)文件夹下的所有文件夹和文件
2009-06-16 15:30 1777import java.io.FileNotFoundExce ... -
500人(小孩)围成一个圈,数到3的人下个人就从1开始数,问最后一个人的位置在那里?
2009-06-16 14:57 1816小孩玩游戏,手拉手围成 ... -
写一个java程序实现线程连接池的功能
2009-06-16 14:44 1210线程池: import java.util.lin ... -
用java写二叉树算法,实现添加数据形成二叉树功能,并打印
2009-06-16 14:27 876public class MyTest { private ...
相关推荐
在IT行业中,笔试是许多著名公司挑选优秀人才的重要环节,特别是大公司,它们通常会设置一系列严谨的测试来评估候选人的技术能力、逻辑思维和问题解决技巧。这份"著名IT公司笔试题笔试题库"正是为准备进入IT行业的...
这个压缩包可能包含了当年方正公司Java软件工程师笔试的所有题目,包括但不限于Java语言基础、JVM原理、JavaEE相关技术、数据结构与算法等内容。考生可以通过分析这些题目来了解方正对Java工程师的技能期望,并进行...
标题 "46家著名IT公司的笔试题" 涵盖了大量的技术知识点,这些知识点是IT行业,特别是互联网领域招聘过程中的常见考核内容。这包括但不限于编程语言、算法与数据结构、操作系统、网络、数据库、软件工程、计算机基础...
这个名为"46家著名IT公司的笔试题.rar"的压缩包文件显然包含了多个著名IT公司招聘过程中的笔试题目。这些题目通常涵盖了编程、算法、计算机网络、操作系统、数据结构、数据库管理、软件工程等多个IT领域的核心知识。...
阿里软件JAVA笔试题是阿里巴巴公司为招聘软件开发工程师所设计的一份笔试题目,涵盖了JAVA语言、数据结构、算法、设计模式、数据库等多方面的知识点。 本题目共有15道题目,涵盖了以下几个方面: 逻辑推理 1. 甲...
第二份文档《华为Java笔试题.doc》则专门针对华为公司的Java笔试,可能包括了华为对Java技术栈的特定要求,比如JVM内存模型、Spring框架的应用、数据库操作、网络编程等。解答这类题目有助于理解企业对于Java开发者...
【标题】:“各公司java笔试题”所涵盖的Java编程知识点详解 【描述】:这份资源集合了2012年和2013年北京、上海等地一些知名IT公司的Java笔试题目,其中包括用友公司和亿阳信通等企业的考题。这些题目无疑是Java...
【标题】:“软件公司——华信笔试题——供大家参加笔试时参考” 这是一份与软件公司华信相关的笔试题目集锦,旨在为准备参加华信或其他类似软件公司笔试的求职者提供参考资料。这类题目通常涵盖了计算机科学和技术...
网龙最新秋招Java笔试题 本文档是对网龙最新秋招Java笔试题的知识点总结。通过对试题的分析,我们可以总结出以下知识点: 1. 计算机网络基础知识: * PING 命令的实现机制:PING 命令发出的是 ICMP 请求报文,而...
《46家著名IT公司笔试题》是一本集合了众多知名IT企业的面试笔试题目的电子书籍,对于准备进入IT行业的求职者来说,是一份极具价值的学习资料。这本书籍旨在帮助应聘者了解并熟悉IT公司的面试流程,提升自身的技术...
在准备进入世界著名公司的工作之旅时,面试和笔试环节无疑是最关键的部分。这些环节是公司评估候选人能力、技能和潜力的重要方式。为了帮助你更好地应对这些挑战,了解并熟悉各类公司的面试笔试题库是非常有益的。...
"北京尔宜居科技有限公司Java笔试题" 这个标题表明这是一个与Java编程相关的考试题目集,可能是该公司在招聘Java开发人员时所使用的面试或笔试材料。这通常涵盖Java语言的基础知识、进阶特性、面向对象编程概念、多...
【标题】:“北京宏景世纪软件股份有限公司Java笔试题”涉及的Java知识点解析 【描述】:本题目来源于北京宏景世纪软件股份有限公司的Java程序员笔试环节,这通常包括了对Java基础知识、编程能力、面向对象设计以及...
Java笔试题是评估应聘者技术水平和解决问题能力的重要环节,涵盖了基础语法、面向对象、数据结构、算法、JVM原理、多线程、网络协议、数据库、框架应用等多个方面。这份"java笔试题(收集了各大公司的笔试题)"资源...
【南瑞笔试题集合】是针对应届毕业生设计的一系列笔试试题,旨在考察应聘者在IT领域的基础知识、专业技能和解决问题的能力。南瑞,作为中国电力行业的重要企业,其笔试环节通常涵盖计算机科学、软件工程、电力系统等...
通过对"各个著名公司的笔试题(有答案)"的深入学习,你可以对不同公司的招聘标准有更直观的理解,同时提升自己的技术实力。 首先,编程语言是IT行业的基础,包括Java、Python、C++、C#等,可能会出现在笔试题中。...
【标题】:“北京四维图新科技股份有限公司Java笔试题”涉及的Java知识点解析 【描述】:本题目来源于北京四维图新科技股份有限公司的Java笔试,通常这样的试题集会涵盖Java语言的基础、进阶以及实际应用等多个方面...
本资源集合了当年各大IT公司的面试和笔试试题,涵盖了Java语言的各种知识点,旨在帮助应聘者提升自己的技能水平,成功通过面试。 首先,Java面试通常会涉及到以下几个核心领域: 1. **Java基础知识**:包括Java...
【标题】:“诺明软件有限公司Java笔试题”通常是一份由诺明软件有限公司设计的用于评估应聘者Java编程技能的测试题目集。这样的试题旨在检验求职者的编程基础、面向对象设计、异常处理、集合框架、多线程、IO流、...