李寧的極客世界

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

請問index.indexOf(i + 48) < 0判斷條件的作用是什么？

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

index保存了當(dāng)前數(shù)字串的索引，index.indexOf(i + 48) < 0就是判斷當(dāng)前的數(shù)字的索引是否在index中（由于給定的數(shù)字串有重復(fù)的數(shù)字，因此，只能使用索引來判斷了），如果不在，就會(huì)認(rèn)為這個(gè)數(shù)字還沒有加到index中，如果存在了，說明這個(gè)數(shù)已經(jīng)在數(shù)字串中了。


注：i+48 ，當(dāng)i=0時(shí)，正好是數(shù)字0的ASCII，以此類推

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

你給出的想法和代碼都很優(yōu)秀，我覺得你對本題有兩點(diǎn)非常獨(dú)特的見解：1）你會(huì)使用字符索引來“組合”最后的字符串，而且?guī)滋幱玫降膇ndexOf非常合理，也很巧妙；2）validate函數(shù)的使用，尤其是判斷重復(fù)字符串上面，很難想到。我建議你還能去網(wǎng)上找到兩個(gè)版本的程序，其中一個(gè)也是用遞歸，另一個(gè)是圖的思想，一定要做多組測試，因?yàn)榫W(wǎng)上好多的程序都是錯(cuò)誤的，你這幾組的數(shù)據(jù)都是對的。

補(bǔ)：在“注”中有筆誤，當(dāng)i=0的時(shí)候，i+48是0的ASCII，因?yàn)槟鉯ndex中存的畢竟是索引，是位置嘛，所以是從0開始的

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

to dreamingnest

謝謝提醒，是寫錯(cuò)了，i+48，從數(shù)字0開始。改過來了。如果有更好的解決方案，請跟貼。謝謝！

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

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()));
}
}

}

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

我前天才筆試過這道題，可惜沒做起！

# re: 一著名軟件公司的java筆試算法題的答案[未登錄]  回復(fù)  更多評論   

你好，謝謝你的題目，我寫了另外的一個(gè)算法：http://www.aygfsteel.com/lanxiazhi/archive/2009/07/27/288626.html。解法有局限，只是針對這個(gè)題寫的。

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

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= =

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

.我看了這麼多個(gè),這個(gè)很完美.

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

博主，為什么在list方法里我如果不定義新變量s，而直接用result保存連接的結(jié)果，只能打印出123345來，暈了。

# re: 一著名軟件公司的java筆試算法題的答案  回復(fù)  更多評論   

我這樣寫的，和你原理一樣，實(shí)現(xiàn)的略有不同

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);

}

}