【刷题之路】LeetCode 2073. 买票需要的时间

一、题目描述

原题连接： 2073. 买票需要的时间
题目描述：
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

示例 1：

输入： tickets = [2,3,2], k = 2
输出： 6
解释：

• 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。
• 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。
  位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。

示例 2：

输入： tickets = [5,1,1,1], k = 0
输出： 8
解释：

• 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。
• 接下来的 4 轮，只有位置 0 的人在买票。
  位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。

提示：
n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

二、解题

1、方法1——记录每个人需要的时间

1.1、思路分析

很显然，我们的程序是要在第k个人买完票的时候停止。那么在第k个人买完票的时候，其他的所有人能买到的票数，也即买票的时间也就已经确定了(包括买完票和未买完票)。
具体的：
1、对于排在第k个人前面的或者第k个人(即i <= k)，因为他们的买票顺序一定先于第k个人(即使是重排到队尾也还是前面的人先重排)。

如果他们其中一人要买的票数小于第k个人要买的票数，那么他在第k个人买完票之前就能先买完票。而如果他要买的票数大于或等于第k个人需要买的票数，那么在第k个人买完票时他能买到的票数也和第k个人的相同。
所以对于位置小于或等于k的人，他在第k个人买完票时能买到的票数是min(tickets[i], tickets[k])。
2、而对于排在第k个人后面的人，如上面所说的，他们买票的顺序一定是在第k个人之后。所以当第k个人买完票时，如果他们中的每一个最多能买到的票数为tickets[k] - 1，而如果小于tickets[k] - 1，那就能买完。
所以对于位置大于k的人，他在第k个人买完票时能买到的票数是min(tickets[i], tickets[k] - 1)。

有题目所述我们得知，每个人买到的票数即是每个人所花的时间，所以我们可以先统计完每个人所花的时间，然后再算出这些事件的总和，最后返回这个总和即可。

1.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了:

int min(int x, int y) {
    return x < y ? x : y;
}
int timeRequiredToBuy(int* tickets, int ticketsSize, int k) {
    assert(tickets);
    int *time = (int*)malloc(ticketsSize * sizeof(int));
    if (NULL == time) {
        perror("malloc fail!\n");
        exit(-1);
    }
    int i = 0;
    for (i = 0; i < ticketsSize; i++) {
        if (i <= k) {
            time[i] = min(tickets[i], tickets[k]);
        } else {
            time[i] = min(tickets[i], tickets[k] - 1);
        }
    }
    int totalTime = 0; // 统计总时间
    for (i = 0; i < ticketsSize; i++) {
        totalTime += time[i];
    }
    free(time);
    return totalTime;
}
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

2、方法2——队列+记录下标

可能方法一的思路会有点儿抽象，有的朋友可能会看不懂。
但没关系，我这里还准备了第二种思路更简单易懂的方法，保证你能听得懂，只不过代码比方法一要稍微复杂“一点儿”。

2.1、思路分析

其实题目中描述的未买完票的人继续回到队尾排理解起来并不难，用队列实现也非常简单。但最主要的问题是当队列重排了之后我们并不能知道之后买完票的人是最初始队列中的第几个。
这个问题其实很容易解决，我们可以采用类似键值对的方式，创建一个结构体，里面保存好最初始队列中每个人对应的位置(下标)和票数(值)，就像下面这样：

typedef struct keyVal {
    int index;
    int val;
} keyVal;
1
2
3
4

然后我们再将队列保存的数据改成keyVal，再将初始队列中每个人对应的keyVal入队。这样在任何时候当队列中有人买完票，我们就知道是初始队列中的第几个人买完票了，那么这一题也就迎刃而解了。

2.2、先将队列实现一下

因为我是用的是C语言，所以没办法还是得先自己造轮子，先将队列实现一下。
(没想到吧，这年头还有人用纯C刷这么多的题)

// 创建一个结构体，保存数组中对应的之和下标
typedef struct keyVal {
    int index;
    int val;
} keyVal;

// 先将队列实现一下
// 重定义数据类型
typedef keyVal QDataType;
// 定义节点类型
typedef struct QueueNode {
	struct QueueNode* next;
	QDataType data;
} QueueNode;
// 定义队列类型
typedef struct Queue {
	QueueNode* head;
	QueueNode* tail;
} Queue;
// 队列的初始化
void QueueInit(Queue* pq);
// 队列的入队
void QueuePush(Queue* pq, QDataType x);
// 队列的出队
void QueuePop(Queue* pq);
// 返回队列的对头元素
QDataType QueueFront(Queue* pq);
// 返回队列的队尾元素
QDataType QueueBack(Queue* pq);
// 返回队列中的节点个数
int QueueSize(Queue* pq);
// 判断队列是否为空
bool QueueEmpty(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
// 队列的初始化
void QueueInit(Queue* pq) {
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
// 队列的入队
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	// 创建一个新节点
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newNode) {
		perror("malloc fail!\n");
		exit(-1);
	}
	newNode->data = x;
	if (NULL == pq->head) {
		pq->head = newNode;
		pq->tail = newNode;
		pq->tail->next = NULL;
	}
	else {
		pq->tail->next = newNode;
		pq->tail = pq->tail->next;
		pq->tail->next = NULL;
	}
}
// 队列的出队
void QueuePop(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	// 如果对头为空了，我们也要把队尾也给置空，避免野指针
	if (NULL == pq->head) {
		pq->tail = NULL;
	}
}
// 返回队列的对头元素
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
// 返回队列的队尾元素
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
// 返回队列中的节点个数
int QueueSize(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* cur = pq->head;
	int size = 0;
	while (cur) {
		size++;
		cur = cur->next;
	}
	return size;
}
// 判断队列是否为空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* pq) {
	assert(pq);
	if (!QueueEmpty(pq)) {
        QueueNode* cur = pq->head;
        QueueNode* next = cur->next;
        while (cur) {
            next = cur->next;
            free(cur);
            cur = next;
        }
    }
	
	pq->head = NULL;
	pq->tail = NULL;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

其实这里也就是将以前写过的队列CV大法了一遍，也就只改了个数据类型。并没有什么复杂或难的。
熟悉队列这个数据结构的朋友完全可以不看这里的实现啦。

2.3、代码实现

有了以上的思路和队列的实现，那我们写起代码来也就水到渠成了：

int timeRequiredToBuy(int* tickets, int ticketsSize, int k) {
    assert(tickets);
    int time = 0;
    Queue queue;
    QueueInit(&queue);
    int i = 0;
    keyVal *keyArray = (keyVal*)malloc(ticketsSize *sizeof(keyVal));
    if (NULL == keyArray) {
        perror("malloc fail!\n");
        exit(-1);
    }
    // 先完善好keyArray
    for (i = 0; i < ticketsSize; i++) {
        keyArray[i].index = i;
        keyArray[i].val = tickets[i];
    }
    // 再将keyArray中的元素入队列
    for (i = 0; i < ticketsSize; i++) {
        QueuePush(&queue, keyArray[i]);
    }
    
    while (1) {
        keyVal front = QueueFront(&queue);
        QueuePop(&queue);
        front.val--;
        if (front.val > 0) {
            QueuePush(&queue, front);
        }
        time++;
        if (front.index == k && front.val == 0) {
            break;
        }
    }
    QueueDestroy(&queue);
    free(keyArray);
    return time;
}

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
29
30
31
32
33
34
35
36
37
38