2道英文JAVA试题，有谁帮我看下？

Question

1) Randomly reshuffle an array:   a function takes an array as input, and output the randomly re-shuffled array.  Please ensure the reshuffling is uniformly distributed.
For example,
before, the array is :0, 1 ,2 ,3, 4, ..n,
after,  the array is : a0, ..,  an
where,  ai has equal probabilities to be 0 - n.
 
2)  detect a loop in a single linked list. Given a single linked list, output whether the list has a loop or not.
  for example: list1 : node0 -> node1 -> node2 -> null
               list2 : node0 -> node1 -> node2 -> node1
The second list has loop, but the first one doesn't. 
Please make sure the java files is compilable, and run correctly.

Answer 1

第二题方法很多，楼主可以自行考虑。
至于第一题嘛，这个是有点麻烦的，楼主可以参考java.util.Collections里边的shuffle方法，但要做到几率的的绝对平等这个是非常困难的，应为这取决于随机数取值的质量，但是在程序中实现的随机数应该都是伪随机数。但是取随机数还是使用java.util.Random吧，如果不用自己取写随机数的方法，这个问题还是很简单的，但是还得强调，不能保证绝对平均。 
Java Puzzlers 这本书有对这个问题的描述，不记得在哪一章了，有兴趣的话可以自己看看！

Answer 2

