昨天一个同学去面试,面试官出的一个逻辑思维能力的题 - 黑马程序员技术交流社区

import java.util.ArrayList;
/**
* 思路：在桥这边枚举两个人过去，然后在桥那表让花时最小的送手电筒回来，
* 然后继续枚举两个人过桥，再让花时最小的送手电筒回来，循环的，直到这边的人只剩下两个。
*/
class Tie_2
{
// 记录过程
private static String changes = "";
// 标记是否成功过桥，若成功过了，那么就跳出，不找了
private static boolean isCross = false;
public static void main(String[] args)
{
ArrayList<Integer> here = new ArrayList<Integer>();
ArrayList<Integer> there = new ArrayList<Integer>();
init(here,there);
// 枚举两个人过桥
o:for(int i=0; i<here.size(); i++)
{
for(int j=0; j<here.size(); j++)
{
if(i==j)
continue;
int timeone = here.get(i);
int timetwo = here.get(j);
if(!isCross){
crossBridge(here,there,timeone,timetwo,0);
init(here,there);
}else{
break o;
}
}
}
}
// 初始化数据
public static void init(ArrayList<Integer> here,ArrayList<Integer> there)
{
here.clear();
there.clear();
here.add(1);
here.add(2);
here.add(5);
here.add(10);
}
// 过桥
public static void crossBridge(ArrayList<Integer> a, ArrayList<Integer> b, int timeone, int timetwo,int allTime)
{
// 取出花时最大的
int bigTime = timeone > timetwo ? timeone : timetwo;
changes += "这边：" + a +" -------桥-------- " + "那边："+b + "\n\t" +timeone + "和" + timetwo + "一起过桥！---用时："+bigTime+"分\n";
// 将过桥的两个存在b集合，代表过桥了
b.add(timeone);
b.add(timetwo);
allTime += bigTime; // 一共用了多少时间
// 把过桥的两个人在a集合中删除
for(int i=0;i<a.size();i++)
if(timeone==a.get(i)){
a.remove(i);
break;
}
for(int i=0;i<a.size();i++)
if(timetwo==a.get(i)){
a.remove(i);
break;
}
// 在这边找一个花时最小的送手电筒回去
int smallTimeIndex = getSmallTime(b); // 花时最小的时间的角标
changes += "这边：" + a +" -------桥-------- " + "那边："+b+"\n\t"
+ b.get(smallTimeIndex) + "送手电筒回去！---用时：" +b.get(smallTimeIndex)+"分\n";
allTime += b.get(smallTimeIndex); // 累加时间
a.add(b.get(smallTimeIndex)); // 送手电筒回去了，就添加到a集合
b.remove(smallTimeIndex);
// 出口判断
if(a.size()==2 && b.size()==2)
{
bigTime = Math.max(a.get(0),a.get(1));
allTime+=bigTime;
if(allTime > 17)
{
changes = "";
return;
}
System.out.println(changes +"\t"+ a.get(0)+"和"+a.get(1) +"一起过桥！---用时："+bigTime+"分");
System.out.println("\t一共花时："+allTime+"分");
isCross = true; // 标记已经成功过桥了
changes = "";
return;
}
// 继续枚举两个人过桥
for(int i=0; i<a.size(); i++)
{
for(int j=0; j<a.size(); j++)
{
if(i==j)
continue;
timeone = a.get(i);
timetwo = a.get(j);
if((allTime + (timeone > timetwo ? timeone : timetwo)) > 17)
continue;
crossBridge(a,b,timeone,timetwo,allTime);
}
}
}
// 获取b集合中花时最小时间的角标
public static int getSmallTime(ArrayList<Integer> b)
{
int small = Integer.MAX_VALUE;
int index = -1;
for(int i=0;i<b.size();i++)
if(small > b.get(i))
{
small = b.get(i);
index = i;
}
return index;
}
}

复制代码