求助：一道数据结构与算法的面试机试题
请高手们给提供思路，如果哪位能帮忙实现，那就更好了，先谢过！一排座位有1-25个位置，每次进来一个人，都坐到离现在的人最远的位置，人与人之间不能相邻。。。主人想坐最多 的人，他应该让第一个人坐哪个位置？ --------------------编程问答-------------------- 第一个人做在第9个位置，正好13个位置，最多。。。 --------------------编程问答-------------------- 都坐到离现在的人最远的位置
这句话是怎么理解的？
现在的人指的是一位还是多位？ --------------------编程问答--------------------
---现在的人是指多人 --------------------编程问答-------------------- #1能解释一下如何实现么？我写到这里，写不下去了。。。
package com.boa.interview;--------------------编程问答-------------------- 请问一下，我那个递归头，为什么退不出方法呀？第80行
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);
}
}
}
}
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);
}
}
}
}
}
}
}
--------------------编程问答--------------------
我觉得楼主可以用二分查找来计算，因为二分查找的中点保证了到左边或右边的距离是最大的（如果没理解错坐到最远的意思）
--------------------编程问答--------------------
靠，搞错了 ....
--------------------编程问答--------------------
说实话是我自己分析出来的答案，没有用程序实现，不过用程序实现并不容易啊。
--------------------编程问答--------------------
你用二分法查找最佳位置。能瞒住距离最远同时人数最多
--------------------编程问答--------------------
多位？都坐到离多个人最远的位置？那这个“最远”是指什么，离在坐的每个人的距离之和最远？还是怎么个最远法？
如果这是原题，那么出面试题人根本没考虑过这个问题，这个题出的非常不严谨！ --------------------编程问答-------------------- 人家题意很明确，这种题本来就不能咬文嚼字。。。。
--------------------编程问答--------------------
+1 --------------------编程问答--------------------
有多个人提出同样的问题，居然还能认为别人在咬文嚼字？！！其实我们都一样，大部分时候都缺乏换位思考 --------------------编程问答-------------------- 还是那一句，题本身是没问题，有问题的是对题的理解。。。。。。 --------------------编程问答-------------------- 看不懂题意!
补充：Java , Java SE
