題目鏈接：https://leetcode-cn.com/problems/cinema-seat-allocation/

在一個(gè)電影院里，有n行座位，每行10個(gè)，被過道分隔為左邊三個(gè)中間四個(gè)右邊三個(gè)。四口之家去看電影，有三種坐法，一是都坐中間，二是坐左邊過道的兩邊（各坐兩個(gè)人），三是坐右邊過道兩邊（各坐兩個(gè)人）。但是有的座位已經(jīng)被預(yù)約了，問電影院還能夠坐多少個(gè)這樣的四口之家？
note：$1<=n<=10^9$

分析

首先關(guān)注數(shù)據(jù)量，這里的數(shù)據(jù)量是億級(jí)的，所以$O(n)$復(fù)雜度一定會(huì)超時(shí)的。經(jīng)過觀察，能夠得到如果某一行座位沒有被預(yù)約，那么就能夠安排兩家人，要是被預(yù)約了我們就要根據(jù)預(yù)約情況來判斷能夠安排多少家庭。我們只處理有預(yù)約的座位行，采用位運(yùn)算，記錄被預(yù)約的行。

代碼：

class Solution { public:int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {unordered_map<int,int> record;for(auto &vec:reservedSeats){record[vec[0]]|=(1<<(vec[1]-1));//記錄保留位置}int ans=(n-record.size())*2;int a=0b0111111110;int b=0b0000011110;int c=0b0111100000;int d=0b0001111000;for(auto &p:record){if((p.second&a)==0){ans+=2;continue;}if((p.second&b)==0){ans+=1;continue;}if((p.second&c)==0){ans+=1;continue;}if((p.second&d)==0){ans+=1;continue;}}return ans;}};

總結(jié)

以上是生活随笔為你收集整理的leetcode 1386. 安排电影院座位 位运算的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。