数据结构:力扣OJ题(每日一练)

题一:有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
  4. 示例 2:

    输入:s = "()[]{}"
    输出:true

思路一:

        第一步:写出数组栈的结构体,然后分别写出栈的初始化,入栈,出栈,获取栈顶元素,销毁栈,检验栈是否为空的函数;

        第二步:创建一个结构体变量,初始化,while(*s)决定是否继续循环,用switch找到对应的前置符号将他们入栈,如果是后置符号,则先判断ps中是否为空,然后再判断是否有对应的前置符合,没有:直接结束,:继续循环;

        第三步:创建相应的bool型变量记录SLEmpty()函数的返回值,销毁创建空间。

注意:OJ题不会判断代码开辟动态内存空间,所以在OJ题,不销毁开辟的动态内存也正确。

//约定类型方便更改类型
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}SL;
//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//入栈
void SLPush(SL* ps, STDataType x)
{assert(ps);//栈顶=容量说明需要扩容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->a[ps->top] = x;//后缀++方便下一次入栈和打印栈顶ps->top++;
}//出栈
void SLPop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);//--ps->top;
}//获得栈顶元素
STDataType SLTTop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);int n = (ps->top) - 1;return ps->a[n];
}//获取栈中有效元素个数
int SLSize(SL* ps)
{assert(ps);return ps->top;
}//销毁栈
void SLDestroy(SL* ps)
{assert(ps);//开辟数组优势:一次全部释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool SLEmpty(SL* ps)
{assert(ps);//为“0”说明为NULLif (ps->top == 0){return true;}return false;
}//思路一:使用switch
bool isValid(char * s)
{SL ps;char val;//初始化SLInit(&ps);while (*s){switch (*s){case '(':case '[':case '{'://入栈SLPush(&ps, *s);break;case ')':case '}':case ']'://判断栈是否为空if (SLEmpty(&ps)){//销毁开辟的动态内存SLDestroy(&ps);return false;}//栈顶值val = SLTTop(&ps);//出栈SLPop(&ps);if (*s == ')' && val != '(' ||*s == ']' && val != '[' ||*s == '}' && val != '{'){SLDestroy(&ps);return false;}break;}s++;}bool ret = SLEmpty(&ps);SLDestroy(&ps);return ret;
}

改进简化:

        原理同上,要实现的内容也同上,不过简化了switch()语句造成的多次调用,以及步骤上的增加,改用if----else语句后,代码更加的简洁清晰不需要考虑每种后置符号的操作,if一次性全部解决了。总体上减少了三分之一的代码量

//约定类型方便更改类型
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}SL;
//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//入栈
void SLPush(SL* ps, STDataType x)
{assert(ps);//栈顶=容量说明需要扩容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->a[ps->top] = x;//后缀++方便下一次入栈和打印栈顶ps->top++;
}//出栈
void SLPop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);//--ps->top;
}//获得栈顶元素
STDataType SLTTop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);int n = (ps->top) - 1;return ps->a[n];
}//销毁栈
void SLDestroy(SL* ps)
{assert(ps);//开辟数组优势:一次全部释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool SLEmpty(SL* ps)
{assert(ps);//为“0”说明为NULLif (ps->top == 0){return true;}return false;
}//改进简化内容if——else
bool isValid(char * s)
{SL ps;char val;//初始化SLInit(&ps);while (*s){if(*s == '(' || *s == '{' || *s == '['){//入栈SLPush(&ps, *s);}else{//判断栈是否为空if (SLEmpty(&ps)){//销毁开辟的动态内存SLDestroy(&ps);return false;}//栈顶值val = SLTTop(&ps);//出栈SLPop(&ps);if (*s == ')' && val != '(' ||*s == ']' && val != '[' ||*s == '}' && val != '{'){SLDestroy(&ps);return false;}}s++;}bool ret = SLEmpty(&ps);SLDestroy(&ps);return ret;
}

本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/89802.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot复习:(31)Controller中返回的对象是如何转换成json字符串给调用者的?

首先,SpringBoot自动装配了HttpMessageConvertersAutoConfiguration这个自动配置类 而这个自动配置类又通过Import注解导入了JacksonHttpMessageConvertersConfiguration类, 在这个类中配置了一个类型为MappingJackson2HttpMessageConverter类型的bean…

技术广度必备——高并发设计之分布式锁的实现方式

文章目录 问题背景前言实现基于MySQL实现唯一索引乐观锁悲观锁 基于Redis基于Zookeeper原理使用Curator框架实现ZK分布式锁缺点 问题背景 研究有哪几种方案可以实现分布式锁,技术选型的场景下能用到。 前言 本文参考过的文章有分布式锁的几种实现方式方式大致分为3种…

IDEA 设置字体大小无效

设置字体大小,一般都是从file>settings>editor>font>Size里设置,一般都有效。 但是,如果是更换了主体,则需要从主体颜色菜单那里这是,你看这个页面,上面黄色三角也提示你了,要去颜色…

风丘科技将亮相 EVM ASIA 2023

风丘科技将首次亮相 EVM ASIA 2023 WINDHILL will debut EVM ASIA 2023 ——可持续移动的未来 —The Future of SUSTAINABLE Mobility EVM ASIA 2023是亚太地区电气化的国际性展会,专注于新能源汽车、充电技术及汽车零件制造等。展会致力于促进包括充电站、交通…

【dnf5文档】新一代RedHat自动化包管理器

前言 HI,CSDN的码友们,距离上一次我发文章已经过去了半年的时间,现在我又来介绍自己新发现和探究的开源技术了。计算机的发展总是飞速的,当我在写这篇文章的时候,Fedora rawhide已经进入了40版本、默认采用的自动化包管理器为dnf…

论文阅读——Adversarial Eigen Attack on Black-Box Models

Adversarial Eigen Attack on Black-Box Models 作者:Linjun Zhou, Linjun Zhou 攻击类别:黑盒(基于梯度信息),白盒模型的预训练模型可获得,但训练数据和微调预训练模型的数据不可得&#xff…

SpringBoot Thymeleaf模板引擎

Thymeleaf 模板引擎 前端交给我们的页面,是html页面。如果是我们以前开发,我们需要把他们转成jsp页面,jsp好处就是当我们查出一些数据转发到JSP页面以后,我们可以用jsp轻松实现数据的显示,及交互等。 jsp支持非常强大…

【Linux】高级IO

目录 IO的基本概念 钓鱼五人组 五种IO模型 高级IO重要概念 同步通信 VS 异步通信 阻塞 VS 非阻塞 其他高级IO 阻塞IO 非阻塞IO IO的基本概念 什么是IO? I/O(input/output)也就是输入和输出,在著名的冯诺依曼体系结构当中…

k8s常用资源管理 控制

目录 Pod(容器组):Pod是Kubernetes中最小的部署单元,可以包含一个或多个容器。Pod提供了一种逻辑上的封装,使得容器可以一起共享网络和存储资源 1、创建一个pod 2、pod管理 pod操作 目录 创建Pod会很慢 Pod&…

MySQL表的增删查改

目录 一,新增 二,查询 2.1 全列查询 2.2 指定列查询 2.3 查询字段为表达式 2.4 别名 - as 2.5 去重 - distinct 2.6 排序 - order by 2.7 条件查询 - where 2.8 分页查询 - limit 三,修改 - update 四,删除 - delete 一…

考公-判断推理-定义判断

第九节课 例题 例题 例题 例题 例题 例题 脚一滑,就是工伤,这难道不是操作不当吗 例题 不要较真,公务员,把没有全局观念的人排除在公务员队伍之外 例题 例题 下次看到不字,先给我画上 例题 例题 例题 例题…

管理类联考——逻辑——论证逻辑——汇总篇——因果推理

因果推理的逻辑方法(穆勒五法) 确定现象之间因果关系的方法有五种: 求同法、求异法、求同求异并用法、共变法、剩余法。这五种方法统称为穆勒五法。用穆勒五法确定的因果关系具有或然性。 PS:求同球童;求异球衣,求同…

图解结构体大小和位域例子

struct A {short a; char b; int c : 1; char d : 4; short e : 7; }; 备注:蓝色:表示占一个符号位空间红色:表示补齐其他颜色:实际最大值所占空间 (1)图解例1 st…

opencv实战项目 手势识别-手势音量控制(opencv)

本项目是使用了谷歌开源的框架mediapipe,里面有非常多的模型提供给我们使用,例如面部检测,身体检测,手部检测等。 手势识别系列文章 1.opencv实现手部追踪(定位手部关键点) 2.opencv实战项目 实现手势跟踪…

答疑:Arduino IDE配置其他开发板下载速度慢

基于案例:Linux环境Arduino IDE中配置ATOM S3 通常,网络问题较多,可以使用一些技巧。 https://m5stack.oss-cn-shenzhen.aliyuncs.com/resource/arduino/package_m5stack_index.json 没有配置,不支持M5Stack(ESP32&…

【MongoDB基础】

目录 一、概述 1.概念 2.相关 2.1 实例 2.2 库 2.3 集合 2.4 文档 2.5 主键 3.特性 4,应用场景 二、安装 1.RPM安装 2.启动数据库 三、目录结构 1.rpm -ql mongodb-org-server 2.rpm -ql mongodb-org-shell 3.rpm -ql mongodb-org-tools 四、默…

【MySQL--->数据库基础】

文章目录 [TOC](文章目录) 一、基本概念二、实际应用中的数据库三、mysql的架构四、mysql语句分类五、存储引擎查看 一、基本概念 mysql本质是一个CS模式的网络服务,mysql是客户端,mysqld是服务端,提供高效的数据存取方案.数据库系统简单来说是一个数据集合加上管理这个数据集…

数据库数据恢复-Oracle数据库数据恢复案例

数据库数据恢复环境: Oracle数据库ASM磁盘组有4块成员盘。 数据库故障&分析: Oracle数据库ASM磁盘组掉线 ,ASM实例无法挂载,用户联系我们要求恢复oracle数据库。 数据库数据恢复工程师拿到磁盘后,先将所有磁盘以只…

Kafka的下载安装以及使用

一、Kafka下载 下载地址:https://kafka.apache.org/downloads 二、Kafka安装 因为选择下载的是 .zip 文件,直接跳过安装,一步到位。 选择在任一磁盘创建空文件夹(不要使用中文路径),解压之后把文件夹内容…

Android:换肤框架Android-Skin-Support

gihub地址:https://github.com/ximsfei/Android-skin-support 样例: 默认: 更换后: 一、引入依赖: // -- 换肤依赖implementation skin.support:skin-support:4.0.5// skin-supportimplementation skin.support:ski…