【LintCode 简单】1881. 飞机座位

座位"/>

【LintCode 简单】1881. 飞机座位

1. 描述

您的任务是为四口之家尽可能多的分配座位。一个四口之家必须占领一排当中连续的四个座位。过道上的座位（例如2C和2D）不被认为是彼此相邻的。一家人被过道分开是可以的，但在这种情况下必须每一边坐两个。

编写一个函数

class Solution {public int solution(int N,String S};

函数中N表示有N排座位，S表示已经提供出去的座位，函数返回剩下的座位能坐四口之家的最大值。例如， N = 2，S = '1A 2F 1C’,你的函数应该返回2.下图给出了做法。

2. 样例

输入: 
N = 2，S = "1A 2F 1C"
输出: 
2
输入: 
N = 1，S = ""
输出: 
2

3. 代码

解题思路：首先通过观察和理解问题描述，可以知道 1）每一排最多能够安排2个四口之家 2）座位A和J是否被reserved和结果没有关系 （这里需要注意 座位是ABC DEFG HIJ 和图片里不相符合，需要按照测试用例的编码）

大概可以分成几种情况：1）当没有任何预定时候，直接可以返回 2*N

                                          2）首先对S数组分析，将预定的座位提取到一个字典 seats_dict={}中，然后在后续循环中，每排提取当行已经被预定的座位号，这里需要注意的是，当找到一个四口之家可以坐下后，需要往list里append新的被预定的座位

import re
class Solution:"""@param N:  the number of rows@param S: a list of reserved seats@return: An integer"""def solution(self, N, S):# Write your code here.if S == '':return 2*Nnumber = 0seats_dict = {}for i in S.split(' '):digital = i[0:-1]letter = i[-1]if int(digital) not in seats_dict.keys():seat = []else:seat = seats_dict[int(digital)]seat.append(letter)seats_dict[int(digital)] = seatfor n in range(1, N+1):if n not in seats_dict.keys():number +=2else:seats1 = ['B','C','D','E']seats2 = ['F','G','H','I']seats3 = ['D','E','F','G']reserved_seats = seats_dict[n]flag1 = Truefor i in seats1:if i in reserved_seats:flag1=Falsebreakif flag1==True:number+=1reserved_seats.append('B')reserved_seats.append('C')reserved_seats.append('D')reserved_seats.append('E')flag2= Truefor i in seats2:if i in reserved_seats:flag2=Falsebreakif flag2==True:number+=1reserved_seats.append('F')reserved_seats.append('G')reserved_seats.append('H')reserved_seats.append('I')flag3= Truefor i in seats3:if i in reserved_seats:flag3=Falsebreakif flag3==True:number+=1return number