如何在彼此之后检查LinkedList中的多个值？

I want to make an application which allocates seats in a cinema in a simple way.

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

I have a LinkedList which is randomly filled with 0 'seat is available' or 1 'seat is taken'. This LinkedList is generated by the variable int 'seatsTotal', the LinkedList is then filled with the Math.random function with 1 or 0.

我有一个LinkedList,随机填充0'座位可用'或1'座位被采取'。这个LinkedList是由变量int'tacesTotal'生成的,然后LinkedList被Math.random函数填充为1或0。

The idea is that the user gives a variable which is how many seats they would like to book, after that, a (perhaps recursive) method will look for (example) 5 seats which are labeled with 0 (available).

想法是用户给出一个变量,即他们想要预订的座位数,之后,(可能是递归的)方法将寻找(例子)5个标有0(可用)的座位。

If there are no 5 seats available after (next to) eachother, the method has to look for 4 available seats and 1 seat seperate. If there are no 4 seats available, the application will look for 3 seats and 2 seats etc.

如果在彼此之后(旁边)没有可用的5个座位,则该方法必须寻找4个可用座位和1个座位单独。如果没有4个座位,应用程序将寻找3个座位和2个座位等。

My first question is; I know I can use LinkedList.contains() to check if a certain value is present, but how can I check if (for example) 0 is presents 5 times in a row?

我的第一个问题是;我知道我可以使用LinkedList.contains()来检查是否存在某个值,但是如何检查(例如)0是否连续5次出现?

My second question is; How can I handle the method if there are no 5 seats available and I will have to look for 4 seats and 1 seat (for instance)?

我的第二个问题是;如果没有5个座位,我该如何处理这个方法,我将需要寻找4个座位和1个座位(例如)?

I'm really stuck with this, help would be greatly appreciated.

我真的坚持这一点,非常感谢帮助。

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;
    }
}

2 个解决方案

#1

To answer the first part of your question :

要回答问题的第一部分:

If you want to find n consecutive empty seats, you have to loop through your LinkedList and count free seats until you found n consecutive, or you go through all seats.

如果你想找到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;
}

---

To answer the second part of your question, You need to call the previous method with n=5. If the list returned contains 5 seats, great you found them, return it. If it contains an empty list, call the method with n=4 then n=1. Etc...

要回答问题的第二部分,您需要使用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;
    }

    ...

}

Note : this code is not complete, for example after looking for n-1 seats, you need to remove the found seats before looking for the 1 seat, otherwise you could return an already found seat.

注意:此代码不完整,例如在寻找n-1个座位后,您需要在找到1个座位之前移除找到的座位,否则您可以返回已找到的座位。

#2

You need to find the consecutive seats and store those items.

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

Assume that you're store your seat information in a Seat class, and we have List<Seat> seats as input. and n is number of seats you want to find.

假设您将座位信息存储在Seat类中,并且我们将List 座位作为输入。和n是您要查找的座位数。

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++;
}

After this you have access to all of consecutiveLength in consecutiveMap.

在此之后,您可以访问consecutiveMap中的所有consecutiveLength。

You can also return immediately by test consecutiveLength == n in above else block.

您也可以通过上面的else块中的testLength == n测试立即返回。

By accessing every number of consecutiveLength you are able to choose the sub option (4 consecutive + 1 single, etc)

通过访问每个数量的连续长度,您可以选择子选项(4连续+ 1单,等)

Edit

After running the code your consecutiveMap will look like

运行代码后,您的consecutiveMap将如下所示

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

It reads: At index 1, there's 1 consecutive Seat.

它显示:在索引1处,有1个连续的席位。

At index 3, there's a 4 consecutive seats block. ....

在指数3处,有一个连续4个席位。 ....

You access the consecutive length in your list by consecutiveMap.values()

您可以通过consecutiveMap.values()访问列表中的连续长度

It will give you {1, 4, 1, 2, ...}.

它会给你{1,4,1,2 ......}。

And your problem is reduced to: Pick several item in an array so that sum of them are n. You can even sort them to pick from larger to smaller consecutive length.

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

It's pretty straightforward.

这很简单。

You can bruteforce here also, since number of seat per row is not very large.

你也可以在这里暴力,因为每排座位数不是很大。