【算法集训】基础数据结构:五、队列(续)
2023-12-14 22:29:37
第二题 LCR 041. 数据流中的移动平均值
https://leetcode.cn/problems/qIsx9U/description/
typedef struct {
int head; //记录头部
int tail; //记录尾部
int size; //记录长度
int data[10001]; //记录每个数据
double sum; //记录队列的和
} MovingAverage;
/** Initialize your data structure here. */
MovingAverage* movingAverageCreate(int size) {
MovingAverage * obj = (MovingAverage *)malloc(sizeof(MovingAverage));
obj->head = 0;
obj->tail = -1;
obj->size = size;
obj->sum = 0;
return obj;
}
double movingAverageNext(MovingAverage* obj, int val) {
obj->data[++obj->tail] = val;
obj->sum += val;
if(obj->tail - obj->head + 1 > obj->size) {
obj->sum -= obj->data[obj->head];
++obj->head;
}
int size = obj->tail - obj->head + 1; //当前队列的长度
return obj->sum / size;
}
void movingAverageFree(MovingAverage* obj) {
}
/**
* Your MovingAverage struct will be instantiated and called as such:
* MovingAverage* obj = movingAverageCreate(size);
* double param_1 = movingAverageNext(obj, val);
* movingAverageFree(obj);
*/
第三题 1700. 无法吃午餐的学生数量
https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/description/
int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize) {
int head = 0;
int tail = -1;
int data[100001];
for(int i = 0; i < studentsSize; ++i) {
data[++tail] = students[i];
}
int sandIdx = 0;
int gg = 0; //如果一直不满足条件防止无限循环下去
while(head <= tail) {
if(data[head] == sandwiches[sandIdx]) {
// 如果相等的话当前学生会拿走食物,所以head++退出队列
++head;
++sandIdx;
// 如果遍历完都满足,则返回0;
if(sandwichesSize == sandIdx) { //这里sandwichesSize不-1的原因是上面sandIdx满足条件后+1,所以这里直接比
return 0;
}
}else {
data[++tail] = data[head];
head++;
if(gg++ > 10000) {
return tail - head + 1;
}
}
}
return tail - head + 1;
}
文章来源:https://blog.csdn.net/m0_51425296/article/details/134933991
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!