A.每日一题：1386. 安排电影院座位

题目链接1386. 安排电影院座位中等算法原理解法一模拟时间复杂度O(mn)空间复杂度O(n)①直接开出 n 行 10 列的二维 boolean 数组如果对应位置已经被预订则直接标记为 true②循环遍历每一行对于每一行的固定四个位置做出如下标记1座位块12345 记为 t12座位块24567 记为 t23座位块36789 记为 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] 数组直接爆内存而绝大多数行完全没有被预订座位这些行直接可以放两个组完全不需要存储所以我们使用 哈希表 HashMapInteger,boolean[] 只保存有被预订座位的行key行号value该行10个座位占用标记①没有出现在 hash 中的行全部空位直接贡献 2 不用处理②只对有预订的行做三块窗口判断解法二位运算19ms击败38.37%时间复杂度O(m)空间复杂度O(m)大致思路不变~~一行一共10个座位编号1~10→数组下标0~9我们可以直接用一个 int 整数的 bit 位标记座位当 bit 0 时代表全是空位三个合法区间t1下标1234对应掩码0b11110bit:9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 1 1 1 1 0t2下标3456对应掩码0b1111000bit:9 8 7 6 5 4 3 2 1 0 0 0 0 1 1 1 1 0 0 0t3下标5678对应掩码0b111100000bit: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[][] gridnew boolean[n][10]; for(int[] r:reservedSeats) grid[r[0]-1][r[1]-1]true; int cnt0; for(int i0;in;i){ boolean t1true,t2true,t3true; //判断第一个固定位置是否可行但凡有一个被占就不可行 for(int j1;j5;j) if(grid[i][j]){t1false;break;} if(t1) cnt; //直接判断第三个位置避免重复 for(int j5;j9;j) if(grid[i][j]){t3false;break;} if(t3) cnt; if(!t1!t3){//如果第一个和第三个都不可行再判断第二个位置 for(int j3;j7;j) if(grid[i][j]){t2false;break;} if(t2) cnt; } } return cnt; } }class Solution { //1386. 安排电影院座位 //解法模拟 //哈希表优化 public int maxNumberOfFamilies(int n, int[][] reservedSeats) { MapInteger,boolean[] hashnew 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 t1true,t2true,t3true; //判断第一个固定位置是否可行但凡有一个被占就不可行 for(int j1;j5;j) if(grid[j]){t1false;break;} if(t1) cnt; //直接判断第三个位置避免重复 for(int j5;j9;j) if(grid[j]){t3false;break;} if(t3) cnt; if(!t1!t3){//如果第一个和第三个都不可行再判断第二个位置 for(int j3;j7;j) if(grid[j]){t2false;break;} if(t2) cnt; } } return cnt; } }class Solution { //1386. 安排电影院座位 //解法位运算 public int maxNumberOfFamilies(int n, int[][] reservedSeats) { //key行号valueint掩码记录该行哪些座位被占 MapInteger,Integer hashnew HashMap(); for(int[] r:reservedSeats){ int rowr[0]-1; int colr[1]-1; //如果hash里已经存过这一行取出之前的mask //如果hash里没有这一行返回0代表这一行座位全是空的 int maskhash.getOrDefault(row,0); //把 col 对应的 bit 置为1 mask|(1col);//col必然不为0 hash.put(row,mask); } //没有任何预订的行每行直接放2组 int cnt(n-hash.size())*2; //三个区间掩码 final int mask10b11110;//下标1234 final int mask20b1111000;//下标3456 final int mask30b111100000;//下标5678 for(int mask:hash.values()){ boolean t1(maskmask1)0; if(t1) cnt; boolean t3(maskmask3)0; if(t3) cnt; //左右都不行才检查中间t2 if(!t1!t3){ boolean t2(maskmask2)0; if(t2) cnt; } } return cnt; } }