求助：一道数据结构与算法的面试机试题

Question

请高手们给提供思路，如果哪位能帮忙实现，那就更好了，先谢过！一排座位有1-25个位置，每次进来一个人，都坐到离现在的人最远的位置，人与人之间不能相邻主人想坐最多 的人，他应该让第一个人坐哪个位置？

Answer 1

#1能解释一下如何实现么？我写到这里，写不下去了
package com.boa.interview;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class MaxSeatTest {
public static void main(String[] args) {
MaxSeatTest test = new MaxSeatTest();
Boolean[] seatArray = test.initializeSeatArray(5);

List occupiedList = new ArrayList();
// occupiedList = test.specifyFirst(occupiedList, seatArray);
test.findNextPlace(occupiedList, seatArray);
}

/*
 * step1: Initialize 25 seats as emptyArray, boolean[] b==new boolean[25]; each obj is initalized to true.
 *  1.1 empty seat = true; occupied seat = false; 
 *  1.2 For each 25 from index=0, call findNextPlace() to identity next Place;
 * 
 * step2: findNextPlace(occupiedList); return occupiedSeatNumber;
 *  2.1 for each emptyArray, assume 1st person seat from index = 0, 1, 2...
 *  occupiedList.add(0) == emptyArray[i]; 
 *  2.2 Calculate nextSeat place based on 1st,..., minSeat, maxSeat
 * 
 *  for each occupiedList;
 * 
 *  if occupiedList.size()==1; then last = 1st;
 *  next person seat range: max of ((1st-minSeat),(2nd-1st)...(maxSeat-last)); 
 *  if((1st-minSeat)<(maxSeat-last)){
 *  nextSeat = (last+max)/2;
 *  }else{
 *  nextSeat = (min+1st)/2;
 *  }
 * 
 *  if(nextSeat is odd) 
 *  {break loop;}
 * else{
 * emptyArray[index] = false;
 * occupiedList.add(nextSeat);
 * occupiedSeatNumber++;
 *  }
 * 
 *  if(occupiedSeatNumber>=emptyArray.length/2){
 *  "SUCCESS";
 *  } 
 * 
 */// Intialize Boolean[] array, set each boolean element to true; true means it's available to be occupied;
public Boolean[] initializeSeatArray(int totalSeatNumber){
Boolean[] seatArray = new Boolean[totalSeatNumber];
for(int i=0; i<totalSeatNumber; i++){
seatArray[i] = true;
}
return seatArray;
}

public void findNextPlace(List occupiedList, Boolean[] seatArray){

int minSeat = 0;
int maxSeat = seatArray.length;
int maxPlaceholder = maxSeat/2 + 1; int occupiedSeatNumber = occupiedList.size();
int emptySeatNumber = maxSeat-occupiedSeatNumber;

int nextSeat = 0;
// recursion exit if maxNumber reaches;
if(occupiedSeatNumber==maxPlaceholder){
return; 
}else{ 
// List all occupied Seat inclusive minSeat and maxSeat;
List<Integer> comparePointList = new ArrayList<Integer>();
comparePointList.add(minSeat);
comparePointList.add(maxSeat);

for(int i=0; i<occupiedSeatNumber; i++){
comparePointList.add((Integer)occupiedList.get(i));
}
Collections.sort(comparePointList);

// calculate the farthest distance between any adjacent 2 seats; The next person will sit startPoint+maxDistance/2;
// comparePointList is the list containing all seats' index;

List<Integer> distanceList = new ArrayList<Integer>();
for(int i=0; i<comparePointList.size()-1; i++){
int startPoint = comparePointList.get(i);
int endPoint = comparePointList.get(i+1);
distanceList.add(endPoint-startPoint);
}
}
}


}

Answer 2