import java.util.*;
public class Hash { /**
 * @param args
 */
int number [] = {1,2,3,4,5,6};
Map<Integer, String> map1 = new HashMap<Integer, String>();
public Hash(){
for (int a = 0; a < number.length; a++){
map1.put(a, "a" + number[a]);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Hash hash1 = new Hash();
for(int a = 0; a < hash1.number.length; a++){
System.out.print(hash1.map1.get(a));
}
}}

Answer 3

第二题还是好实现， 用map或者其他的
第一题就不知道是什么意思了

Answer 4

第一题的参考实现，因为不明白uniformly distributed. 的意思。应该是几率相等吧，但是几率相等跟应该跟Random有关系的。我看了文档只是搞明白了Random的两个构造方法的区别。楼主可以看看，如有不明白可以讨论。
参考API文档代码如下：其实多行注释掉的内容是测试内容，楼主可去掉注释测试！package test;import java.util.*;
public class ArrayShuffle { /**
 * @param args
 */
 public static void shuffle( Object[] arr, Random rnd) {
        int size = arr.length;
         // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));
             }
 
private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

public static void main(String[] args) {
// TODO Auto-generated method stub
     Integer[] arr = {0,1,2,3,4,5,6,7};
     //输出初始数组
     for(int i=0 ;i<arr.length;i++){
      System.out.print(arr[i]);
     }
     System.out.println("处理中....");
     //处理数组
     shuffle(arr,new Random());
     System.out.println("处理后....");
     //处理后
     for(int i=0 ;i<arr.length;i++){
      System.out.print(arr[i]);
     }
     /**
     System.out.println("处理中....");
     //处理数组
     shuffle(arr,new Random());
     System.out.println("处理后....");
     //处理后
     for(int i=0 ;i<arr.length;i++){
      System.out.print(arr[i]);
     }System.out.println("处理中....");
     //处理数组
     shuffle(arr,new Random());
     System.out.println("处理后....");
     //处理后
     for(int i=0 ;i<arr.length;i++){
      System.out.print(arr[i]);
     }
     */
}
}

Answer 5

第一个9楼已经实现了。
现在实现的是第二个。
import java.util.ArrayList;
import java.util.List;
public class DetectLoop { /**
 * @param args
 */
public boolean isDetected;
List<node> list1 = new ArrayList<node>();
public DetectLoop(){
//@SuppressWarnings("unused")
// boolean isDetected;
if(list1.isEmpty()) 
{
System.out.println("Empty");
isDetected = false;
}

else{
for(int i = 0; 0 < list1.size(); i++){
node temp = list1.get(i);
for(int j = 0; 0 < i; j++ ){
if(temp == (list1.get(j)).next) 
isDetected = true;

else isDetected = false;
}
}
}
} public static void main(String[] args) {
// TODO Auto-generated method stub DetectLoop detect = new DetectLoop();
System.out.println(detect.isDetected);

}}

Answer 6

我认为9楼的理解是错误的，题目的意思应该是将原来的数组随机排列，例如0~5个人，输出的a 可能为 a1,a0,a3,a5,a4
可以理解为以下模型，
有10个房子a0~a9，十个人为0~9
假设
a0房子进入一个人，这个人进入该房的概率为1/10；
a1进入剩下9个人中的一个，这个人进入该房的概率为（1/9）*（9/10）= 1/10；---因为他没进入0号房，所以需要乘9/10；
a2进入剩下8个人中的一个，这个人进入该房的概率为（1/8）*（8/9）*（9/10）= 1/10；---同理他没进入1号房，所以需要乘8/9，没进入0号需乘9/10；
。
现在可以知道，哪个人进入哪个房子的概率都是一样的；
下面就是实现这个思想的代码
public static void main(String[] args) {
int n = 10;//人数
int m = n;//队尾号码 
int[] person = new int[n];//人的编号
int[] a = new int[n];//房间编号
for (int i = 0; i < n; i++) {
person[i] = i;
}
for (int i = 0; i < n; i++) {
int j = (int)(Math.random()*m);//j为随机得到的人编号
a[i] = person[j];//j号进入洞房
int temp = person[m-1];//将已经进入洞房的人的编号放在队尾，为了以后不查找到他
person[m-1] = person[j];
person[j] = temp;//队尾的编号提前
m--;//队尾自减，为了下次循环的队尾不是原来的
}
for( int i =0; i<n; i++){
System.out.println("a" +i+ "=" + a[i]); //输出结果
}
}
a0=8
a1=5
a2=2
a3=0
a4=4
a5=3
a6=9
a7=7
a8=6
a9=1希望对楼主有帮助，本人也在找工作中，呵呵

Answer 7

朋友，我想请问下你的node是从哪来的？

Answer 8

9楼的没看明白。HashMap这个东西本来就是无序的。
这个引用部分倒是讲得很详细。

Answer 9

import java.util.ArrayList;
import java.util.List;
public class AAA {
public static void main(String[] args) {
try {
int i = 0;
while(true){
if(i>100){
break;
}
i++;
char[] array = new char[]{'a','b','c','d','e','f'};
char[] ranArray = new char[array.length];
List list = new ArrayList();
while(true){
double d= Math.floor(Math.random()*array.length);//随机产生0-5
boolean flag = false;
for(int j=0;j<list.size();j++){
double value = (Double)list.get(j);
if(value==d){
flag = true;
}
}
if(!flag){
list.add(d);
}
if(list.size()==array.length){
break;
}
}
for(int k = 0;k<list.size();k++){
ranArray[((Double)list.get(k)).intValue()] = array[k];
}
for(int m = 0;m<ranArray.length;m++){
System.out.print(ranArray[m]+" ");
}
System.out.println();
}

} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

Answer 10

import java.util.ArrayList;
import java.util.List;
public class AAA {
public static void main(String[] args) {
try {
int i = 0;
while(true){
if(i>100){
break;
}
i++;
char[] array = new char[]{'a','b','c','d','e','f'};
char[] ranArray = new char[array.length];
List list = new ArrayList();
while(true){
double d= Math.floor(Math.random()*array.length);//随机产生0-5
boolean flag = false;
for(int j=0;j<list.size();j++){
double value = (Double)list.get(j);
if(value==d){
flag = true;
}
}
if(!flag){
list.add(d);
}
if(list.size()==array.length){
break;
}
}
for(int k = 0;k<list.size();k++){
ranArray[((Double)list.get(k)).intValue()] = array[k];
}
for(int m = 0;m<ranArray.length;m++){
System.out.print(ranArray[m]+" ");
}
System.out.println();
}

} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}