pc访问手机网站跳转,做建筑材料的网站有哪些,摄影作品网站建设方案书,网站开发工资山东执行结果#xff1a;通过 题目#xff1a; 855 考场就坐
在考场里#xff0c;有 n 个座位排成一行#xff0c;编号为 0 到 n - 1。
当学生进入考场后#xff0c;他必须坐在离最近的人最远的座位上。如果有多个这样的座位#xff0c;他会坐在编号最小的座位上。(另外通过 题目 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* tmpobj-root;while(tmp!NULL){printf(%d ,tmp-id);tmptmp-next;}printf(\n);
}ExamRoom* examRoomCreate(int n) {ExamRoom* objmalloc(sizeof(ExamRoom));obj-lengthn;obj-rootNULL;return obj;}int examRoomSeat(ExamRoom* obj) {if(obj-rootNULL){obj-rootmalloc(sizeof(mylink));obj-root-id0;obj-root-nextNULL;return 0;}int max-1;if(obj-root-id!0) maxobj-root-id;mylink* max_link_beforeNULL;mylink* tmpobj-root;int diff0;while(tmp-next!NULL){ diff(tmp-next-id - tmp-id)/2;if(diffmax){maxdiff;max_link_beforetmp;}tmptmp-next;}//tmp 为末尾时diffobj-length -1 - tmp-id;if(diffmax){maxdiff;max_link_beforetmp;}if(max_link_beforeNULL){mylink* addmalloc(sizeof(mylink));add-id0;add-nextobj-root;obj-rootadd;return 0;}if(max_link_before-nextNULL){max_link_before-nextmalloc(sizeof(mylink));max_link_before-next-idobj-length-1;max_link_before-next-nextNULL;return obj-length-1;}else{mylink* addmalloc(sizeof(mylink));add-idmax_link_before-id max;add-nextmax_link_before-next;max_link_before-nextadd;return add-id;}}void examRoomLeave(ExamRoom* obj, int p) {mylink* tmpobj-root;mylink* beforeNULL;while(tmp!NULL){if(tmp-idp){if(beforeNULL){obj-roottmp-next;free(tmp);}else{before-nexttmp-next;free(tmp);}return;}beforetmp;tmptmp-next;}}void examRoomFree(ExamRoom* obj) {mylink* tmpobj-root;mylink* next;while(tmp!NULL){nexttmp-next;free(tmp);tmpnext;}free(obj);}解题思路
1. 数据结构定义
mylink 结构体表示链表中的一个节点包含座位号 id 和指向下一个节点的指针 next。ExamRoom 结构体表示考场包含两个成员length 表示考场总座位数root 指向链表的头节点。
2. print_obj 函数
作用打印考场信息包括总座位数和已分配的座位号。解题思路首先打印总座位数 length然后遍历链表打印每个节点的座位号 id。
3. examRoomCreate 函数
作用创建一个新的考场对象。解题思路使用 malloc 分配 ExamRoom 结构体所需的内存初始化 length 为传入的参数 nroot 初始化为 NULL表示链表为空最后返回创建的考场对象。
4. examRoomSeat 函数
作用在考场中分配一个座位并返回分配的座位号。解题思路 如果链表为空即还没有分配任何座位则在链表头部插入一个座位号为 0 的节点并返回 0。遍历链表计算相邻座位之间的最大间距 max 和该间距前的节点 max_link_before。考虑链表末尾与最后一个座位之间的间距。根据 max_link_before 的值在最大间距处插入一个新节点 如果 max_link_before 为 NULL则在链表头部插入新节点。如果 max_link_before-next 为 NULL则在链表尾部插入新节点。否则在 max_link_before 和 max_link_before-next 之间插入新节点。新节点的座位号 id 为 max_link_before-id max然后返回新节点的座位号。
5. examRoomLeave 函数
作用释放一个座位。解题思路遍历链表找到座位号为 p 的节点并将其从链表中删除。如果要删除的节点是头节点则更新头节点为下一个节点否则更新前一个节点的 next 指针跳过要删除的节点。最后释放要删除的节点的内存。
6. examRoomFree 函数
作用释放考场对象及其占用的所有内存。解题思路遍历链表释放每个节点的内存然后释放考场对象本身的内存。