请问一下，我那个递归头，为什么退不出方法呀？第80行package com.boa.interview;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;public class MaxSeatTest {
public static void main(String[] args) {
MaxSeatTest test = new MaxSeatTest();
Boolean[] seatArray = test.initializeSeatArray(5);

List occupiedList = new ArrayList();
// occupiedList = test.specifyFirst(occupiedList, seatArray);
// for(int i=0; i<seatArray.length;i++){
//
// test.findNextPlace(occupiedList, seatArray, i);
// }
test.findNextPlace(occupiedList, seatArray, 0);
}

/*
 * step1: Initialize 25 seats as emptyArray, boolean[] b==new boolean[25]; each obj is initalized to true.
 *  1.1 empty seat = true; occupied seat = false; 
 *  1.2 For each 25 from index=0, call findNextPlace() to identity next Place;
 * 
 * step2: findNextPlace(occupiedList); return occupiedSeatNumber;
 *  2.1 for each emptyArray, assume 1st person seat from index = 0, 1, 2...
 *  occupiedList.add(0) == emptyArray[i]; 
 *  2.2 Calculate nextSeat place based on 1st,..., minSeat, maxSeat
 * 
 *  for each occupiedList;
 * 
 *  if occupiedList.size()==1; then last = 1st;
 *  next person seat range: max of ((1st-minSeat),(2nd-1st)...(maxSeat-last)); 
 *  if((1st-minSeat)<(maxSeat-last)){
 *  nextSeat = (last+max)/2;
 *  }else{
 *  nextSeat = (min+1st)/2;
 *  }
 * 
 *  if(nextSeat is odd) 
 *  {break loop;}
 * else{
 * emptyArray[index] = false;
 * occupiedList.add(nextSeat);
 * occupiedSeatNumber++;
 *  }
 * 
 *  if(occupiedSeatNumber>=emptyArray.length/2){
 *  "SUCCESS";
 *  } 
 * 
 */// Intialize Boolean[] array, set each boolean element to true; true means it's available to be occupied;
public Boolean[] initializeSeatArray(int totalSeatNumber){
Boolean[] seatArray = new Boolean[totalSeatNumber];
for(int i=0; i<totalSeatNumber; i++){
seatArray[i] = true;
}
return seatArray;
}

public void findNextPlace(List occupiedList, Boolean[] seatArray, int firstSeat){

int minSeatIndex = 0;
int maxSeatIndex = seatArray.length-1;
int maxPlaceholder = (seatArray.length+1)/2; int occupiedSeatNumber = occupiedList.size();
int emptySeatNumber = maxSeatIndex-occupiedSeatNumber;

int nextSeat = 0;
// recursion exit if maxNumber reaches;
if(occupiedSeatNumber==maxPlaceholder){
System.out.println("ending...");
// why return cannot exit findNextPlace()???
return;
}else{ 
for(int arrayIndex=0; arrayIndex<seatArray.length; arrayIndex++){
while(seatArray[arrayIndex]){

// List all occupied Seat inclusive minSeat and maxSeat;
List<Integer> comparePointList = new ArrayList<Integer>();
comparePointList.add(minSeatIndex);
comparePointList.add(maxSeatIndex);
comparePointList.add(firstSeat);

Collections.sort(comparePointList);

// calculate the farthest distance between any adjacent 2 seats; The next person will sit startPoint+maxDistance/2;
// comparePointList is the list containing all seats' index;

TreeMap<Integer,String> tm = new TreeMap<Integer,String>();
for(int i=0; i<comparePointList.size()-1; i++){
Integer startPoint = comparePointList.get(i);
Integer endPoint = comparePointList.get(i+1);
Integer distance = endPoint - startPoint;
String startPoint_endPoint = startPoint+"_"+endPoint;
tm.put(distance, startPoint_endPoint);
}

int tmSize = tm.size();
String farest_startPoint_endPoint = (String) tm.values().toArray()[tmSize-1];
System.out.println(farest_startPoint_endPoint);
String[] start_endPoint = farest_startPoint_endPoint.split("_");

int startPoint = Integer.parseInt(start_endPoint[0]);
int endPoint = Integer.parseInt(start_endPoint[1]);
nextSeat = (startPoint+endPoint)/2;
System.out.println("nextSeat Index: "+nextSeat);

if(nextSeat%2==1){
return;
}else{
occupiedList.add(nextSeat);
seatArray[nextSeat] = false;
int rightPartLength = endPoint-nextSeat;
int leftPartLength = nextSeat-startPoint;
if(leftPartLength==rightPartLength){
Boolean[] subArray = new Boolean[leftPartLength];
System.arraycopy(seatArray, startPoint, subArray, 0, leftPartLength);
findNextPlace(occupiedList, subArray, nextSeat);
}
}

}
}
}
}


}