java - 如何检查链表中的多个值？

Question

我想制作一个以简单方式分配电影院座位的应用程序。

我有一个 LinkedList，其中随机填充了 0 个“空位”或 1 个“已占位”。这个 LinkedList 由变量 int 'seatsTotal' 生成，LinkedList 然后用 Math.random 函数填充 1 或 0。

想法是用户给出一个变量，即他们想要预订多少个座位，之后，一个(可能是递归的)方法将寻找(示例)5 个标记为 0(可用)的座位。

如果彼此之后(相邻)没有 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

回答你问题的第一部分:

如果你想找到 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个座位，否则您可以归还已找到的座位。