如何检测LinkedList中连续目标值？简易影院选座系统实现咨询

Hey there! Let's tackle your two Java LinkedList-related problems one by one, with practical code examples and easy-to-follow explanations.

To spot consecutive occurrences of a target value in a LinkedList, the core idea is maintaining a streak counter as you iterate through the list:

• Start with a counter set to 0
• Loop through each element in the list:
  • If the current element matches the target, increment the counter
  • If not, reset the counter back to 0
  • After each counter update, check if it hits your required consecutive count—if yes, you can immediately return a positive result (or record the starting position)

Here's a Java implementation:

import java.util.LinkedList;

public class LinkedListStreakChecker {
    public static boolean hasConsecutiveValues(LinkedList<Integer> list, int target, int requiredStreak) {
        if (requiredStreak <= 0) return true; // Edge case: 0 required streaks is always true
        int currentStreak = 0;
        
        for (Integer num : list) {
            if (num.equals(target)) {
                currentStreak++;
                if (currentStreak == requiredStreak) {
                    return true;
                }
            } else {
                currentStreak = 0;
            }
        }
        return false;
    }

    // Test the method
    public static void main(String[] args) {
        LinkedList<Integer> testList = new LinkedList<>();
        testList.add(0);
        testList.add(0);
        testList.add(1);
        testList.add(0);
        testList.add(0);
        testList.add(0);
        
        System.out.println(hasConsecutiveValues(testList, 0, 3)); // Outputs true
        System.out.println(hasConsecutiveValues(testList, 1, 2)); // Outputs false
    }
}

If you need to record the starting index of the consecutive values, tweak the code to calculate and return currentIndex - requiredStreak + 1 when the streak is achieved.

This task breaks down into three key parts: generating a random seat list, recursively finding consecutive available seats, and handling user input. Here's a complete, working implementation:

2.1 Generate Random Seat List #

Use Math.random() to fill a LinkedList with 0 (available) and 1 (occupied) values:

import java.util.LinkedList;
import java.util.Scanner;

public class CinemaSeatAllocator {
    private LinkedList<Integer> seats;

    // Initialize the seat list with random availability
    public CinemaSeatAllocator(int totalSeats) {
        seats = new LinkedList<>();
        for (int i = 0; i < totalSeats; i++) {
            // 50% chance of available/occupied—adjust the threshold to change occupancy rate
            seats.add(Math.random() > 0.5 ? 1 : 0);
        }
        System.out.println("Current seat status (0=available, 1=occupied): " + seats);
    }

2.2 Recursive Method to Find Consecutive Available Seats #

The recursive logic works like this:

• Base case: If there aren't enough seats left to meet the requirement, return -1 (no match found)
• Recursive step: Check if the current starting index has enough consecutive 0s. If yes, return the index; if not, recurse starting from the next index.

// Recursive helper to find starting index of consecutive available seats
    private int findConsecutiveSeats(int startIndex, int requiredSeats) {
        // Base case: Not enough seats left to fulfill the request
        if (startIndex + requiredSeats > seats.size()) {
            return -1;
        }

        // Check if all seats from startIndex are available
        boolean allAvailable = true;
        for (int i = startIndex; i < startIndex + requiredSeats; i++) {
            if (seats.get(i) != 0) {
                allAvailable = false;
                break;
            }
        }

        if (allAvailable) {
            return startIndex; // Found valid seats
        } else {
            // Move to next index and try again
            return findConsecutiveSeats(startIndex + 1, requiredSeats);
        }
    }

    // Public method to start search from index 0
    public int findAvailableConsecutiveSeats(int requiredSeats) {
        if (requiredSeats <= 0 || requiredSeats > seats.size()) {
            System.out.println("Invalid number of seats requested!");
            return -1;
        }
        return findConsecutiveSeats(0, requiredSeats);
    }

2.3 Handle User Input and Complete Booking #

Add a main method to take user input, find seats, and mark them as occupied if booking is successful:

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Set up total seats
        System.out.print("Enter total number of cinema seats: ");
        int totalSeats = scanner.nextInt();
        CinemaSeatAllocator allocator = new CinemaSeatAllocator(totalSeats);

        // Get user's booking request
        System.out.print("Enter number of consecutive seats to book: ");
        int requiredSeats = scanner.nextInt();

        int startIndex = allocator.findAvailableConsecutiveSeats(requiredSeats);
        if (startIndex != -1) {
            // Mark seats as occupied
            for (int i = startIndex; i < startIndex + requiredSeats; i++) {
                allocator.seats.set(i, 1);
            }
            System.out.println("Booking successful! Seats start at index " + startIndex + " and end at index " + (startIndex + requiredSeats - 1));
            System.out.println("Updated seat status: " + allocator.seats);
        } else {
            System.out.println("Sorry, no consecutive available seats found for your request.");
        }

        scanner.close();
    }
}

Notes #

• Adjust the Math.random() threshold to change the occupancy rate (e.g., Math.random() > 0.7 for 70% occupied seats)
• The recursive method stops as soon as it finds a valid block of seats for efficiency

内容的提问来源于stack exchange，提问作者user8827176