当前位置：首页 > article >正文

Leetcode打卡：考场就坐

article 2024/12/24 16:08:26

执行结果：通过

题目： 855 考场就坐

在考场里，有 n 个座位排成一行，编号为 0 到 n - 1。

当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

设计一个模拟所述考场的类。

实现 ExamRoom 类：

ExamRoom(int n) 用座位的数量 n 初始化考场对象。
int seat() 返回下一个学生将会入座的座位编号。
void leave(int p) 指定坐在座位 p 的学生将离开教室。保证座位 p 上会有一位学生。

示例 1：

输入：
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
输出：
[null, 0, 9, 4, 2, null, 5]
解释：
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // 返回 0，房间里没有人，学生坐在 0 号座位。
examRoom.seat(); // 返回 9，学生最后坐在 9 号座位。
examRoom.seat(); // 返回 4，学生最后坐在 4 号座位。
examRoom.seat(); // 返回 2，学生最后坐在 2 号座位。
examRoom.leave(4);
examRoom.seat(); // 返回 5，学生最后坐在 5 号座位。

提示：

1 <= n <= 109
保证有学生正坐在座位 p 上。
seat 和 leave 最多被调用 104 次。

代码以及解题思路

代码：

typedef struct mylink {
    int id;
    struct mylink *next;
} mylink;


typedef struct {
    int length;
    mylink* root;
} ExamRoom;
void print_obj(ExamRoom *obj)
{
    printf("%d ",obj->length);
    mylink* tmp=obj->root;
    while(tmp!=NULL)
    {
        printf("%d ",tmp->id);
        tmp=tmp->next;
    }
    printf("\n");
}


ExamRoom* examRoomCreate(int n) {
     ExamRoom* obj=malloc(sizeof(ExamRoom));
    obj->length=n;
    obj->root=NULL;
    return obj;

}

int examRoomSeat(ExamRoom* obj) {
    if(obj->root==NULL)
    {
        obj->root=malloc(sizeof(mylink));
        obj->root->id=0;
        obj->root->next=NULL;
        return 0;
    }
    int max=-1;
    if(obj->root->id!=0) max=obj->root->id;
    mylink* max_link_before=NULL;
    mylink* tmp=obj->root;
    int diff=0;
    while(tmp->next!=NULL)
    {   
        diff=(tmp->next->id - tmp->id)/2;
        if(diff>max)
        {
            max=diff;
            max_link_before=tmp;
        }
        tmp=tmp->next;
    }
    //tmp 为末尾时
    diff=obj->length -1 - tmp->id;
    if(diff>max)
    {
        max=diff;
        max_link_before=tmp;
    }
    if(max_link_before==NULL)
    {
        mylink* add=malloc(sizeof(mylink));
        add->id=0;
        add->next=obj->root;
        obj->root=add;
        return 0;
    }
    if(max_link_before->next==NULL)
    {
        max_link_before->next=malloc(sizeof(mylink));
        max_link_before->next->id=obj->length-1;
        max_link_before->next->next=NULL;
        return obj->length-1;
    }
    else
    {
        mylink* add=malloc(sizeof(mylink));
        add->id=max_link_before->id + max;
        add->next=max_link_before->next;
        max_link_before->next=add;
        return add->id;
    }

}

void examRoomLeave(ExamRoom* obj, int p) {
     mylink* tmp=obj->root;
    mylink* before=NULL;
    while(tmp!=NULL)
    {
        if(tmp->id==p)
        {
            if(before==NULL)
            {
                obj->root=tmp->next;
                free(tmp);
            }
            else
            {
                before->next=tmp->next;

                free(tmp);
            }
            return;
        }
        before=tmp;
        tmp=tmp->next;
    }

}

void examRoomFree(ExamRoom* obj) {
    mylink* tmp=obj->root;
    mylink* next;
    while(tmp!=NULL)
    {
        next=tmp->next;
        free(tmp);
        tmp=next;
    }
    free(obj);

}

解题思路：

1. 数据结构定义

mylink 结构体：表示链表中的一个节点，包含座位号 id 和指向下一个节点的指针 next。
ExamRoom 结构体：表示考场，包含两个成员：length 表示考场总座位数，root 指向链表的头节点。

2. `print_obj` 函数

作用：打印考场信息，包括总座位数和已分配的座位号。
解题思路：首先打印总座位数 length，然后遍历链表，打印每个节点的座位号 id。

3. `examRoomCreate` 函数

作用：创建一个新的考场对象。
解题思路：使用 malloc 分配 ExamRoom 结构体所需的内存，初始化 length 为传入的参数 n，root 初始化为 NULL（表示链表为空），最后返回创建的考场对象。

4. `examRoomSeat` 函数

作用：在考场中分配一个座位，并返回分配的座位号。
解题思路：
1. 如果链表为空（即还没有分配任何座位），则在链表头部插入一个座位号为 0 的节点，并返回 0。
2. 遍历链表，计算相邻座位之间的最大间距 max 和该间距前的节点 max_link_before。
3. 考虑链表末尾与最后一个座位之间的间距。
4. 根据 max_link_before 的值，在最大间距处插入一个新节点：
  - 如果 max_link_before 为 NULL，则在链表头部插入新节点。
  - 如果 max_link_before->next 为 NULL，则在链表尾部插入新节点。
  - 否则，在 max_link_before 和 max_link_before->next 之间插入新节点。
5. 新节点的座位号 id 为 max_link_before->id + max，然后返回新节点的座位号。