参加考试的最大学生数
难度:
标签:
题目描述
Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.
Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible.
Students must be placed in seats in good condition.
Example 1:
Input: seats = [["#",".","#","#",".","#"], [".","#","#","#","#","."], ["#",".","#","#",".","#"]] Output: 4 Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.
Example 2:
Input: seats = [[".","#"], ["#","#"], ["#","."], ["#","#"], [".","#"]] Output: 3 Explanation: Place all students in available seats.
Example 3:
Input: seats = [["#",".",".",".","#"], [".","#",".","#","."], [".",".","#",".","."], [".","#",".","#","."], ["#",".",".",".","#"]] Output: 10 Explanation: Place students in available seats in column 1, 3 and 5.
Constraints:
seatscontains only characters'.' and'#'.m == seats.lengthn == seats[i].length1 <= m <= 81 <= n <= 8
代码结果
运行时间: 30 ms, 内存: 16.5 MB
/*
* Java Stream cannot be directly used to solve this problem efficiently due to its complex dynamic programming nature.
* However, we can demonstrate the initial part of the solution to create the mask and check validity using streams.
*/
import java.util.stream.*;
public class SolutionStream {
public int maxStudents(char[][] seats) {
int m = seats.length, n = seats[0].length;
int[] dp = new int[1 << n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 0; i < m; i++) {
int[] nextDp = new int[1 << n];
Arrays.fill(nextDp, -1);
IntStream.range(0, 1 << n).filter(mask -> dp[mask] != -1).forEach(mask -> {
IntStream.range(0, 1 << n).forEach(newMask -> {
boolean valid = IntStream.range(0, n).allMatch(k -> {
if ((newMask & (1 << k)) == 0) return true;
if (seats[i][k] == '#') return false;
if (k > 0 && (newMask & (1 << (k - 1))) != 0) return false;
if (k < n - 1 && (newMask & (1 << (k + 1))) != 0) return false;
if (k > 0 && (mask & (1 << (k - 1))) != 0) return false;
if (k < n - 1 && (mask & (1 << (k + 1))) != 0) return false;
return true;
});
if (valid) {
int count = (int) IntStream.range(0, n).filter(k -> (newMask & (1 << k)) != 0).count();
nextDp[newMask] = Math.max(nextDp[newMask], dp[mask] + count);
}
});
});
dp = nextDp;
}
return Arrays.stream(dp).max().orElse(0);
}
}解释
方法:
该题解采用动态编程与位运算相结合的方法来求解。首先，将教室的座位状态从字符数组转换为整数数组，每个整数的二进制位表示一行中的座位是否可用（'.' 表示可用，对应位为1）。接着，定义一个递归函数 `dfs` 来尝试所有可能的座位安排。对于每一行，递归函数尝试将学生放在当前可用的座位上，同时确保不违反学生之间的视线要求（不能看到左上、右上、左边、右边的同学）。`dfs` 函数使用记忆化以避免重复计算，提高效率。最终，通过递归检查所有行的所有可能座位安排，找出可以容纳的最大学生数。
时间复杂度:
O(m * 4^n)
空间复杂度:
O(m * 4^n)
代码细节讲解
🦆
题解中的`dfs`函数中的参数`i`, `j`, `k`各代表什么含义？在递归中它们是如何变化的？
▷🦆
在位运算中，`k << 1`和`k >> 1`操作是如何帮助检查左上和右上的座位约束的？这是否意味着左右方向的座位也是被考虑的？
▷🦆
题解提到`记忆化存储`用于避免重复计算，请问具体是如何实现的？`@cache`装饰器具体是如何工作的？
▷