如何在LinkedList中逐个检查多个值？

Question

我想做一个应用程序，以一种简单的方式在电影院分配座位。

我有一个LinkedList，其中随机填写了0“座位可用”或1“座位已被占用”。此LinkedList由变量int“seatsTotal”生成，然后用数学填充LinkedList。具有1或0的随机函数。

这个想法是用户给出一个变量，即他们想预订多少座位，之后，一个（也许是递归的）方法将查找（例如）标有0（可用）的5个座位。

如果后面（旁边）没有5个座位可用，该方法必须寻找4个可用座位和1个单独的座位。如果没有4个座位可用，应用程序将查找3个座位和2个座位等。

我的第一个问题是；我知道我可以使用LinkedList。contains（）检查是否存在某个值，但如何检查（例如）0是否连续出现5次？

我的第二个问题是；如果没有5个座位可用，我将不得不寻找4个座位和1个座位（例如），我如何处理这种方法？

我真的被这件事困住了，非常感谢你的帮助。

public class Main {

    static int seatCount = 10;
    int verzoekAantal = 3;
    int consecutiveLength = 0; // Consecutive free seats length
    int index = 0;
    int startIndex = -1; // Store the start of consecutive free seats
    LinkedList<Seat> consecutiveList = new LinkedList<>(); // Store startIndex -> length

    public static void main(String[] args) {
//        System.out.println(Arrays.toString(fillList(seatCount).toArray()));
        System.out.println(fillSeats(3).toString());
    }

    //Deze methode geeft via de Math package een willekeurig getal, 1 (bezet) of 0 (vrij)
    static int giveRandomAvailability() {
        return intValue(Math.random() * 2);
    }


    //Deze methode creëert een LinkedList van grootte 'seatCount' en vult de plaatsen een voor een met 0 of 1 op willekeur
    static LinkedList fillList(int seats){
        LinkedList<Seat> list = new LinkedList<Seat>();
        seats = seatCount;

        for(int i = 0; i < seats; i++){
            Seat seat = new Seat();
            seat.availability = giveRandomAvailability();
            seat.seatNumber = (i + 1);
            list.add(seat);
        }

        return list;
    }

    static Map fillSeats(int n){
        LinkedList<Seat> newList = fillList(seatCount);
        int consecutiveLength = 0; // Consecutive free seats length
        int index = 0;
        int startIndex = -1; // Store the start of consecutive free seats
        int remConsecutiveLength = 0;
        System.out.println(newList.toString());
        Map<Integer, Integer> consecutiveMap = new HashMap<>(); // Store startIndex -> length

        for (Seat seat : newList) {
            if (seat.IsFree()) {
                if (startIndex < 0) {
                    startIndex = index;
                }
                consecutiveLength ++;
            } else {
                consecutiveMap.put(startIndex + 1, consecutiveLength);
                if (consecutiveLength >= n) {
                    System.out.println("SEATS FOUND, " + n + " seats available counting from " + (seat.seatNumber - n));
                }

//                if(consecutiveLength > remConsecutiveLength) {
//                    remConsecutiveLength = consecutiveLength;
//                }
                startIndex = -1;
                consecutiveLength = 0;
            }
            index++;
        }
        if (startIndex >= 0) {
            consecutiveMap.put(startIndex + 1, consecutiveLength);
        }
//                    if (remConsecutiveLength < n) {
//                    while(n > 1) {
//                        System.out.println("Looking for seats which are not next to eachother");
//                        n--;
//                        fillSeats(n);
//                    }
//                }
        Map<Integer, Integer> treeMap = new TreeMap<Integer, Integer>(consecutiveMap);
        return treeMap;
    }
}

Answer 1

您需要找到连续的座位并存储这些项目。

假设您正在将座位信息存储在seat类中，我们有列表

int consecutiveLength = 0; // Consecutive free seats length
int index = 0;
int startIndex = -1; // Store the start of consecutive free seats
Map<Integer, Integer> consecutiveMap = new HashMap<>(); // Store startIndex -> length

for (Seat seat : seats) {
  if (seat.isFree()) {
    if (startIndex < 0) {
      startIndex = index;
    }
    consecutiveLength ++;
  } else {
    consecutiveMap.put(startIndex, consecutiveLength);
    if (consecutiveLength == n) {
      // Found, do something here
    }
    // Reset
    startIndex = -1;
    consecutiveLength = 0;
  }
  index++;
}

在此之后，您可以访问连续地图中的所有连续长度。

您也可以通过上述ore块中的test连续长度==n立即返回。

通过访问每个数量的连续长度，您可以选择子选项（4个连续1个单一等）

编辑

运行代码后，您的连续映射将如下所示

{1 -> 1, 3 -> 4, 8 ->1, ...}

上面写着：在索引1处，有一个连续的座位。

在索引3处，有一个连续的4个座位区。。。。

您可以通过连续映射访问列表中的连续长度。values（）

它将为您提供<代码>{1，4，1，2，…} 。

您的问题简化为：在数组中选择几个项目，使它们的总和为n。您甚至可以对它们进行排序，以从较大到较小的连续长度进行选择。

这很简单。

您也可以在这里施暴，因为每排座位的数量不是很大。

Answer 2

回答问题的第一部分：

如果你想找到n个连续的空座位，你必须遍历你的LinkedList并计数空闲座位，直到你找到n个连续的座位，或者你遍历所有座位。

public List<Seat> findNConsecutiveEmptySeats(List<Seat> seats, int n) {
    List<Seat> freeSeats = new LinkedList<Seat>();
    for(Seat s : seats) {
        if(s.isEmpty()) {
            freeSeats.add(s);
        } else {
            freeSeats.clear();
        }
        if(freeSeats.size() >= n) {
            break;
        }
     }
     if(freeSeats.size() < n) {
        freeSeats.clear();
     }
     return freeSeats;
}

要回答问题的第二部分，需要使用n=5调用前面的方法。如果返回的列表包含5个座位，很好，您找到了，请返回它。如果它包含空列表，请使用n=4然后n=1调用该方法。等

public List<Seat> findNEmptySeats(List<Seat> seats, int n) {
    List<Seats> freeSeats = findNConsecutiveEmptySeats(seats, n);
    if(freeSeats.size() == n) {
        return freeSeats;
    }
    freeSeats = findConsecutiveEMptySeats(seats, n-1);
    freeSeats.addAll(findConsecutiveEMptySeats(seats, 1));
    if(freeSeats.size() == n) {
        return freeSeats;
    }
    freeSeats = findConsecutiveEMptySeats(seats, n-2);
    freeSeats.addAll(findConsecutiveEMptySeats(seats, 2));
    if(freeSeats.size() == n) {
        return freeSeats;
    }

    ...

}

注意：此代码不完整，例如在查找n-1个座位后，您需要在查找1个座位之前删除找到的座位，否则您可能会返回一个已经找到的座位。