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

Leetcode打卡：考场就坐

news 2025/6/26 11:57:04

执行结果：通过

题目： 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，然后返回新节点的座位号。