avatar

LeetCode-1386 安排电影院座位⭐

📝题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
如图一所示,电影院的观影厅中有 n 行座位,行编号从 1 到 n ,且每一行内总共有 10 个座位,列编号从 1 到 10 。

给你数组 reservedSeats ,包含所有已经被预约了的座位。比如说,researvedSeats[i]=[3,8] ,它表示第 3 行第 8 个座位被预约了。

请你返回最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位(比方说 [3,3] 和 [3,4])不是连续的座位,但是如果你可以将 4 人家庭拆成过道两边各坐 2 人,这样子是允许的。

示例 1:

输入:n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出:4
解释:图二所示是最优的安排方案,总共可以安排 4 个家庭。蓝色的叉表示被预约的座位,橙色的连续座位表示一个 4 人家庭。

示例 2:

输入:n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
输出:2

示例 3:

输入:n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
输出:4

限制:

· 1 <= n <= 10^9
· 1 <= reservedSeats.length <= min(10*n, 10^4)
· reservedSeats[i].length == 2
· 1 <= reservedSeats[i][0] <= n
· 1 <= reservedSeats[i][1] <= 10
· 所有 reservedSeats[i] 都是互不相同的。

图一

图二

📝思路

对于一个家庭而言,只有以下三种给他们安排座位的方法:

  • 安排位置 2,3,4,5;
  • 安排位置 4,5,6,7;
  • 安排位置 6,7,8,9。

因此每一排的位置 1 和位置 10 都是没有意义的,即使被预约了也对答案没有任何影响,所以,忽略所有在位置 1 和位置 10 的预约。同时可以发现,如果一排位置(不含位置 1 和位置 10 ,下同)没有被预约,那么恰好可以安排给两个家庭;如果一排位置被预约了至少一个座位,那么最多只能安排给一个家庭了。
对于只能安排一个家庭的情况,有两种方法计算。

方法一:查找。即利用STL自定义的函数暴力查找。

方法二:位运算
哈希表来存储每一排以及它们的二进制数。对于哈希映射中的每个键值对,键表示电影院中的一排,值表示这一排对应的二进制数。如果某一排没有任何位置被预约(例如上面的第三排),那么这一排一定可以安排给两个家庭,因此可以不必将这个键值对存放在哈希映射中。也就是说,只有某一排的某一座位被预约了,才将这一排放入哈希映射。
在处理完了所有的预约之后,遍历哈希映射。对于一个键值对 (row,bitmask),如何知道 row 这一排可以安排给几个家庭呢?根据之前的分析,被存储在哈希映射中的这些排最多只能安排给一个家庭,那么对于三种安排座位的方法:

  • 对于安排位置 2,3,4,5,如果 bitmask 中第 0,1,2,3 个二进制位均为 0,那么就可以安排给一个家庭;也就是说,bitmask 和 (11110000)2 的按位或值保持为 (11110000)2 不变;
  • 对于安排位置 4,5,6,7,如果 bitmask 中第 2,3,4,5 个二进制位均为 0,那么就可以安排给一个家庭;也就是说,bitmask 和 (11000011)2 的按位或值保持为 (11000011)2 不变;
  • 对于安排位置 6,7,8,9,如果 bitmask 中第 4,5,6,7 个二进制位均为 0,那么就可以安排给一个家庭;也就是说,bitmask 和 (00001111)2 的按位或值保持为 (00001111)2 不变;

这样以来,我们只需要将 bitmask 分别与 (11110000)2、 (11000011)2 和 (00001111)2进行按位或运算,如果其中有一个在运算后保持不变,那么 row 这一排就可以安排给一个家庭。
🐣:auto冒号遍历为 C++11 新特性,参见 C++11 auto冒号遍历C++之auto使用;温习一下左移/右移运算符

📝题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//想法一

int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
int result = 0;
unordered_map<int, unordered_set<int>> record;
for (auto i : reservedSeats){
if (i[1] >= 2 && i[1] <= 9)
record[i[0]].insert(i[1]);
}
result += (n - record.size()) * 2;

for (auto i : record){
bool side = false;
if (!(i.second.count(2) || i.second.count(3) || i.second.count(4) || i.second.count(5))) ++result, side = true;
if (!(i.second.count(6) || i.second.count(7) || i.second.count(8) || i.second.count(9))) ++result, side = true;
if (!(i.second.count(4) || i.second.count(5) || i.second.count(6) || i.second.count(7)) && !side) ++result;
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//想法二

int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
int left = 0b11110000; // 2~9
int middle = 0b11000011;
int right = 0b00001111;
int result = 0;

unordered_map<int, int> record;
for (auto iter : reservedSeats){
if (iter[1] >= 2 && iter[1] <= 9)
record[iter[0]] |= (1 << (iter[1]-2));
}
result += (n - record.size()) * 2;

for (auto iter : record){
if ((iter.second | left) == left || (iter.second | middle) == middle || (iter.second | right) == right)
++result;
}

return result;
}
Author:WhiteBeerHouse
Link:https://github.com/WhiteBeerHouse/WhiteBeerHouse.github.io/tree/master/2020/05/02/LeetCode-1386-%E5%AE%89%E6%8E%92%E7%94%B5%E5%BD%B1%E9%99%A2%E5%BA%A7%E4%BD%8D%E2%AD%90/
Copyright Notice:All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.