《六月集训》第十六日——队列_这个过程会一直持续到队列里所有学生都不喜欢栈顶的纪念品为止

前言

这是六月集训的第十六日，今日的训练内容是 队列

解题报告

1.力扣933

原题链接

933. 最近的请求次数

题目概述

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
  保证 每次对 ping 的调用都使用比之前更大的 t 值。

解题思路

详细的解题思路见源码剖析中的注释，这是一道上个月做过的题。

源码剖析

typedef struct {
    int front;                      //头指针
    int rear;                       //尾指针
    int *que;
    int cal;
} RecentCounter;


RecentCounter* recentCounterCreate() {
    RecentCounter* obj =(RecentCounter*)malloc(sizeof(RecentCounter));
    obj->front=0;
    obj->rear=0;
    obj->cal=0;
    obj->que=(int*)malloc(sizeof(int)*10000);         //至多只需要调用10e4次
    return obj;
}

int recentCounterPing(RecentCounter* obj, int t) {
    obj->que[obj->rear++] = t;                        //首先将请求添加到队尾，并移动尾指针
    obj->cal++;
    if(t-obj->que[obj->front]>3000){                  //当t减去头指针指向元素大于3000就向后移动头指针
        while(1){
            obj->front++;
            obj->cal--;
            if(t-obj->que[obj->front]<=3000) break;
        }
    }
    return obj->cal;
}

void recentCounterFree(RecentCounter* obj) {
    free(obj->que);
    free(obj);
}
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

2.力扣1700

原题链接

1700. 无法吃午餐的学生数量

题目概述

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

• 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
• 否则，这名学生会 放弃这个三明治 并回到队列的尾部。
  这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

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

解题思路

在上个月曾经做过的一道题，在这道题里我没有使用到结构体，直接使用一下指针来模拟循环队列。详见源码剖析。

源码剖析

bool if_break(int b,int c,int d,int amax){     //预设一个判断是不是要break的函数，用起来稍微简洁一些
    if((b<amax)&&(c>0)&&(d<=c)) return false;
    else return true;
}
int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize){
    int ans = studentsSize;
    int i=0,j=0,cul=0;                        //i是student指针，j是sandwich指针,cul用于统计队列循环次数
    while(1){
        cul = 0;
        while(cul<=ans){                     //这说明队伍没背遍历完，也就是说不是所有人都不吃栈顶这个
            if(students[i]==sandwiches[j]){
                students[i] = 2;              //排除出这一项
                if(i==studentsSize-1) i = 0;
                else i++;
                j++;
                ans--;
                break;
            }
            if(if_break(j,ans,cul,studentsSize)) break;
            if(students[i]!=sandwiches[j]){
                if(students[i]==2){          //说明这一项被排除出去了
                    if(i==studentsSize-1) i = 0;
                    else i++;
                }else{
                    if(i==studentsSize-1) i = 0,cul++;
                    else i++,cul++;
                }
            }
            if(if_break(j,ans,cul,studentsSize)) break;
        }
        if(if_break(j,ans,cul,studentsSize)) break;
    }
    return ans;
}
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

3.力扣2073

原题链接

2073. 买票需要的时间

题目概述

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到  队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

解题思路

首先把数组填入一个队列之中，在填入的过程中，使用一个指针指向第 k 个结点的数据域，一旦当这个数据域变为0了说明循环已经结束了，具体的分析可以见源码剖析的注释部分，写的很详细。

源码剖析

```cpp
typedef struct{                                      //定义结点
    int data;
    struct Node* next;
}Node;
typedef struct{                                     //定义队列
    Node *head,*tail;
    int size;
}que;
void que_enter(que *a,int dt){                      //用尾插法插入队列
    Node *b = (Node*)malloc(sizeof(Node));          //申请内存
    b->data = dt;
    b->next = NULL;
    if(a->tail){                                    //如果尾结点不为空
        a->tail->next = b;                          //尾结点的next指针指向新插入的结点
        a->tail = b;                                //尾结点变为插入的结点
    }else{                                          //如果尾结点为空
        a->head = a->tail = b;                      //头结点和尾结点都是这个
    }
    a->size++;                                      //插入完结点后队列长度增加
}
void que_out(que *a){                               //将头结点移出队列
    Node *tmp = a->head;                            //定义一个中继结点，复制头结点，防止链表断开
    a->head = tmp->next;                            //使头结点变为tmp所指的下一个结点，原结点解链
    free(tmp);                                      //释放tmp结点
    a->size--;                                      //队列长度减一
    if(a->size==0) a->tail = NULL;                  //长度为0时使尾结点也一起指向空
}
int timeRequiredToBuy(int* tickets, int ticketsSize, int k){
    que *a;
    que_start(a);
    int *aim;
    int ans = 0;
    for(int i = 0;i<ticketsSize;++i){               //将数组填入队列中
        que_enter(a,tickets[i]);
        if(i==k-1) aim=&a->tail->data;              //使用一个指针标记k位所在结点的数据
    }
    while(1){                                       //当标记项不等于 0 时   
        a->head->data--;
        if(*aim==0){                                //如果是标记项直接结束循环防止bug
            ans++;
            break;
        }
        if(a->head->data==0){
            que_out(a);                             //不然就出队
        }
        else{                                       //否则把头结点放入尾巴
            que_enter(a,a->head->data);
            que_out(a);
        }
        ans++;
    }
    return ans;
}
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

4.力扣239

原题链接

239. 滑动窗口最大值

题目概述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

解题思路

这个思路会在最后几组的超大量数据的情况下超时，但暂时没有想到特别好的解题思路，先记录一下现在的做法，感觉后续有可能可以优化好。

思路就是，先看好第一组的数据的最大值，然后开始滑动窗口，如果新加入的值已经大于原本的最大值了，就直接写入答案数组中，否则就去看被划出去的元素是不是最大值，如果是的话就需要对窗口内的数据重新找一下最大值了，否则最大值仍然填入答案数组。这个思路之所以超时可能和重新遍历窗口有直接关系。

源码剖析

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    if (k == 1){
        *returnSize = numsSize;
        return nums;
    }
    int len = numsSize - k + 1;
    int *ret = (int*)malloc(sizeof(int)*len);
    *returnSize = len;
    int i,j,max;
    for(i = 0;i<1;++i){
        max = -10001;
        for(j = i;j<i+k;++j){
            max = max>nums[j]?max:nums[j];
        }
        ret[i] = max;
    }
    for(i = 1;i<len;++i){
        if(nums[i+k-1]>=max){
            max = nums[i+k-1];
            ret[i] = max;
            continue;
        }else{
            if(nums[i-1]==max){
                max = -10001;
                for(j = i;j<i+k;++j){
                    max = max>nums[j]?max:nums[j];
                }
            }
            ret[i] = max;
        }
    }
    return ret;
}
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