Leetcode 2073. 买票需要的时间

一、题目描述

有 $n$ 个人前来排队买票,其中第 $0$ 人站在队伍 最前方,第 $(n - 1)$ 人站在队伍 最后方 。
给你一个下标从 $0$ 开始的整数数组 tickets,数组长度为 $n$ ,其中第 $i$ 人想要购买的票数为 tickets[i]
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ,如果需要购买更多票,他必须走到 队尾 重新排队(瞬间发生,不计时间)。如果一个人没有剩下需要买的票,那他将会 离开队伍
返回位于位置 $k$(下标从 0 开始)的人完成买票需要的时间(以秒为单位)
输入:tickets = [2,3,2], k = 2
输出:6
解释:
第一轮,队伍中的每个人都买到一张票,队伍变为 [1, 2, 1]
第二轮,队伍中的每个都又都买到一张票,队伍变为[0, 1, 0]。位置 2 的人成功买到 2 张票,用掉 $3$ + $3$ = $6$ 秒。
来源:Leetcode 2073. 买票需要的时间

二、解题报告

1、思路分析

(1) 符合先进先出,应用队列。
(2) 用一个结构体数组储存每个人所需的票数,和序号。
(3)一个for循环使所有人入队。
(4)使队头出队,并减少其需要的票数,时间增加。
(5)判断出队的人所需票数是否为0,若为否,重新加入队尾。
(6)若是0,则判断其序号是否是指定人序号,若是返回

2、代码详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef struct {
int idx;
int need;
}que;
int timeRequiredToBuy(int* tickets, int ticketsSize, int k){
que q[100000],tmp;
int time=0;
int front=0,rear=0;
for(int i=0;i<ticketsSize;i++){
q[rear].idx=i;
q[rear].need=tickets[i];
++rear;
}
while(front<rear){
tmp=q[front++];
tmp.need--;
time++;
if(tmp.need){
q[rear++]=tmp;
}else{
if(tmp.idx==k){
return time;
}
}
}
return time;
}

借鉴:英雄哪里出来

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2021-2023 lucky_dog
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信