原题:
一著名软件公司的java笔试算法题!算法程序题: 该公司笔试题就1个,要求在10分钟内作完。 题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
/************************************************/第一时间我想到的是循环(可以改写成递归调用),虽然我也知道这不是最好的,可是第一时间近来的就是这个想法,挥之不去了。
实现起来如下:
public static void main(String args[]) {
int a[] = { 1, 2, 2, 3, 4, 5 };
StringBuffer sb = new StringBuffer(); Date date = new Date();
SimpleDateFormat sf = new SimpleDateFormat("yyMMddHHmmss:SSS");
System.out.println(sf.format(date));
for (int i = 0; i < 6; i++)// --------------------------------------1
{
StringBuffer result = new StringBuffer();
result.append( a[i]);
for (int j = 0; j < 6; j++)// ----------------------------------2
{
if (j == i)
continue;
result.append( a[j]);
for (int m = 0; m < 6; m++)// ------------------------------3
{
if (m == i || m == j)
continue;
result.append( a[m]);
for (int n = 0; n < 6; n++)// --------------------------4
{
if (n == i || n == j || n == m)
continue;
result.append( a[n]);
for (int o = 0; o < 6; o++)// ----------------------5
{
if (o == i || o == j || o == m || o == n)
continue;
result.append( a[o]);
for (int p = 0; p < 6; p++)// ------------------6
{
if (p == i || p == j || p == m || p == n
|| p == o)
continue;
result.append( a[p]);
if (result.charAt(2) != '4'
&& result.indexOf("35") < 0) {
if (sb.indexOf(result.toString()) < 0) {
//System.out.println(result);
sb.append(result + "|");
}
//System.out.println(result);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
} }
date = new Date();
System.out.println(sf.format(date));
}
大家说如果遇到这种情况我应该,硬着头皮实现这个想法吗?另外帮忙看看那两个时间输出有没有更好的方法。谢谢了!
一著名软件公司的java笔试算法题!算法程序题: 该公司笔试题就1个,要求在10分钟内作完。 题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
/************************************************/第一时间我想到的是循环(可以改写成递归调用),虽然我也知道这不是最好的,可是第一时间近来的就是这个想法,挥之不去了。
实现起来如下:
public static void main(String args[]) {
int a[] = { 1, 2, 2, 3, 4, 5 };
StringBuffer sb = new StringBuffer(); Date date = new Date();
SimpleDateFormat sf = new SimpleDateFormat("yyMMddHHmmss:SSS");
System.out.println(sf.format(date));
for (int i = 0; i < 6; i++)// --------------------------------------1
{
StringBuffer result = new StringBuffer();
result.append( a[i]);
for (int j = 0; j < 6; j++)// ----------------------------------2
{
if (j == i)
continue;
result.append( a[j]);
for (int m = 0; m < 6; m++)// ------------------------------3
{
if (m == i || m == j)
continue;
result.append( a[m]);
for (int n = 0; n < 6; n++)// --------------------------4
{
if (n == i || n == j || n == m)
continue;
result.append( a[n]);
for (int o = 0; o < 6; o++)// ----------------------5
{
if (o == i || o == j || o == m || o == n)
continue;
result.append( a[o]);
for (int p = 0; p < 6; p++)// ------------------6
{
if (p == i || p == j || p == m || p == n
|| p == o)
continue;
result.append( a[p]);
if (result.charAt(2) != '4'
&& result.indexOf("35") < 0) {
if (sb.indexOf(result.toString()) < 0) {
//System.out.println(result);
sb.append(result + "|");
}
//System.out.println(result);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
}
result.setLength(result.length()-1);
} }
date = new Date();
System.out.println(sf.format(date));
}
大家说如果遇到这种情况我应该,硬着头皮实现这个想法吗?另外帮忙看看那两个时间输出有没有更好的方法。谢谢了!
3个条件都满足则加入到List并打印出来,任何一个不满足则进行下一个循环。办法很笨,不过很好实现,10分钟估计搞的定。
{
int [] s={1,2,3,4,5};
int t =0;
for (int i=12345;i<=54321;i++)
{
String str =i+"";
int l = str.length();
boolean b = true;
for (int k=0;k<l-1;k++)
{
char [] c = str.toCharArray();
if ((int)c[k]+(int)c[k+1] ==8 )
{
b = false;
break;
}
if (c[2] == 4)
{
b = false;
break;
}
}
if (b)
{
t++;
System.out.println(str);
}
}
System.out.println("共:"+t);
}
先封装成Integer,再用个集合类,如ArrayList
再判断
这样做应该很简单
public static void main(String[] args) {
String[] src = {"1","2","2","3","4","5"};
List<Object[]> list = new ArrayList<Object[]>();
getPerm(src,list);
Set<String> s = new HashSet<String>();
for(Object[] temp : list){
StringBuffer sb = new StringBuffer("");
for(int i = 0; i < temp.length; i ++){
sb.append(temp[i]);
}
String result = sb.toString();
if(result.charAt(2) != '4' && result.indexOf("35") == -1 && result.indexOf("53") == -1){
s.add(result);
}
}
for(String tmpS : s){
System.out.println(tmpS);
}
System.out.println("一共有[" + s.size() + "]个数据~");
} /** *************** 第一种方法:递归法 ******************************** */
/**
*
* 对array中的元素全排列,结果以数组的形式保存在list中
*
* @param array
*
* @param list
*
*/
public static void getPerm(Object[] array, List<Object[]> list) {
perm(array, 0, array.length, list);
} /**
*
* 用递归取排列数
*
* @param array
*
* @param m
*
* @param n
*
* @param list
*
*/ private static void perm(Object[] array, int m, int n, List<Object[]> list) {
if (array == null) {
list = new ArrayList<Object[]>(); return;
} // 用array的copy进行排列
Object[] _array = Arrays.copyOf(array, array.length); if (m < n - 1) {
perm(_array, m + 1, n, list); for (int i = m + 1; i < n; i++) {
Object t = _array[m];
_array[m] = _array[i];
_array[i] = t; perm(_array, m + 1, n, list);
t = _array[m];
_array[m] = _array[i];
_array[i] = t;
}
} else {
list.add(_array);
}
}结果:
312254
321524
325412
212543
125234
152324
123245
123254
251423
322145
431225
523241
312245
421325
212345
325421
315242
232145
125243
132524
341225
432251
322154
232154
132254
142325
431252
345221
413225
522134
451322
215243
512324
512423
213245
232451
321254
345212
231452
341252
512432
243152
213254
342251
321245
243215
223415
241523
342512
123425
342215
152423
425231
251324
432215
245123
422513
225143
243125
342521
252314
322415
422315
342125
432512
215234
245132
322514
225134
221345
345122
231425
152342
225431
152243
321542
412523
521234
123452
251342
521324
432521
322541
242513
342152
431522
521342
152234
432125
521243
152432
543122
225413
223451
243251
251432
125432
122345
122543
425123
543221
252341
143252
252413
512243
252143
245213
451232
542213
132452
325241
513242
125423
231245
521423
245231
542231
421523
425132
543212
321425
231542
521432
412325
452231
522413
231254
522314
425213
215432
145223
252431
143225
223145
145232
322451
232514
423251
541232
312452
321452
215423
252134
512234
223154
451223
231524
541223
522431
213452
325142
241325
542321
512342
423215
542312
542123
423125
522341
523124
413252
312425
522143
542132
452213
312524
132425
452312
312542
142523
325124
452123
251243
432152
513224
452132
232415
415223
213425
452321
523421
132245
523142
315422
541322
523214
341522
242315
221543
232541
325214
251234
132542
423152
415232
315224
523412
513422
一共有[198]个数据~
public static void main(String[] args) {
String[] src = {"1","2","2","3","4","5"};
//位移法
Set<String> ss = new HashSet<String>();
Object[] results = perm(src);
for(Object temp : results){
StringBuffer sb = new StringBuffer("");
if(!(temp instanceof Object[])){
continue;
}
Object[] tmp = (Object[])temp;
for(int i = 0; i < tmp.length; i ++){
sb.append(tmp[i]);
}
String result = sb.toString();
if(result.charAt(2) != '4' && result.indexOf("35") == -1 && result.indexOf("53") == -1){
ss.add(result);
}
}
for(String tmpS : ss){
System.out.println(tmpS);
}
System.out.println("一共有[" + ss.size() + "]个数据~");
}
/** ****************** 排列第二种方法:移位法 ********************** */ /**
*
* 不重复元素数组array中的元素全排列
*
* 非递归算法
*
* @param array
*
* @return
*
*/ public static Object[] perm(Object[] array) {
if (array == null || array.length <= 1) {
return array;
} Queue<ArrayWrapper> queue = new LinkedList<ArrayWrapper>();
int len = array.length;
int cnt = 0;
queue.offer(new ArrayWrapper(array, 0)); while (cnt < len) {
Object[] _array = array;
if (!queue.isEmpty()) {
ArrayWrapper _tmp = queue.poll();
_array = _tmp.getArray();
cnt = _tmp.getSign();
} for (int j = 0; j < len - cnt; j++) {
ArrayWrapper _aw = new ArrayWrapper(shiftLeft(_array,
len - cnt, j), cnt + 1);
queue.offer(_aw);
}
cnt++;
} int total = queue.size();
Object[] result = new Object[total]; for (int i = 0; i < total; i++) {
result[i] = queue.poll().getArray();
}
return result;
} /*
*
* 有序数组array中的左起m个元素左移n位,最高位回到最低位
*
*/
private static Object[] shiftLeft(Object[] array, int m, int n) {
if (array == null || array.length <= 1) {
return array;
} if (m <= 1) {
return array;
} int length = array.length;
Object[] _temp = new Object[length]; int _n = n % m;
System.arraycopy(array, _n, _temp, 0, m - _n);
System.arraycopy(array, 0, _temp, m - _n, _n);
System.arraycopy(array, m, _temp, m, length - m);
return _temp;
}/**
* array数组封装类,加了个标签sign
* @author Daniel
*
*/class ArrayWrapper{
private Object[] array;
private int sign; public ArrayWrapper(Object[] array,int sign){
this.array = array;
this.sign = sign;
} public Object[] getArray() {
return array;
} public int getSign() {
return sign;
}
}
char[] number = new char[] {'1', '2', '2', '3', '4', '5'};
perm(number, 0, number.length - 1);
}public static void perm(char[] n, int beg, int end) {
if (beg == end) {
String result = String.valueOf(n);
if (n[2] == '4') return;
if (result.contains("35") || result.contains("53")) return;
System.out.println(String.valueOf(n));
return;
}
for (int i = beg; i <= end; ++i) {
swap(n, beg, i);
perm(n, beg + 1, end);
swap(n, beg, i);
}
}public static void swap(char[] n, int a, int b) {
char temp = n[a];
n[a] = n[b];
n[b] = temp;
}
1、确实很笨
2、第一次见,十分钟IDE内搞定,若手写则搞不定。呵呵~
下次注意~ java2000_net 的两个方法不错,思路没有太多奇特的地方,但是都很好。大家应该都可以想的到。如果放开时间限制,我觉得还是应该从从人脑自己解决这种排列问题的方法中归纳总结出一套思路。然后再用程序去实现。
PS:大家好像都最终跑到递归这条路上来了,哈哈。
070618101852:421
070618101852:515
我也编了一个跟你的差不多,但是结果也不对。StringBuffer在这里很难用好。
static Set set = new HashSet();
static Set set1 = new HashSet();
public static void main(String args[])
{
char[] number = new char[] {'1', '2', '2', '3', '4', '5'};
perm(number, 0, number.length - 1);
f();
System.out.println(list.size()+" "+set.size());
System.out.println(set1.size());
}
public static void perm(char[] n, int beg, int end) {
if (beg == end) {
String result = String.valueOf(n);
if (n[2] == '4') return;
if (result.contains("35") || result.contains("53")) return;
//System.out.println(String.valueOf(n));
set.add(String.valueOf(n));
list.add(String.valueOf(n));
return;
}
for (int i = beg; i <= end; ++i) {
swap(n, beg, i);
perm(n, beg + 1, end);
swap(n, beg, i);
}
} public static void swap(char[] n, int a, int b) {
char temp = n[a];
n[a] = n[b];
n[b] = temp;
} static void f()
{
int [] s={1,2,2,3,4,5};
int t =0;
for (int i=122345;i<=543221;i++)
{
String str =i+"";
boolean b = true;
char[]c = str.toCharArray();
for (int k=1 ;k <c.length; k++)
{
if (c[k]> '5' || c[k] =='0' || c[2] == '4' || fun(str,c[k],'2'))
{
b = false;
break;
}
if (c[k-1]+c[k] == '3'+'5')
{
b = false;
break;
}
}
if (b)
{
t++;
set1.add(str);
System.out.print(str+" ");
if(t%10==0)
System.out.println();
}
}
System.out.println("共:"+t);
}
static boolean fun(String str,char c,final char cf)
{
int count=0;
for (char ch:str.toCharArray())
{
if (ch == c)
count++;
}
if (c == cf && count==2)
{
count =0;
}
return count>1?true:false;
}