当前位置: 首页 > news >正文

刷爆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);
*/

相关文章:

  • C++生成随机数游戏
  • 基于双向长短期神经网络BILSTM的线损率预测,基于gru的线损率预测
  • path环境变量的作用
  • 蓝桥杯 每日2题 day5
  • Android开发基础:对话框,Toast,Notification的使用 选项菜单,上下文菜单,弹出式菜单的使用
  • OJ系统JavaScript Node标准输入输出(https://pintia.cn/)
  • Redis 8种基本数据类型及常用命令和数据类型的应用场景
  • c语言游戏实战(9):球球大作战
  • C++面试 -操作系统-安全能力:死锁的危害、出现原因、解决方法
  • 速盾:cdn服务器怎么做
  • 【黑马程序员】2、TypeScript介绍_黑马程序员前端TypeScript教程,TypeScript零基础入门到实战全套教程
  • 云端技术驾驭DAY13——Pod污点、容忍策略、Pod优先级与抢占、容器安全
  • Colmap安装与实践
  • 【苹果iMessage相册推信息推】 重要用于安装背面必要安装的watchman
  • 艾德克斯IT6512D可编程直流电源中文介绍
  • 使用机器学习做DGA域名识别
  • Day06-尚品汇-排序操作上
  • Linux进程替换(exec系列)
  • 史上最全软件测试工程师常见的面试题总结(百度、oppo、中软国际、华为)
  • 艾美捷抗人IL-2单抗MT8G10即用型解决方案
  • 头歌-信息安全技术-实训04 数据库SQL注入漏洞
  • C# 中的多线程
  • 建立自己的kindle书库
  • JavaWeb笔记(五)后端(Thymeleaf)(Tomcat类加载机制)(编写图书管理系统)
  • 提升网站流量和排名的方法,SEO优化要这样做
  • kubernets集群升级
  • 使用HTML+CSS+JS模拟比赛晋级的动画功能
  • 【数据结构Java版】LinkedList与链表之单链表
  • python list转str类型,str转list类型
  • 基于java校园德育活动预约和评分管理系统的设计与实现-计算机毕业设计源码+LW文档
  • 在 ESP 开发板上开发 UI 不再复杂
  • 最适合新手的100个深度学习实战项目