持续更新中~
📍2073. 买票需要的时间
问题描述
有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
解题思路
- 初始化一个队列tp，将每个人的下标依次入队。
- 遍历队列tp，对于每个人，检查他的票数tickets[i]是否大于0。如果是，则他将花费1秒购买一张票，并将剩余的票数减1。如果他的票数大于0，则将其下标再次入队。
- 如果在队列中找到了位置k的人，并且他的票数为0，则购票过程结束，返回已经花费的时间。
- 如果队列中没有剩下的人，则购票过程结束，返回已经花费的时间。
代码实现
下面是相应的代码实现：
class Solution { public: int timeRequiredToBuy(vector<int>& tickets, int k) { queue<int> tp; int ans = 0; for (int i = 0; i < tickets.size(); i++) { tp.push(i); } while (!tp.empty()) { if (tickets[tp.front()]) { // 如果队列中的值当作下标在tickets中有值就进入 ans++; tickets[tp.front()]--; // 将tickets中对应值减1 if (tickets[tp.front()]) { // 如果tickets中对应值还是大于0则将下标加入队列 tp.push(tp.front()); } else if (tp.front() == k) { 如果tickets中对应值等于0而且下标是k的话 break; } } tp.pop(); // 将已访问的下标弹出队列 } return ans; } };
总结
该解决方案的时间复杂度为O(n)，其中n为购票人数。该解决方案使用队列来模拟购票过程，通过遍历队列来计算购票时间。
📍面试题 03.04. 化栈为队
问题描述
给定一个 MyQueue 类，要求使用两个栈来实现队列的功能，包括 push、pop、peek 和 empty 方法。
解题思路
题目要求使用两个栈来实现队列，其中一个栈用于入队操作，另一个栈用于出队和获取队头元素操作。具体思路如下：
- 创建两个栈 st1 和 st2，st1 用于入队操作，st2 用于出队和获取队头元素操作。
- 入队操作 push：将元素 x 直接压入 st1 栈中。
- 出队操作 pop：当 st2 栈为空时，将 st1 栈中的元素逐个弹出并压入 st2 栈，这样保证了 st2 的栈顶元素是最早入队的元素。然后从 st2 栈中弹出栈顶元素，即为队首元素。
- 获取队头元素操作 peek：与出队操作类似，先将 st1 栈中的元素逐个弹出并压入 st2 栈，然后取得 st2 的栈顶元素作为队头元素。
- 判断队列是否为空操作 empty：判断 st1 是否为空即可。
代码如下
class MyQueue { public: /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { st1.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { while (!st1.empty()) { st2.push(st1.top()); st1.pop(); } int res = st2.top(); st2.pop(); while (!st2.empty()) { st1.push(st2.top()); st2.pop(); } return res; } /** Get the front element. */ int peek() { while (!st1.empty()) { st2.push(st1.top()); st1.pop(); } int res = st2.top(); while (!st2.empty()) { st1.push(st2.top()); st2.pop(); } return res; } /** Returns whether the queue is empty. */ bool empty() { return st1.empty(); } private: stack<int> st1; stack<int> st2; };
📍1352. 最后 K 个数的乘积
问题描述
请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
- add(int num)
- 将数字 num 添加到当前数字列表的最后面。
- getProduct(int k)
- 返回当前数字列表中，最后 k 个数字的乘积。
- 你可以假设当前列表中始终 至少 包含 k 个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
解题思路
为了实现该数字乘积类 ProductOfNumbers，我们可以使用一个辅助数组 pre 来记录每个位置之前所有数字的乘积。同时，我们还需要一个变量 len 来记录当前数字列表中数字的个数。
在初始化 ProductOfNumbers 类时，我们将 pre[0] 初始化为 1，并将 len 初始化为 0。
对于 add 方法，如果 num 是 0，则将 len 置为 0，表示清空数字列表。否则，我们将 num 添加到数字列表末尾，并更新 pre[len] 为 pre[len-1] * num，即当前数字列表的乘积。
对于 getProduct 方法，我们首先判断数字列表中的数字个数是否小于 k，如果是，则说明无法计算乘积，直接返回 0。否则，我们可以通过 pre[len] / pre[len-k] 计算最后 k 个数字的乘积。
以上就是解题的思路，我们使用辅助数组 pre 来记录累积乘积，通过更新 pre 和 len 可以实现添加数字和计算乘积的功能。
我的代码
class ProductOfNumbers { public: #define N 40010 int len,pre[N]; ProductOfNumbers() { pre[0]=1; len=0; } void add(int num) { if (!num) len=0; else{ pre[++len]=num; pre[len]*=pre[len-1]; } } int getProduct(int k) { if (len<k) return 0; return pre[len]/pre[len-k]; } };
📍queue的基础知识
👨🚀小明：“这里我们先看一下文档是怎么说的。总结就是下面几点。”
🎈queue的介绍
- ✨队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
- ✨队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
- ✨底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
- ✨标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
👨🚀小明又给小星展示了一张表“它的常用函数有下面这些，每一个都是链接了文档的超链接，想了解更多就点它，后面接口说明有功能介绍”
🎈queue的常用函数
🎈queue的使用
👨🚀小明：”按照惯例，现在该做题练练手了“
🧚小星又恢复了活力，双手叉腰、鼻孔朝天道：”来吧，小小队列题“
👨🚀小明心想可不能打击他的士气，万一不学了就不好了，于是找到了这题：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示：
- 1 <= x <= 9
- 最多调用100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
接口如下：
class MyStack { public: MyStack() { } void push(int x) { } int pop() { } int top() { } bool empty() { } };
🧚小星脑袋极速运转：”用队列实现栈的功能，队列是先进先出，栈是先进后出，那么就需要两个队列，要把进入的数据倒来倒去，让后面的到前面就好了，其他的功能也是类似，把握好数据的顺序就可以了，这么简单？不愧是我，“
代码如下：
class MyStack { public: MyStack() { } void push(int x) { if(q1.empty()) { q1.push(x); while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } } else { q2.push(x); while(!q1.empty()) { q2.push(q1.front()); q1.pop(); } } } int pop() { if(q1.empty()) { int res=q2.front(); q2.pop(); return res; } else { int res=q1.front(); q1.pop(); return res; } } int top() { if(q1.empty()) { int res=q2.front(); return res; } else { int res=q1.front(); return res; } } bool empty() { return q1.empty()&&q2.empty(); } private: queue<int> q1; queue<int> q2; };
过了！！！
👨🚀小明：”嗯嗯，孺子可教也，不错，看来有点天赋的“（其实都在我的掌控之中）
🧚小星：”哼哼，不看看我是谁（得意）“
🧚小星：”你尽管讲，那年我双手插兜，不知道什么是对手。“
