刷爆leetcode第五期

简介: 刷爆leetcode第五期

题目一 有效的括号

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。


我们假设字符串有这些符号组成

当我们遍历到左括号的时候 我们就对其进行压栈操作

c语言代码表示如下


typedef int STDateType;
 
typedef struct Stack
{
    int* a;//存储数据的大小
    int Top;//栈顶
    int capacity;//容量大小
}ST;
void STInit(ST*ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDateType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDateType STTop(ST* ps);
void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(sizeof(STDateType)*4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps->Top = 0;//top是栈顶元素的下一个位置
  ps->capacity = 4;
}
//销毁
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->capacity = 0;
  ps->Top = 0;
  ps->a = NULL;
}
//压栈
void STPush(ST* ps, STDateType x)
{
  assert(ps);
  if (ps->Top == ps->capacity)
  {
    STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->Top] = x;
  ps->Top++;
}
//出栈
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
   ps->Top--;
}
//个数
int STSize(ST* ps)
{
  assert(ps);
 
  return ps->Top;
}
//判断空
bool STEmpty(ST* ps)
{
  assert(ps);
 
  return ps->Top==0;
}
//栈顶的位置
STDateType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
  return ps->a[ps->Top - 1];
}
 
 
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            STPush(&st,*s);
        }else
        {
            char top = STTop(&st);
            STPop(&st);
            if(*s==')'&&top!='('
            ||*s==']'&&top!='['
            ||*s=='}'&&top!='{')
            {
                return false;
            }
        }
        ++s;
    }
    STDestroy(&st);
    return true;
}


我们提交试试看


我们可以发现 这里好像没有匹配成功过 直接遍历完了也返回true了

那么这里我们可以判断下是否为空 如果为空我们返回假就好了

我们再测试下看看



又出错了

我们发现 这里栈上还没有数据 直接就开始出栈了 当然就报错了

那么我们再打个补丁

//如果遇到右边括号且栈为空,直接返回false   
if(STEmpty(&st))
            {
                return false;
            }


之后我们再试试看


虽然成功通过所有测试用例

但是我们还要考虑一个内存泄露的问题,还是要加上销毁

完整的代码如下:

typedef int STDateType;
 
typedef struct Stack
{
    int* a;//存储数据的大小
    int Top;//栈顶
    int capacity;//容量大小
}ST;
void STInit(ST*ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDateType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDateType STTop(ST* ps);
void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(sizeof(STDateType)*4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps->Top = 0;//top是栈顶元素的下一个位置
  ps->capacity = 4;
}
//销毁
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->capacity = 0;
  ps->Top = 0;
  ps->a = NULL;
}
//压栈
void STPush(ST* ps, STDateType x)
{
  assert(ps);
  if (ps->Top == ps->capacity)
  {
    STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->Top] = x;
  ps->Top++;
}
//出栈
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
   ps->Top--;
}
//个数
int STSize(ST* ps)
{
  assert(ps);
 
  return ps->Top;
}
//判断空
bool STEmpty(ST* ps)
{
  assert(ps);
 
  return ps->Top==0;
}
//栈顶的位置
STDateType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
 
  return ps->a[ps->Top - 1];
}
 
 
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            STPush(&st,*s);
        }else
        {
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);
            STPop(&st);
            if(*s==')'&&top!='('
            ||*s==']'&&top!='['
            ||*s=='}'&&top!='{')
            {
                STDestroy(&st);
                return false;
            }
        }
        ++s;
    }
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}


也是完美通过



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

目录
相关文章
|
开发工具 git C++
『实用教程』使用Visual Studio自带的Git管理回滚代码版本
使用Visual Studio自带的Git管理回滚代码版本
2029 0
『实用教程』使用Visual Studio自带的Git管理回滚代码版本
|
机器学习/深度学习 自然语言处理 算法
利用机器学习算法进行自动化测试
利用机器学习算法进行自动化测试
|
人工智能
使用Kimi AI整理会议记录,同事都来围观
使用Kimi AI整理会议记录,同事都来围观
422 0
遍历Map的四种方法之map.entry详解
遍历Map的四种方法之map.entry详解
|
Java 持续交付 Maven
云效产品使用常见问题之流水线的容器读取本地的挂载文件失败如何解决
云效作为一款全面覆盖研发全生命周期管理的云端效能平台,致力于帮助企业实现高效协同、敏捷研发和持续交付。本合集收集整理了用户在使用云效过程中遇到的常见问题,问题涉及项目创建与管理、需求规划与迭代、代码托管与版本控制、自动化测试、持续集成与发布等方面。
|
存储 安全 网络安全
云计算与网络安全:技术融合与挑战
【6月更文挑战第10天】本文探讨了云计算与网络安全的紧密联系,分析了云服务、网络安全和信息安全等技术领域的发展及其面临的挑战。通过阐述云计算的基本原理、网络安全的重要性以及信息安全的关键要素,强调了在云计算环境下保障网络安全和信息安全的必要性。
|
负载均衡 网络协议 安全
华为19级大佬10年心血终成百页负载均衡高并发网关设计实战文档
负载均衡(LoadBalance)的字面意思是将工作负载分担到多个工作单元上进行执行,它建立在现有网络结构之上,是构建分布式服务、大型网络应用的关键组件。 近十几年来,负载均衡技术层出不穷,令人眼花缭乱。如果问身边的技术人员什么是负载均衡,我们可能会得到许多不同的答案。
|
机器学习/深度学习 自然语言处理 文字识别
初步了解RNN, Seq2Seq, Attention注意力机制
初步了解RNN, Seq2Seq, Attention注意力机制
282 0
初步了解RNN, Seq2Seq, Attention注意力机制
|
JavaScript
Vue编写表单常用操作(过滤和排序)
Vue编写表单常用操作(过滤和排序)