刷爆leetcode第八期

简介: 刷爆leetcode第八期

题目一 设计循环队列

题目分析

这里直接看图

我们发现这里要求我们设计一个循环队列

这要怎么设计呢?

还是一样 我们先画图

我们首先假设只能储存四个数字

同学们看这张图能观察到什么呢?

是不是可以得到front 和 rear相等的时候整个队列为空

这里当插入一个数据之后 rear就往后走了一步

我们插入四个数据试试

咦 这个时候front和rear又相等了

这里好像队列满的条件和队列空的条件一样了

那么这个时候有没有什么好办法可以区分两种相等呢?

好像没有特别好的方法

那么我们加一个空数据

这样子可不可以呢?

这个时候呢?

我们好像可以使用公式

(tail+1)% (k+1) == head

来判断是否为满

这不就形成循环了嘛

那么我们接下来开始看题目、

第一步 设计结构体

typedef struct {
    int*a;
    int front;
    int rear;
    int k;
} MyCircularQueue;

我们需要用到的数据有

数组 头指针 尾指针 数字K

所以说我们定义这几个变量出来

第二步 初始化结构体

1 首先我们先动态开辟结构体的内存

2 因为需要k+1个数据的存贮空间 所以我们要开辟k+1个内存的大小

3 开始的头尾指针都设置为0

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

第三步 我们先判断队列是否空或满

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;

判断满的情况我们就可以用公式啦

我们说有以上代码可以来判断

第四步 重新回到插入数据

这里主要分两种情况讨论

像这种情况 直接插入 rear+1就可以

但是如果是这样子呢?

像这个时候tail就要走到最前面了?

那么我们怎么来表示呢?

我们说

可以使用 tail=(tail+1)%(k+1)表示 想想看 是不是这样子

当tail等于4向前是不是就变成0了

所以我们开始敲代码

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    return false;
    obj->a[obj->rear++] = value;
    obj->rear%=(obj->k+1);
    return true;
}

这样子就完成了

第五步 删除数据

这个的判断和前面一样

参考前面的代码就能够写出来了

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    ++obj->front;
     obj->front%=(obj->k+1);
     return true;
}

第六步 返回头数据

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
 
    return obj->a[obj->front];
}

这个很简单 返回头部的数据就可以

数组越界问题跟前面的处理结果相似

第七步 返回尾数据

这里要考虑一个特殊情况

就是当尾指针在数组的0位置的时候

这个时候我们单拎出来分类讨论就可以

如果是0的话 我们返回最后面的数据就可以

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
 
    if(obj->rear==0)
    {
        return obj->a[obj->k];
    }else
    {
        return obj->a[obj->rear-1];
    }
}

第八步 释放

这个也很简单,先释放结构里面的再释放结构体

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

源码

1. ttypedef struct {
    int*a;
    int front;
    int rear;
    int k;
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    return false;
    obj->a[obj->rear++] = value;
    obj->rear%=(obj->k+1);
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    ++obj->front;
     obj->front%=(obj->k+1);
     return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
 
    return obj->a[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
 
    if(obj->rear==0)
    {
        return obj->a[obj->k];
    }else
    {
        return obj->a[obj->rear-1];
    }
}
 
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}


以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
9月前
|
存储 人工智能 运维
内附源码|头部基模企业信赖之选——DMS+Lindorm智能搜索方案
本文为数据库「拥抱Data+AI」系列连载第6篇,针对企业构建智能搜索服务的痛点,介绍如何利用阿里云Data+AI解决方案构建一站式AI搜索服务,深入分析了DMS+Lindorm的智能搜索解决方案。
|
11月前
|
Rust Ubuntu Linux
|
9月前
|
前端开发 Java 数据库
玩转springboot之springboot注册servlet
在Spring Boot中注册Servlet非常灵活,可以通过 `@WebServlet`注解快速注册,也可以通过 `ServletRegistrationBean`进行细粒度控制。通过这两种方式,可以满足各种场景下的需求,确保应用能够高效处理HTTP请求。
672 14
|
6月前
|
JSON JavaScript 前端开发
shpfile转GeoJSON;控制shp转GeoJSON的精度;如何获取GeoJSON;GeoJSON是什么有什么用;GeoJSON结构详解(带数据示例)
在使用Openlayers、leaflet、mapbox等地图控件的时候,GeoJSON几乎是不可避免打交道的数据类型,如果您想要从事gis行业相关的开发工作,本篇文章应该能为您带来一些帮助。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
安全 关系型数据库 MySQL
MySQL装机全攻略:从下载到安全配置的详细指南
出于安全考虑,建议禁止root用户通过远程连接登录MySQL数据库。可以通过修改用户权限或配置防火墙规则来实现。 创建新用户并授权: 根据实际需求,创建具有不同权限的用户账户,并为他们分配必要的数据库和表权限。这样既可以满足业务需求,又可以降低安全风险。
|
API 数据库 Python
Python web框架fastapi数据库操作ORM(二)增删改查逻辑实现方法
Python web框架fastapi数据库操作ORM(二)增删改查逻辑实现方法
629 1
|
开发工具 git Docker
隐私计算实训营 第四讲 快速上手隐语SecretFlow的安装和部署
在两台虚拟机(10.10.101.58:alice, 10.10.104.124:bob)上部署Secretflow,使用docker和`secretflow/secretflow-lite-anolis81.4.0b0`镜像。每台机器上运行docker容器,并通过`docker exec`启动Ray服务(Bob节点在8085端口)。接着,导入secretflow库,配置集群信息并初始化。Secretnode部署通过源码完成,克隆secretnote仓库,进入sim目录,运行`docker-compose up`。展示部署成功后的界面截图。
272 0
|
存储 JSON 数据可视化
API入门项目项目收集GitHub上热门项目的信息
API是网站的一部分,在学术领域中常用于获取数据信息。如果我们想要获取某个网站上的一些信息,可以使用API请求数据,然后对这些数据进行处理和可视化,以便更好地理解和分析数据。
257 0
|
监控 数据可视化 数据安全/隐私保护
魔笔低代码开发平台在业务流程自动化应用搭建方面的体验评测
魔笔低代码开发平台在业务流程自动化应用搭建方面的体验评测
391 1