随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

一著名软件公司的java笔试算法题的答案

本文为原创,如需转载,请注明作者和出处,谢谢!

    原题如下:用1、2、2、3、4、5这六个数字,用java写一个程序,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。

 解题思路:

    很明显,这是一个递归算法。我们可以排列将这6个数按从小到大的顺序排一下,如果是1,2,3,4,5,6,那么会有1*2*3*4*5*6= 6!=720个递增的数。但如果是1,2,2,3,4,5,那么在这720个数中一定会有相同的数对出现(由于在这6个数中只有两个数两同,也就是说,如果有重复的数,那么一定是一对数,如122345会出现两次)。

    排列的基本规则是分步进行。也就是说,要排列上面6个数,首先应该选择第一个数,这第一个数可以选择这6个数中的任意一个,如选择1.第二步是选择第二个数,这第二个数不能再选择已经选过的数,如1.因此,它只能从后面5个数中选择。如选择2。以此类推。

    我们也可以在程序中模拟这一过程。源程序如下:

public class test1
{
    
private int[] numbers = new int[]
    { 
123345 };
    
public int n;
    
private String lastResult = "";

    
private boolean validate(String s)
    {
        
if (s.compareTo(lastResult) <= 0)
            
return false;
        
if (s.charAt(2== '4')
            
return false;
        
if (s.indexOf("35">= 0 || s.indexOf("53">= 0)
            
return false;
        
return true;
    }

    
public void list(String index, String result)
    {
        
for (int i = 0; i < numbers.length; i++)
        {
            
if (index.indexOf(i + 48< 0)
            {
                String s 
= result + String.valueOf(numbers[i]);
                
if (s.length() == numbers.length)
                {
                    
if (validate(s))
                    {
                        System.out.println(s);
                        lastResult 
= s;
                        n
++;
                    }
                    
break;
                }
                list(index 
+ String.valueOf(i), s);
            }
        }
    }

    
public static void main(String[] args)
    {
        test1 t 
= new test1();
        t.list(
"""");
        System.out.println(
"总数:" + t.n);

    }
}


    其中list函数是这个算法的核心函数。index参数表示已经选择过的数,用numbers数组的索引表示。如index="012",表示numbers的前三个数已经被选择,也表示应该选择第四个数了,而这第四个数应该从后三个数中选择。result参数表示临时的数字组合(这个数字组合最多是5个数字,因为,如果到了6个数字,就表示已经有一个结果产生了)。在默认情况下index和result的值都是""。

    在validate中使用了  if (s.compareTo(lastResult) <= 0)进行判断,由于按这种方法进行排列,如果这6个数是递增给出的,那么排列的结果一定是递增的,但上述的6个数其中第2和第3个位置上都是2,因此,如果出现了上一个结果不小于当前结果的情况,一定是有重复了,因此,要将这部分数过滤出去。

使用1, 2, 2, 3, 4, 5的测试结果
122345
122543
123245
123254
123425
123452
125234
125243
125423
125432
132245
132254
132425
132452
132524
132542
142325
142523
143225
143252
145223
145232
152234
152243
152324
152342
152423
152432
212345
212543
213245
213254
213425
213452
215234
215243
215423
215432
221345
221543
223145
223154
223415
223451
225134
225143
225413
225431
231245
231254
231425
231452
231524
231542
232145
232154
232415
232451
232514
232541
241325
241523
242315
242513
243125
243152
243215
243251
245123
245132
245213
245231
251234
251243
251324
251342
251423
251432
252134
252143
252314
252341
252413
252431
312245
312254
312425
312452
312524
312542
315224
315242
315422
321245
321254
321425
321452
321524
321542
322145
322154
322415
322451
322514
322541
325124
325142
325214
325241
325412
325421
341225
341252
341522
342125
342152
342215
342251
342512
342521
345122
345212
345221
412325
412523
413225
413252
415223
415232
421325
421523
422315
422513
423125
423152
423215
423251
425123
425132
425213
425231
431225
431252
431522
432125
432152
432215
432251
432512
432521
451223
451232
451322
452123
452132
452213
452231
452312
452321
512234
512243
512324
512342
512423
512432
513224
513242
513422
521234
521243
521324
521342
521423
521432
522134
522143
522314
522341
522413
522431
523124
523142
523214
523241
523412
523421
541223
541232
541322
542123
542132
542213
542231
542312
542321
543122
543212
543221
总数:198


使用1,2, 3, 3, 4, 5的测试结果
123345
125433
132345
132543
133245
133254
133425
133452
143325
145233
152334
152343
152433
213345
215433
231345
231543
233145
233154
233415
233451
243315
245133
251334
251343
251433
312345
312543
313245
313254
313425
313452
315234
315243
315423
315432
321345
321543
323145
323154
323415
323451
325134
325143
325413
325431
331245
331254
331425
331452
331524
331542
332145
332154
332415
332451
332514
332541
341325
341523
342315
342513
343125
343152
343215
343251
345123
345132
345213
345231
413325
415233
423315
425133
431325
431523
432315
432513
433125
433152
433215
433251
451233
451323
451332
452133
452313
452331
512334
512343
512433
513234
513243
513324
513342
513423
513432
521334
521343
521433
523134
523143
523314
523341
523413
523431
541233
541323
541332
542133
542313
542331
543123
543132
543213
543231
543312
543321
总数:118

使用1, 3, 3, 3, 4, 5的测试结果

133345
313345
315433
331345
331543
333145
333154
333415
333451
343315
345133
433315
451333
513334
513343
513433
541333
543133
543313
543331
总数:20




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-10 09:19 银河使者 阅读(7647) 评论(11)  编辑  收藏 所属分类: javaalgorithm 原创

评论

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

请问index.indexOf(i + 48) < 0判断条件的作用是什么?
2008-05-10 12:10 | fengsuiyijing

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

index保存了当前数字串的索引,index.indexOf(i + 48) < 0就是判断当前的数字的索引是否在index中(由于给定的数字串有重复的数字,因此,只能使用索引来判断了),如果不在,就会认为这个数字还没有加到index中,如果存在了,说明这个数已经在数字串中了。


注:i+48 ,当i=0时,正好是数字0的ASCII,以此类推
2008-05-10 12:41 | 银河使者

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

你给出的想法和代码都很优秀,我觉得你对本题有两点非常独特的见解:1)你会使用字符索引来“组合”最后的字符串,而且几处用到的indexOf非常合理,也很巧妙;2)validate函数的使用,尤其是判断重复字符串上面,很难想到。我建议你还能去网上找到两个版本的程序,其中一个也是用递归,另一个是图的思想,一定要做多组测试,因为网上好多的程序都是错误的,你这几组的数据都是对的。

补:在“注”中有笔误,当i=0的时候,i+48是0的ASCII,因为你index中存的毕竟是索引,是位置嘛,所以是从0开始的
2008-05-16 10:32 | dreamingnest

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

to dreamingnest

谢谢提醒,是写错了,i+48,从数字0开始。改过来了。如果有更好的解决方案,请跟贴。谢谢!
2008-05-16 10:49 | 银河使者

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

public class DefTest
{
public static boolean validate(String s)
{
if (s.charAt(2) == '4')
return false;
if (s.indexOf("35") >= 0 || s.indexOf("53") >= 0)
return false;
return true;
}

public static void main(String[] ssdfa) throws IllegalAccessException, InvocationTargetException, NoSuchMethodException
{
cmp("","122345");
}
public static void cmp(String p,String ss)
{
if(ss.length() == 1)
{
if(validate(p+ss))
System.out.println(p+ss);
return;
}
for(int i=0;i<ss.length();i++)
{
if(ss.indexOf(ss.charAt(i)) == i)
cmp(p+ss.charAt(i),ss.substring(0,i)+ss.substring(i+1, ss.length()));
}
}

}
2008-05-30 17:38 | walnutprince

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

我前天才笔试过这道题,可惜没做起!
2009-03-05 20:01 | hbhjun

# re: 一著名软件公司的java笔试算法题的答案[未登录]  回复  更多评论   

你好,谢谢你的题目,我写了另外的一个算法:http://www.blogjava.net/lanxiazhi/archive/2009/07/27/288626.html。解法有局限,只是针对这个题写的。
2009-07-27 20:08 | lanxiazhi

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{

int[] x = new int[] { 1,2,2,3,4,5};
Hashtable ht = new Hashtable();
for (int a = 0; a < x.Length;a++ )
{
int[] outi=new int[6];

outi[0] = x[a];

for (int b = 0; b < x.Length;b++ )
{
if (b != a)
{
outi[1] = x[b];
}
else {
continue;
}



for(int c=0;c<x.Length;c++){

if (c != a && c != b && c != 4)
{
outi[2] = x[c];
}
else
{
continue;
}


for(int d=0;d<x.Length;d++){
if (d != a && d != b && d != c)
{
outi[3] = x[d];
}
else
{
continue;
}


for (int e = 0; e < x.Length ;e++ )
{
if (e != a && e != b && e != c && e != d)
{
outi[4] = x[e];
}
else
{

continue;
}


for (int f = 0; f < x.Length ;f++ )
{
if (f != a && f != b && f != c && f != d && f != e)
{
outi[5] = x[f];
}
else
{
continue;
}


String outs = "";
for (int z = 0; z < outi.Length;z++ )
{
outs += outi[z];

}
int aaa = -1;
aaa = outs.IndexOf("35");
int bbb = -1;
bbb = outs.IndexOf("53");
if (aaa ==-1 && bbb ==-1)
{
try
{
ht.Add(outs, outs);
}catch(Exception fgh){
continue;
}
}

}

}

}

}

}
}
foreach(String i in ht.Keys){
System.Console.WriteLine(i);
}

}
}
}
脑子不行,弄了好久弄出这样的垃圾,还用了哈希table= =
2010-06-19 13:58 |

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

.我看了這麼多個,這個很完美.
2010-09-14 17:57 | Lain

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

博主,为什么在list方法里我如果不定义新变量s,而直接用result保存连接的结果,只能打印出123345来,晕了。
2012-02-14 17:22 | theoffspring

# re: 一著名软件公司的java笔试算法题的答案  回复  更多评论   

我这样写的,和你原理一样,实现的略有不同

public void list2(String usedIndex, String result) {
for (int idx = 0; idx < arr.length; idx++) {
if (usedIndex.indexOf(idx + 48) > -1) continue;
result = result + String.valueOf(arr[idx]);

if (result.length() == arr.length) {
if (isValid(result)) {
System.out.println(result);
lastResult = result;
cnt++;
}

break;
}

String newUsedIndex = usedIndex + String.valueOf(idx);
list2(newUsedIndex, result);

}

}
2012-02-14 17:23 | theoffspring

只有注册用户登录后才能发表评论。


网站导航: