В коде есть некоторые ошибки, которые также могут быть реализованы проще:
validSeats возврат для каждого ряда (1,2,...) только последний место (A,B,...) перечислены в переданном списке мест. Поэтому некоторые занятые места не учитываются. Например, для списка мест 1 C 2B 1G 1E 2F 2D validSeats будут найдены только места 1E и 2D . Это вызвано использованием типа Map, который может содержать каждый ключ только один раз. Если пара ключ / значение (K1/V2) установлена с помощью Map#put и пара ключ / значение (K1/V1) с тем же ключом K1 уже существует, старое значение V1 заменяется новым значением V2. Это означает, что ранее найденные места теряются. Чтобы предотвратить это, тип Map должен быть заменен. Одна возможность состоит в том, чтобы заполнить позднее использованный массив int[][] takenSeats напрямую вместо того, чтобы брать объезд через Map -экземпляр.
Кроме того, нет необходимости разбивать переданный список мест. Вместо этого механизм регулярных выражений может быть применен непосредственно к переданной строке.
Возможная реализация:
private static int[][] validSeats(int numberOfRows, String seatList) {
int[][] takenSeats = new int[numberOfRows][10];
Pattern p = Pattern.compile("\\d{1,2}-?[A-Z]");
Matcher m = p.matcher(seatList);
while (m.find()) {
String seat = m.group().replace("-", ""); // e.g. 12C
char letter = seat.substring(seat.length() - 1, seat.length()).charAt(0); // 12
String row = seat.substring(0, seat.length() - 1); // C
int letterIndex = letter > 'H' ? letter - 'A' - 1 : letter - 'A'; // Map ABC DEFG HJK -> 012 3456 789
int rowIndex = Integer.parseInt(row) - 1; // Map 123... -> 012...
takenSeats[rowIndex][letterIndex] = 1;
}
return takenSeats;
}
solution содержит несколько fl aws, например:
int[][] takenSeats заполнено неправильно. Для приведенного выше примера только с 1E (как индекс 04 ) и 2D (как индекс 13 ) 2E (в качестве индекса 14 ). - В нескольких местах кода используется неверный индекс. Например, для случая
k = 1 проверяются места takenSeats[i][k+1], takenSeats[i][k+2], takenSeats[i][k+3] и takenSeats[i][k+4]. Однако, так как индекс начинается с нуля, необходимо проверить местоположения takenSeats[i][k], takenSeats[i][k+1], takenSeats[i][k+2] и takenSeats[i][k+3]. - Не учитывается, что в та же строка комбинация BCDE исключает комбинацию DEFG . Аналогично, комбинация DEFG исключает комбинацию FGHJ .
Возможная альтернативная реализация:
private static int solution(int numberOfRows, String seatList) {
int numberOfFamilySeats = 0;
int[][] takenSeats = validSeats(numberOfRows, seatList); // 0: free, 1: initially occupied, 2: calculated family seats
for (int rowIndex = 0; rowIndex < numberOfRows; rowIndex++) { // Check each row
for (int letterIndex = 1; letterIndex <= 5; letterIndex +=2) { // Check neighboring seats of B (->CDE), D (->EFG) and F (->GHJ)
if (takenSeats[rowIndex][letterIndex] == 0 && takenSeats[rowIndex][letterIndex + 1] == 0 && takenSeats[rowIndex][letterIndex + 2] == 0 && takenSeats[rowIndex][letterIndex + 3] == 0) {
for (int familySeats = 0; familySeats < 4; familySeats++) { // Mark family seats as occupied
takenSeats[rowIndex][letterIndex + familySeats] = 2;
}
if (letterIndex == 1) letterIndex = 3; // BCDE excludes DEFG
else if (letterIndex == 3) letterIndex = 5; // DEFG excludes FGHJ
numberOfFamilySeats++; // Found free family seat
}
}
}
System.out.println(Arrays.deepToString(takenSeats)); // Optionally print seat plan
return numberOfFamilySeats;
}
Пример:
public static void main(String[] args) {
String seatList = "1F 2D 2G 3C 3D 4B 5H 6A 7B 7F";
System.out.println("Number of families: " + solution(7, seatList));
}
Вывод:
[[0, 2, 2, 2, 2, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 2, 2, 2, 2, 0], [0, 1, 0, 2, 2, 2, 2, 0, 0, 0], [0, 2, 2, 2, 2, 0, 0, 1, 0, 0], [1, 2, 2, 2, 2, 2, 2, 2, 2, 0], [0, 1, 0, 0, 0, 1, 0, 0, 0, 0]]
Number of families: 6