题目链接：1386. 安排电影院座位（中等）
算法原理：
解法一：模拟
时间复杂度O(m+n)
空间复杂度O(n)
①直接开出 n 行 10 列的二维 boolean 数组，如果对应位置已经被预订，则直接标记为 true
②循环遍历每一行，对于每一行的固定四个位置，做出如下标记：
1）座位块1：2，3，4，5 记为 t1
2）座位块2：4，5，6，7 记为 t2
3）座位块3：6，7，8，9 记为 t3
从左往右遍历，检查 t1 是否全未被占用，如果是，总数 cnt++，为了最大化总数，不必检查 t2 ，直接去检查 t3
如果 t1 和 t3 都是 false，则再去检查 t2 这个中间位置能否坐一个小组
③但是这种做法会导致超出内存限制，因为这个做法的空间复杂度为 O(N)，而测试用例的 N 可以非常大，我们直接开 n 行的空间会直接引发超出内存限制~~
哈希表优化
17ms击败67.17%
时间复杂度O(m)
空间复杂度O(m)
原问题痛点就在于，题目测试用例的 n 可以达到 10⁹，直接开 boolean[n][10] 数组直接爆内存，而绝大多数行完全没有被预订座位，这些行直接可以放两个组，完全不需要存储
所以我们使用 哈希表 HashMap<Integer,boolean[]> 只保存有被预订座位的行，key=行号，value=该行10个座位占用标记
①没有出现在 hash 中的行：全部空位，直接贡献 2 ，不用处理
②只对有预订的行做三块窗口判断
解法二：位运算
19ms击败38.37%
时间复杂度O(m)
空间复杂度O(m)
大致思路不变~~
一行一共10个座位（编号1~10→数组下标0~9），我们可以直接用一个 int 整数的 bit 位标记座位
当 bit = 0 时代表全是空位
三个合法区间：
t1：下标1，2，3，4，对应掩码：0b11110
bit:9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 1 1 1 1 0t2：下标3，4，5，6，对应掩码：0b1111000
bit:9 8 7 6 5 4 3 2 1 0 0 0 0 1 1 1 1 0 0 0t3：下标5，6，7，8，对应掩码：0b111100000
bit:9 8 7 6 5 4 3 2 1 0 0 1 1 1 1 0 0 0 0 0当（mask&掩码）==0，代表区间内没有座位被占，可以坐一组
掩码只把关心的 4 位设成1，其他全部都是 0，按位与只会保留这 4 位的信息，其他 bit 直接清零丢弃~~
Java代码：
class Solution { //1386. 安排电影院座位 //解法：模拟 //未优化，超出内存限制 public int maxNumberOfFamilies(int n, int[][] reservedSeats) { boolean[][] grid=new boolean[n][10]; for(int[] r:reservedSeats) grid[r[0]-1][r[1]-1]=true; int cnt=0; for(int i=0;i<n;i++){ boolean t1=true,t2=true,t3=true; //判断第一个固定位置是否可行，但凡有一个被占就不可行 for(int j=1;j<5;j++) if(grid[i][j]){t1=false;break;} if(t1) cnt++; //直接判断第三个位置，避免重复 for(int j=5;j<9;j++) if(grid[i][j]){t3=false;break;} if(t3) cnt++; if(!t1&&!t3){//如果第一个和第三个都不可行，再判断第二个位置 for(int j=3;j<7;j++) if(grid[i][j]){t2=false;break;} if(t2) cnt++; } } return cnt; } }class Solution { //1386. 安排电影院座位 //解法：模拟 //哈希表优化 public int maxNumberOfFamilies(int n, int[][] reservedSeats) { Map<Integer,boolean[]> hash=new HashMap<>(); for(int[] r:reservedSeats){ //没有这一行，就新建一个长度为 10 的 boolean 数组 hash.computeIfAbsent(r[0]-1,_->new boolean[10]); hash.get(r[0]-1)[r[1]-1]=true; } //所有无预订的行，每行可以直接坐两组 int cnt=(n-hash.size())*2; //遍历只有预订的行 for(boolean[] grid:hash.values()){ boolean t1=true,t2=true,t3=true; //判断第一个固定位置是否可行，但凡有一个被占就不可行 for(int j=1;j<5;j++) if(grid[j]){t1=false;break;} if(t1) cnt++; //直接判断第三个位置，避免重复 for(int j=5;j<9;j++) if(grid[j]){t3=false;break;} if(t3) cnt++; if(!t1&&!t3){//如果第一个和第三个都不可行，再判断第二个位置 for(int j=3;j<7;j++) if(grid[j]){t2=false;break;} if(t2) cnt++; } } return cnt; } }class Solution { //1386. 安排电影院座位 //解法：位运算 public int maxNumberOfFamilies(int n, int[][] reservedSeats) { //key：行号，value：int掩码，记录该行哪些座位被占 Map<Integer,Integer> hash=new HashMap<>(); for(int[] r:reservedSeats){ int row=r[0]-1; int col=r[1]-1; //如果hash里已经存过这一行，取出之前的mask //如果hash里没有这一行，返回0，代表这一行座位全是空的 int mask=hash.getOrDefault(row,0); //把 col 对应的 bit 置为1 mask|=(1<<col);//col必然不为0 hash.put(row,mask); } //没有任何预订的行，每行直接放2组 int cnt=(n-hash.size())*2; //三个区间掩码 final int mask1=0b11110;//下标1，2，3，4 final int mask2=0b1111000;//下标3，4，5，6 final int mask3=0b111100000;//下标5，6，7，8 for(int mask:hash.values()){ boolean t1=(mask&mask1)==0; if(t1) cnt++; boolean t3=(mask&mask3)==0; if(t3) cnt++; //左右都不行，才检查中间t2 if(!t1&!t3){ boolean t2=(mask&mask2)==0; if(t2) cnt++; } } return cnt; } }
