刷爆leetcode第九期 0020
刷爆leetcode第九期 0020
- 题目编号0020
- 题目分析
- 第一步 设计结构体
- 第二步 初始化结构体
- 第三步 跳到第四步
- 第四步 判断队列是否空或满
- 第五步 插入数据
- 第六步 删除数据
- 第七步 返回头数据
- 第八步 返回尾数据
- 总结
- 问题一
- 问题二
- 源码
题目编号0020
题目分析
这里直接看图
我们发现这里要求我们设计一个循环队列
这要怎么设计呢？
还是一样 我们先画图
我们首先假设只能储存四个数字
同学们看这张图能观察到什么呢？
是不是可以得到head 和 tail相等的时候整个队列为空
这里当插入一个数据之后 tail就往后走了一步
我们插入四个数据试试
咦 这个时候head和tail又相等了
这里好像队列满的条件和队列空的条件一样了
那么这个时候有没有什么好办法可以区分两种相等呢？
好像没有特别好的方法
那么我们加一个空数据
这样子可不可以呢？
这个时候呢？
我们好像可以使用公式
（tail+1）% （k+1） == head
来判断是否为满
那么我们接下来开始看题目
第一步 设计结构体
typedef struct
{
int*a;
int tail;
int front;
int k;
} MyCircularQueue;
我们需要用到的数据有
数组 头指针 尾指针 数字K
所以说我们定义这几个变量出来
第二步 初始化结构体
1 首先我们先动态开辟结构体的内存
2 因为需要k+1个数据的存贮空间 所以我们要开辟k+1个内存的大小
3 开始的头尾指针都设置为0
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue*));
cq->a = (int *)malloc(sizeof(int)*(k+1));
cq->tail = 0;
cq->front = 0
cq->k = k;
return cq;
}
第三步 跳到第四步
第四步 判断队列是否空或满
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
//断言
assert(obj);
//如果说 头等于尾就为空
//否则就为假
return head == tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
//assert
assert(obj);
//judge (tail +1) %(k+1)== head?
return (tail+1)%(k+1) == head ;
}
我们说有以上代码可以来判断
第五步 插入数据
这里主要分两种情况讨论
像这种情况 直接插入 tail+1就可以
但是如果是这样子呢？
像这个时候tail就要走到最前面了？
那么我们怎么来表示呢？
我们说
可以使用 tail=（tail+1）%（k+1）表示 想想看 是不是这样子
当tail等于4向前是不是就变成0了
所以我们开始敲代码
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
// 断言
assert(obj);
//这个时候我们首先要判断整个队列是否为满
//所以我们先要判断队列是否为满
//来都来了 顺便判断下是否为空
if ((obj->tail+1)%(obj->k+1) == obj->front)
{
return false;
}
else
{
obj->arr[obj->tail] = value;
//++obj->tail;
obj->tail++;
//obj->tail %= (obj->k+1);
//++obj->tail;
obj->tail %= (obj->k+1);
return true;
}
}
这样子就完成了
第六步 删除数据
这个的判断和前面一样
参考前面的代码就能够写出来了
int myCircularQueueFront(MyCircularQueue* obj)
{
if (obj->front == obj->tail)
{
return -1;
}
else
{
return obj->arr[obj->front];
}
}
第七步 返回头数据
int myCircularQueueFront(MyCircularQueue* obj)
{
if (obj->front == obj->tail)
{
return -1;
}
else
{
return obj->arr[obj->front];
}
}
这个很简单 返回头部的数据就可以
数组越界问题跟前面的处理结果相似
第八步 返回尾数据
这里要考虑一个特殊情况
就是当尾指针在数组的0位置的时候
这个时候我们单拎出来分类讨论就可以
如果是0的话 我们返回最后面的数据就可以
int myCircularQueueRear(MyCircularQueue* obj)
{
if (obj->front == obj->tail)
{
return -1;
}
else
{
if (obj->tail == 0)
{
return obj->arr[obj->k];
}
else
{
return obj->arr[obj->tail-1];
}
}
}
总结
问题一
今天写代码遇到了两个问题
一个是这个 我们开辟空间的时候 sizeof里面的内容填错了
上一次已经出现了一个没有填sizeof的问题 下次一定要注意
这里解决下就可以了
问题二
这里还有一个报错就是我们没有在前面声明就开始使用函数了
leetcode不会提前声明函数的
所以我们刷题的时候要自己来声明
源码
// 使用数组模式来设计
#include<stdbool.h>
typedef struct
{
int* arr;
int tail;
int front;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
cq->arr = (int *)malloc(sizeof(int)*(k+1));
cq->tail = 0;
cq->front = 0;
cq->k = k;
return cq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
// 断言
assert(obj);
//这个时候我们首先要判断整个队列是否为满
//所以我们先要判断队列是否为满
//来都来了 顺便判断下是否为空
if ((obj->tail+1)%(obj->k+1) == obj->front)
{
return false;
}
else
{
obj->arr[obj->tail] = value;
//++obj->tail;
obj->tail++;
//obj->tail %= (obj->k+1);
//++obj->tail;
obj->tail %= (obj->k+1);
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
assert(obj);
// 这里相同 如果队列为空就返回false 如果不为空再讨论
if(obj->front==obj->tail)
{
return false;
}
else
{
obj->front++;
obj->front %= (obj->k+1);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if (obj->front == obj->tail)
{
return -1;
}
else
{
return obj->arr[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if (obj->front == obj->tail)
{
return -1;
}
else
{
if (obj->tail == 0)
{
return obj->arr[obj->k];
}
else
{
return obj->arr[obj->tail-1];
}
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->tail+1)%(obj->k+1) == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->arr);
obj->arr=NULL;
free(obj);
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/