【刷题之路】LeetCode 1700. 无法吃午餐的学生数量_leetcode1700分

一、题目描述

原题连接： 1700. 无法吃午餐的学生数量
题目描述：
学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。

示例 1：

输入： students = [1,1,0,0], sandwiches = [0,1,0,1]
输出： 0
解释：
-最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
-最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
-最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。
-最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
-最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
-最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
-最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
-最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。

示例 2：

输入： students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
输出： 3

提示：
1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] 要么是 0 ，要么是 1 。
students[i] 要么是 0 ，要么是 1 。

二、解题

1、思路分析

虽然这道题的题目挺长的，但是做起来却很简单，大家应该都能想到这题要用队列来做。
就像题目所描述的那样，我们让所有学生排成一个队列，如果队头学生喜欢的三明治和栈顶的三明治一样，那我们就让队头学生和栈顶的三明治出队和出栈：

而当队头的学生喜欢的三明治和栈顶的三明治不一样时，我们就将队头的学生转移到队尾(先将队头元素入到队尾，在将队头元素出队)：

那么问题来了，题目要求的结束条件是：“这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。”
因为队列的规则是先进先出，所以我们每次只能知道队头学生喜欢的三明治类型，而不能知道具体每个学生的喜好，而且根据题目描述队列的长度有可能时时在变化，所以我们也不能单纯的统计个数。
那该怎么解决这个问题呢?
其实，当队列中所有的学生都不喜欢栈顶的三明治时，一定会出现这样的情况，就是会有连续的个数为队列长度的学生都不喜欢栈顶的三明治。所以我们就可以设置一个变量hungery来记录连续有多少个学生不喜欢堆栈的三明治。
1、当有一个学生不喜欢栈顶的三明治时，就让hungery自加1。
2、当有一个学生喜欢栈顶的三明治时，就让hungery归零，因为已经不连续了。

2、代码实现

2.1、先将队列实现一

因为我选用的是C语言(唉，其实是我现在只学到了C语言)，所以没办法，还得自己先造轮子。我们先得把队列实现一下：

// 重定义数据类型
typedef int 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);
	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

2.2、代码实现

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

int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize) {
    assert(students && sandwiches);
    Queue queue;
    QueueInit(&queue);
    int i = 0;
    // 先将学生全都入队
    for (i = 0; i < studentsSize; i++) {
        QueuePush(&queue, students[i]);
    }
    int hungery = 0; // 统计连续有多少个学生吃不到三明治
    i = 0;
    // 三明治不需要用栈存，直接遍历控制即可
    while (i < sandwichesSize) {
        if (sandwiches[i] == QueueFront(&queue)) {
            QueuePop(&queue);
            i++;
            hungery = 0;
        } else {
            QueuePush(&queue, QueueFront(&queue));
            QueuePop(&queue);
            hungery++;
        }
        if (hungery == QueueSize(&queue) || QueueEmpty(&queue)) {
            break;
        }
    }
    QueueDestroy(&queue);
    return hungery; 
}
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