1700. 无法吃午餐的学生数量：简单模拟+简单分类思想

题目描述

这是 力扣上的 1700. 无法吃午餐的学生数量，难度为 简单。

题目分析

题目说了一啪啦，示例也写了一啪啦，实际上题目就是给了我们两个数组，students 和 sandwiches 分别表示学生队列和三明治栈，从数组的索引 0 开始分别为队头，和栈顶，数组中的内容为：

• 0 表示圆形三明治
• 1 表示圆形三明治

学生排队去看栈顶的三明治，是自己喜欢的就拿走，不是的话，自己就改改跑到队尾去等待下一次的机会，要求我们计算出吃不到三明治的学生数

思考

对于学生吃三明治，难道我们需要去模拟真实排队场景去取餐吗？写一个死循环，然后逐个去看栈顶是否是当前学生喜欢的，喜欢就拿走，不喜欢就回到队尾，那么这真的注定是一个死循环了，都没有退出的条件

其实我们可以这么来思考，对于学生去拿三明治，实际上学生和三明治是没有一一对应关系的，只要栈顶是学生自己喜欢的，就可以拿走

那么对于三明治栈来说，学生在队列中的位置跟他是没有半毛钱关系的，我们应该重点关注的是当前栈顶的这个三明治，在剩下的学生中，是否还有人喜欢吃，如果有那么游戏还可以继续，如果没有了，那么无论循环多少次，都不会有学生拿走这个栈顶的三明治了

好了，这个时候，问题就转换到我们可以去记录 students 数组中有多少人喜欢吃圆形三明治，记为 circulercirculercirculer，喜欢吃方形三明治的人记为 squaresquaresquare

此时，我们遍历栈，

• 如果栈顶是圆形且剩下的学生人数中还有人喜欢吃圆形即circuler>0circuler>0circuler>0，那么就弹出顶，且 circuler−−circuler--circuler−−，
• 同理，如果有人喜欢吃方形，且还有人喜欢吃方形即square>0square>0square>0，那么就弹出栈顶，且square−−square--square−−

如果不满足上述 2 种情况，那么我们就需要遍历 sandwiches 数组，剩下的学生都不会喜欢吃的，直接计算剩下的学生数就可以了

接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现

Golang 的实现方式：

• 先计算 students 喜欢吃圆形和方形的人数
• 去遍历 sandwiches 栈顶是否有学生喜欢吃

func countStudents(students []int, sandwiches []int) int {
    var (
        square int
        circuler int
    )
    // 记录喜欢圆形和方形的学生数
    for i := range students {
        if students[i] == 0{
            circuler++
        }else{
            square++
        }
    }
    for i := range sandwiches {
        // 判断是否还有喜欢吃圆形的学生
        if sandwiches[i] == 0 && circuler>0{
            circuler--
             // 判断是否还有喜欢吃方形的学生
        }else if sandwiches[i] == 1 && square > 0{
            square--
        }else{
            break
        }
    }
    return circuler + square
}

这种实现方式，咱们的时间复杂度为 O(n) ， n 为学生数组的长度，空间复杂度为 O(1)，我们只引入了常数级别的空间消耗

今天就到这里，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~