java面试编程题、
该公司笔试题就1个，要求在10分钟内作完。题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
请问这题怎么做呢
--------------------编程问答-------------------- 找找全排列的算法就行了 --------------------编程问答-------------------- 楼主为什么不考虑数学里排列组合思想呢。
因为今天太过沉迷游戏，不想了，先帮你顶下吧
--------------------编程问答--------------------
先顶，明天再来
--------------------编程问答--------------------
给你一个地址，纯算法的，试试看：http://topic.csdn.net/u/20100514/10/f7c34142-0718-4c59-8195-a711a8fd98e1.html
如果算法的不算很牛看不懂的话，试试下面的全排列吧：
--------------------编程问答--------------------
public class PrintNumber {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
List<String> list2 = new ArrayList<String>();
for (int i = 1; i <= 5; i++) {
list1.add("" + i);
}
list1.add("" + 2);
while (list2.size() < 360) {
Collections.shuffle(list1);
StringBuffer sb = new StringBuffer();
for (int i = 0; i < list1.size(); i++) {
sb.append(list1.get(i));
}
if (list2.contains(sb.toString()) == false) {
list2.add(sb.toString());
}
}
int num = 0;
for (String str : list2) {
if (!str.matches("\\d\\d4\\d+") && !str.matches("\\d*35\\d*")
&& !str.matches("\\d*53\\d*")) {
System.out.println(str);
num++;
}
}
System.out.println("总共输入" + num + "个数");
}
}
--------------------编程问答--------------------
所有组合情况列出来，再除掉不满足的情况。
--------------------编程问答--------------------
--------------------编程问答-------------------- 先mark下！！
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.ArrayList;
import java.util.HashSet;
public class Test{
public static void main(String[] args){
print();
}
public static void print(){
String regex = "([1-6])(?!\\1)([1-6])(?!\\1|\\2|4)([1-6])(?!\\1|\\2|\\3)([1-6])(?!\\1|\\2|\\3|\\4)([1-6])(?!\\1|\\2|\\3|\\4|\\5)([1-6])$";
Pattern pattern = Pattern.compile(regex);
Matcher matcher = null;
HashSet<String> set = new HashSet<String>();
for(int i = 123456 ; i <= 654321 ; i ++){
String content = i + "";
matcher = pattern.matcher(content);
if(!matcher.matches()){
continue;
}
String regex1 = "35";
content = content.replace("6","2");
Pattern pattern1 = Pattern.compile(regex1);
matcher = pattern1.matcher(content);
if(!matcher.find()){
set.add(content);
}
}
System.out.println(set.size());
for(String s : set){
System.out.println(s);
}
}
}
晚上看看 --------------------编程问答-------------------- 学习了 --------------------编程问答-------------------- 学习··· --------------------编程问答-------------------- --------------------编程问答-------------------- 这个你就需要首先考虑这个算法，即先试着排排这些数的顺序 --------------------编程问答-------------------- JAVA全排列，这题还蛮常见的 --------------------编程问答-------------------- 非常好 --------------------编程问答-------------------- 用正则表达式。。。想给个例子的，貌似java正则表达式还不会。。只在javascript中用了。。。学习下再来 --------------------编程问答--------------------
public class TestAllsort {
public static void main(String[] args) {
TestAllsort ta =new TestAllsort();
ta.sortAll();
}
public void sortAll(){
for(int k=0;k<100000;k++){
int [] arr = new int[5];
int [] b ={0,0,0,0,0};
for(int i=0;i<5;i++){
arr[i] = (int)((Math.random()*5)+1);
}
if(arr[2]==4){
continue;
}
for(int i=0;i<4;i++){
if(arr[i]==3&&arr[i+1]==5||arr[i]==5&&arr[i+1]==3){
continue;
}else{
for(int j=0;j<5;j++){
if(b[j]!=arr[j]){
b[j]=arr[j];
System.out.print(b[j]+" ");
}
}
}
System.out.println();
}
}
}
}
能达到要求，不过程序不简洁，呵呵。。。只有这水平了。。。。不要介意哈，还得加油 --------------------编程问答-------------------- --------------------编程问答-------------------- package com.wrox.context.chat;
import java.util.HashSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class RexTest {
public static void eamilTest(String rouse){
String rex ="\\w+@\\w+[.]\\w+";
Pattern p = Pattern.compile(rex);
Matcher m = p.matcher(rouse);
if(m.find()){
System.out.println("符合要求");
}
else{
System.out.println("不符合要求");
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//Regex rex = new Regex();
//String url = "http://sina.com";
//String rex = "@http://.*?sina.*?\.com";
/* String parentString = "abcde";
// String sonString ="cd";
String rex ="[a-z].*cd.*";
Pattern p = Pattern.compile(rex);
Matcher m = p.matcher(parentString);
boolean b = m.find();
System.out.println(b);
*/
/*String root = "li03wei@163.com";
//String rex = "\\w+@\\w+[.]\\w+";
eamilTest(root);*/
/* String s = "xxx==yyy==zzz==";
//String rex = "(?i)([^=]+)={2,}([^=]+)";
String rex = "(?i)([^=]+)={2,}([^=]+)";
// String rex = "(?i)//w+.*={2,}//w+";
Pattern p = Pattern.compile(rex);
Matcher m = p.matcher(s);
System.out.println(m.find());
*/
String rex ="[1-5][1-5][1-3[5]][1-5][1-5]";
Pattern p = Pattern.compile(rex);
Matcher m = null;
HashSet<String> hs = new HashSet<String>();
for(int i=12345;1<=54321;i++){
String context = i + "";
m=p.matcher(context);
if(!m.matches()){
continue;
}
String rex1="35|53";
Pattern p1 = Pattern.compile(rex1);
Matcher m1 = p1.matcher(context);
if(!m1.find()){
hs.add(context);
}
for(String s:hs){
System.out.println(s);
}
}
}
}
--------------------编程问答-------------------- 请问为什么这楼要判断if(b[j]!=arr[j])这个呢？是去除零还是什么？应该不会产生零吧？我不才指导下吧 --------------------编程问答--------------------
--------------------编程问答-------------------- 我觉得吧直接写个for循环，生成结果，再用那两条规则作下判断，所有结果存入hashMap前先判断有么有。
static int[] bits = new int[] { 1, 2, 3, 4, 5 };
/**
* @param args
*/
public static void main(String[] args) {
sort("", bits);
}
private static void sort(String prefix, int[] a) {
if (a.length == 1) {
System.out.println(prefix + a[0]);
}
for (int i = 0; i < a.length; i++) {
sort(prefix + a, copy(a, i));
}
}
private static int[] copy(int[] a,int index){
int[] b = new int[a.length-1];
System.arraycopy(a, 0, b, 0, index);
System.arraycopy(a, index+1, b, index, a.length-index-1);
return b;
}
最后再输出。 --------------------编程问答-------------------- 6位全排列不算多。
System.out.println("512234");
System.out.println("412345");
...
跟考官说这是最快的方法。 --------------------编程问答-------------------- 不用怎么动脑的算法：
public class test {
public static void main(String[] args) {
long n = 0;
for (int i0=1;i0<=6;i0++) //1
for (int i1=1;i1<=6;i1++) //2
for (int i2=1;i2<=6;i2++) //2
if (i2>i1)
for (int i3=1;i3<=6;i3++) //3
for (int i4=1;i4<=6;i4++) //4
if (i4!=3)
for (int i5=1;i5<=6;i5++) //5
if ((i5!=i3+1)&&(i5!=i3-1)&&(i5-i4)*(i5-i3)*(i5-i2)*(i5-i1)*(i5-i0)*(i4-i3)*(i4-i2)*(i4-i1)*(i4-i0)*(i3-i2)*(i3-i1)*(i3-i0)*(i2-i0)*(i1-i0)!=0) {
n++;
char[] str = new char[6];
str[i0-1] = '1';
str[i1-1] = '2';
str[i2-1] = '2';
str[i3-1] = '3';
str[i4-1] = '4';
str[i5-1] = '5';
System.out.println("<"+n+"> ");
System.out.println(str);
}
}
} --------------------编程问答--------------------
+1 我觉得这个不错。 --------------------编程问答--------------------
虽然没验证，但还是顶一下正则表达式的思路。 --------------------编程问答-------------------- 7楼的错误在于, 原始的126543, 162543 算成不同的方案，而把6转化成2以后的122543, 122543是一样的。
这样得到的结果比正确答案要多出不少重复解。
正则表达费时费力，如果只有10分钟做题，最好别用。另外从时间复杂度来说也是比较慢的方案。 --------------------编程问答-------------------- --------------------编程问答--------------------
+1 另外给别人看你的代码也不好看懂。 --------------------编程问答--------------------
这么多for循环，晕啊 --------------------编程问答-------------------- 不用递归减少overhead嘛。 --------------------编程问答-------------------- 找找全排列的算法就行了 --------------------编程问答-------------------- --------------------编程问答--------------------
--------------------编程问答-------------------- 运行结果
public class T12345 {
private int[] ns = {1, 2, 3, 4, 5};
private int nsIndex = 0;
/**
* 12345
* 21345
* 23145
* 23415
* 23451
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
new T12345().lunch1();
}
public void lunch() {
if(ns[ns.length-1] == 5) return;
if(ns[2]==4) {
moveNext();
lunch();
return;
}
if(l35()) {
return;
}
print();
moveNext();
lunch();
}
private boolean l35() {
// TODO Auto-generated method stub
int index = 0;
for (int i = 0; i < ns.length; i++) {
if(ns[i]==3||ns[i]==5) {
index = i;
break;
}
}
if(index == ns.length-1) return false;
if(index == 0) {
if(ns[index+1]==3||ns[index+1]==5) return true;
return false;
}
if(ns[index-1]==5||ns[index+1]==5||ns[index-1]==3||ns[index+1]==3) return true;
return false;
}
private void lunch1() {
// TODO Auto-generated method stub
if(ns[ns.length-1] == 1) {
lunch();
return;
}
if(ns[2]==4) {
moveNext();
lunch1();
return;
}
print();
moveNext();
lunch1();
}
public void moveNext() {
if(nsIndex == ns.length-1) nsIndex = 0;
int temp = ns[nsIndex];
ns[nsIndex] = ns[nsIndex+1];
ns[nsIndex+1] = temp;
nsIndex++;
}
public void print() {
for(int n : ns) {
System.out.print(n);
}
System.out.println();
}
}
12345
21345
23145
34251
34521
34512
--------------------编程问答-------------------- 楼上 人家说的是 122345 不是 12345 --------------------编程问答-------------------- 循环10000次求随机的哥们很值得鼓励 哈哈 --------------------编程问答-------------------- 解题思路：我们把两个2区分对待，比如我们说一个2是正常的，另一个是“假2”.首先对 1,2,3,4,5 这五个数进行全排列，然后找到全排列后2的位置（例如34251,2的位置为3），然后将剩余的“假2”插到2后面的各个位置上！ 3和5不相邻更容易了！！！！ --------------------编程问答-------------------- 两个2保证第一个2的位置小于第二个2的位置就不会重复。 --------------------编程问答-------------------- String str = "[0-5][0-5][0-3[5]][0-5][0-5]";
Pattern p = Pattern.compile(str);
String context = "";
for(int i=12345; i<54321;i++){
context = i + "";
Matcher m = p.matcher(context);
if(!m.find()){
continue;
}
String str2 = "35|53";
Pattern p2 = Pattern.compile(str2);
Matcher m2 = p2.matcher(context);
if(!m2.find()){
System.out.println(context);
} --------------------编程问答-------------------- package test.play;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ListAll {
/**
* 用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位
* ，"3"与"5"不能相连。
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char arr[] = { '1', '2', '2', '3', '4', '5' };
List<Integer> lst = new ArrayList<Integer>();
int min = 122345;
int max = 543221;
for (min = 122345; min <= max; min++) {
char temp[] = String.valueOf(min).toCharArray();
char mArr[] = Arrays.copyOf(temp, temp.length);
Arrays.sort(mArr);
if (new String(arr).equals(String.valueOf(mArr))
&& temp[2] != arr[4] && !String.valueOf(min).contains("35")
&& !String.valueOf(min).contains("53")) {
lst.add(min);
}
}
for (Integer i : lst) {
System.out.println(i);
}
}
}
--------------------编程问答-------------------- package com.chang.test;
import java.util.ArrayList;
import java.util.List;
public class TestCsdn1 {
static List l = new ArrayList();
public TestCsdn1() {
}
public static void add(String n) {
List tmpl = new ArrayList();
for (int i = 0; i < l.size(); i++) {
String s = (String) l.get(i);
s = n + s;
tmpl.add(s);
String tmp = s;
s = change(s);
while (!s.equals(tmp)) {
tmpl.add(s);
s = change(s);
}
}
l.clear();
l.addAll(tmpl);
}
private static String change(String s) {
char a[] = s.toCharArray();
char b = a[0];
s = s.substring(1, s.length()) + b;
return s;
}
private static void printOut() {
int count = 0;
for (int i = 0; i < l.size(); i++) {
String s = (String) l.get(i);
if ((s.indexOf("3") + 1 == s.indexOf("5"))
|| (s.indexOf("3") - 1 == s.indexOf("5"))
|| (s.indexOf("4") == 2)) {
continue;
}
count++;
System.out.println(l.get(i));
}
System.out.println(l.size());
System.out.println(count);
}
public static void main(String[] args) {
l.add("22");
add("1");
add("5");
add("4");
add("3");
printOut();
}
}
--------------------编程问答-------------------- 我也贴一个我自己的
--------------------编程问答-------------------- private String[] b = new String[] { "1", "2", "2", "3", "4", "5" };
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Title:全排列算法
*
* @author xxxxx
*/
public class FullArrayProblem {
//将NUM设置为待排列数组的长度即实现全排列
private int NUM = 6;
private int count;
private List<String> lresult;
/**
* 递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列
*
* @param datas
* @param target
*/
private void sort(List<String> datas, StringBuffer target) {
if (target.length() == NUM) {
String strTarget = target.toString();
if (!lresult.contains(strTarget)&&!strTarget.matches("\\d\\d4\\d+")
&&!strTarget.matches("\\d*35\\d*")&&!strTarget.matches("\\d*53\\d*"))
{
System.out.println(target.toString());
lresult.add(strTarget);
count++;
}
return;
}
for (int i = 0; i < datas.size(); i++) {
List<String> newDatas = new ArrayList<String>(datas);
StringBuffer newTarget = new StringBuffer(target);
newTarget.append(newDatas.get(i));
newDatas.remove(i);
sort(newDatas, newTarget);
}
}
public static void main(String[] args) {
String[] datas = new String[] { "1", "2", "2", "3" , "4" , "5" };
FullArrayProblem t = new FullArrayProblem();
t.lresult = new ArrayList<String>();
t.sort(Arrays.asList(datas), new StringBuffer());
System.out.println("TOTALNUMBER:" + t.count);
}
}
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet<String> set = new TreeSet<String>();
public static void main(String[] args) {
new RandomNum().start();
}
private void start() {
// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
// Begin to depth search.
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
// Print result treeset.
Iterator<String> it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for (int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
// restore the result value and visited value after listing a node.
result = result.substring(0, result.length() - 1);
visited[startIndex] = false;
} --------------------编程问答-------------------- private String[] b = new String[] { "1", "2", "2", "3", "4", "5" };
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet<String> set = new TreeSet<String>();
public static void main(String[] args) {
new RandomNum().start();
}
private void start() {
// Initial the map a[][]
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
// Begin to depth search.
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
// Print result treeset.
Iterator<String> it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
// Filt the duplicate value.
set.add(result);
}
for (int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
// restore the result value and visited value after listing a node.
result = result.substring(0, result.length() - 1);
visited[startIndex] = false;
} --------------------编程问答-------------------- 还 真的不会... --------------------编程问答-------------------- 首先，自己封装了一个类，实现了全排列。这里设置了一个接口，要求继承它的子类，实现这个接口，以达到排列要求的限制
abstract class PaiLei {
private int count;
public int count() {
return count;
}
/**
* 排列算法
* @param list 排序数据
* @param k 移动点
* @param m 数据个数
*/
public void paiLie(int list[], int k, int m) {
if (k == m) {
if (dataFilter(list)) {
count++;
System.out.println(Arrays.toString(list));
}
} else {
for (int i = k; i < m; i++) {
swap(list, k, i);
paiLie(list, k + 1, m);
swap(list, k, i);
}
}
}
/**
* 限制规则方法
* @param list 排列数组
* @return 是否通过
*/
public abstract boolean dataFilter(int[] list);
private void swap(int[] datas, int i, int j) {
int t = datas[i];
datas[i] = datas[j];
datas[j] = t;
}
}根据题目的要求，写了一个测试类，并采用匿名类的方式，实现。
public static void main(String[] args) {
int list[] = { 1, 2, 2, 3, 4, 5};
PaiLei pl = new PaiLei() {
@Override
public boolean dataFilter(int[] list) {
int index = -1;
int n = list.length;
if (n > 3 && list[2] == 4) {
return false;
}
for (int i = 0; i < n; i++) {
if (list[i] == 3) {
index = i;
break;
}
}
return index == -1 ? true : !((index < n - 1 && list[index+1] == 5) ||
(index > 0 && list[index - 1] == 5));
}
};
pl.paiLie(list, 0, list.length);
System.out.println("count : " + pl.count());
}
--------------------编程问答--------------------
--------------------编程问答--------------------
楼上很好很强大，是非常通用并且优雅的解决方法。
--------------------编程问答--------------------
其实就是递归穷举解决方案。当然也有别的方案。 --------------------编程问答--------------------
public class Test {
static int count = 0;
static List list_all = new ArrayList();
static String regex = "35|53";
static Pattern pattern = Pattern.compile(regex);
/**
* 递归
*/
public static List test(ArrayList list,String sbu){
for(int i=0;i<list.size();i++){
String sbu_temp = sbu + list.get(i);
ArrayList list1 = (ArrayList) list.clone();
list1.remove(i);
if(list1.size()==0){
Matcher matcher = pattern.matcher(sbu_temp);
if(!list_all.contains(sbu_temp) && sbu_temp.indexOf("4")!=2 && !matcher.find()){
System.out.println(sbu_temp);
System.out.println(++count);
list_all.add(sbu_temp);
}
}else{
test(list1,sbu_temp);
}
}
return list_all;
}
public static void main(String[] args) {
ArrayList list = new ArrayList(6);
list.add(1);
list.add(2);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
test(list,"");
}
}
--------------------编程问答--------------------
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
--------------------编程问答--------------------
1524315234
12543
12345
13254
13245
14523
14325
21543
21345
25134
25143
23145
23154
24513
24315
31245
31254
31542
31524
32154
32145
32514
32541
34152
34125
34215
34251
34512
34521
41523
41325
42513
42315
43152
43125
43215
43251
45132
45123
45213
45231
51243
51234
51342
51324
52134
52143
52314
52341
54132
54123
54213
54231
54312
54321
共：56
--------------------编程问答-------------------- if (pre.length() == a.length) {
if (pre.charAt(2) != '4'&&!pre.contains("35")&&!pre.contains("53")) {
index++;
System.out.println(pre);
}
}
if (len < 1)
return;
for (int i = 0; i < len; i++) {
char temp = a[i];
swap(a, i, len - 1);
pailie(pre + temp, a, len - 1);
swap(a, len - 1, i);
}
补充：Java , Java SE
