【LintCode 简单】1881. 飞机座位

ゞ浴缸里的玫瑰 2023-01-16 14:27 13阅读 0赞

1. 描述

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

编写一个函数

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzIzMTMzNzgz_size_16_color_FFFFFF_t_70][]

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*N
            number = 0
            seats_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)] = seat
    
            for n in range(1, N+1):
                if n not in seats_dict.keys():
                    number +=2
                else:
                    seats1 = ['B','C','D','E']
                    seats2 = ['F','G','H','I']
                    seats3 = ['D','E','F','G']
                    reserved_seats = seats_dict[n]
                    flag1 = True
                    for i in seats1:
                        if i in reserved_seats:
                            flag1=False
                            break
                    if flag1==True:
                        number+=1
                        reserved_seats.append('B')
                        reserved_seats.append('C')
                        reserved_seats.append('D')
                        reserved_seats.append('E')
                    flag2= True
                    for i in seats2:
                        if i in reserved_seats:
                            flag2=False
                            break
                    if flag2==True:
                        number+=1
                        reserved_seats.append('F')
                        reserved_seats.append('G')
                        reserved_seats.append('H')
                        reserved_seats.append('I')
                    flag3= True
                    for i in seats3:
                        if i in reserved_seats:
                            flag3=False
                            break
                    if flag3==True:
                        number+=1
            return number

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzIzMTMzNzgz_size_16_color_FFFFFF_t_70]: /images/20221022/932d291c181d4889b85a7b0faf97daad.png