LeetCode

安排電影院座位

如上圖所示，電影院的觀影廳中有 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 人家庭。

解法：位運算判斷

解題思路： 其實思路很簡單，每行最多能容納兩個四人家庭，而第一個位置跟最后一個位置并不會對結果造成影響

所以我們用一個8位的數字來進行判斷，當第i個位置被預定之后，我們就將i-2位的數字變成1，沒被預定即為0，然后將該數字跟當前行用一個哈希表聯系起來

當預定數字全部遍歷完之后，我們只要取出哈希表中的值進行以下操作即可判斷是否能容納四人家庭

• 跟11110000按位或計算，如果結果仍是11110000,說明四個0的位置可以容納一個四人家庭
• 跟11000011按位或計算，同理
• 跟00001111按位或計算，同理

完整代碼：

class Solution {public int maxNumberOfFamilies(int n, int[][] reservedSeats) {int left = 0b11110000;int middle = 0b11000011;int right = 0b00001111;Map <Integer, Integer> occupied = new HashMap <Integer, Integer> ();for (int[] seat: reservedSeats) {if (seat[1] >= 2 && seat[1] <= 9) {int origin = occupied.containsKey(seat[0]) ? occupied.get(seat[0]) : 0;int value = origin | (1 << (seat[1] - 2));occupied.put(seat[0], value);}}int ans = (n - occupied.size()) * 2; //seat[1] = 1 || seat[1] = 10的就是坐兩組家庭的，他們不會出現在哈希表中for (Map.Entry <Integer, Integer> entry : occupied.entrySet()) {int row = entry.getKey(), bitmask = entry.getValue();if (((bitmask | left) == left) || ((bitmask | middle) == middle) || ((bitmask | right) == right)) {++ans; // 每一排座位只能坐一組家庭，因為出現在哈希表表示在[2,9]至少有一個座位被預約了}}return ans;} }

心得體會

其實看到這道題我就覺得挺簡單的，但是沒想到用哈希表和按位或計算來簡化代碼，用了一大堆if語句，后面受不了了就看了題解

題目和解法來源

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/cinema-seat-allocation
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

總結

以上是生活随笔為你收集整理的安排电影院座位--贪心算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。