o2o系统/seo外链购买
有效括号问题:
题目描述:
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路:
解决此类问题,传统的暴力遍历法已经不再适用了,暴力遍历无法保证括号的匹配顺序,仅能通过统计左右括号的数量进行比较判断,但即使是左右括号数量相等,也不一定是有效的,如:“( [ { ] ) }”,虽然左右括号数量相同,但是它们的顺序不对,不能相互匹配,所以也是无效的,因此,暴力遍历的方法是不行的。
此时我们应该从问题本身出发,思考一下括号匹配的本质是什么?
我们知道一个合法的括号包括两部分:左括号和右括号,括号匹配就是匹配左右括号,并且每次匹配时都是相邻最近的两个左右括号进行匹配。因此,我们可以创建一个数组用来储存左括号,依次遍历,每出现一次左括号就存进这个数组中,每次出现右括号时,将它与数组中最后一个左括号进行匹配,若匹配成功,则删除数组最后一个左括号,再从下一个开始遍历;若匹配不成功,则说明是非法括号字符串,直接退出程序……直至遍历完括号字符串或者中间出现不匹配的情况直接退出。若正常遍历完括号字符串,再看数组中是否为空,若为空,说明该括号字符串中所有左右括号都匹配成功,即该括号字符串合法,反之则是非法的。观察这个匹配规律,不难发现与栈“先入后出”的特点相符合,因此我们可以直接创建一个栈进行实现。
具体代码如下:
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* p = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);ps->a = p;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}bool isValid(char * s)
{ST ps;STInit(&ps);int i=0;for(i=0;i<strlen(s);i++){if(s[i]=='('||s[i]=='{'||s[i]=='[')//左括号入栈{STPush(&ps,s[i]);}else//右括号与栈顶元素进行匹配{if(STEmpty(&ps))//栈中为空,说明括号数量不匹配{return false;}else if((STTop(&ps)=='('&&s[i]!=')')||(STTop(&ps)=='['&&s[i]!=']')||(STTop(&ps)=='{'&&s[i]!='}'))//栈中不为空,但括号样式不匹配{return false;}else//匹配成功,栈顶元素出栈{STPop(&ps);}}}if(STEmpty(&ps))//全部遍历完之后,栈中为空,说明全部匹配成功{return true;}else//栈中不为空,说明数量不匹配{return false;}STDestroy(&ps);
}
运行结果:
用栈实现队列:
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。
首先要知道栈的特点是“先入后出”,因为此特点,把栈1中的数据移动到栈2中时,数据的顺序会倒过来,如下:
数据入栈顺序是1、2、3、4,此时再从栈2中执行出栈操作,数据出栈顺序也是1、2、3、4,可以满足队列“先入先出”的功能,因此我们不妨把一个栈专门同来进数据(push),另一个栈专门用来出数据(pop)。
每次进数据都压入push栈,出数据都从pop栈出,若pop栈为空,则把push栈的数据都压入pop栈后再出数据。
代码如下:
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;
typedef struct
{ST push;ST pop;
} MyQueue;//初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//销毁
void STDestroy(ST* ps)
{free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* p = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);ps->a = p;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->a);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
//创建我的队列
MyQueue* myQueueCreate()
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->push);STInit(&obj->pop);return obj;
}
//入队
void myQueuePush(MyQueue* obj, int x)
{STPush(&obj->push, x);
}
//出队
int myQueuePop(MyQueue* obj)
{if (STEmpty(&obj->pop)){while (!STEmpty(&obj->push)){STDataType x = STTop(&obj->push);STPop(&obj->push);STPush(&obj->pop, x);}}STDataType front = STTop(&obj->pop);STPop(&obj->pop);return front;
}
//取队头
int myQueuePeek(MyQueue* obj)
{if (STEmpty(&obj->pop)){while (!STEmpty(&obj->push)){STDataType x = STTop(&obj->push);STPop(&obj->push);STPush(&obj->pop, x);}}STDataType front = STTop(&obj->pop);return front;
}
//我的队列判空
bool myQueueEmpty(MyQueue* obj)
{return (STEmpty(&obj->push) && STEmpty(&obj->pop));
}
//销毁我的队列
void myQueueFree(MyQueue* obj)
{STDestroy(&obj->push);STDestroy(&obj->pop);free(obj);
}
运行结果:
用队列实现栈:
题目描述:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack
类:
void push(int x)
将元素 x 压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。
注意:
- 你只能使用队列的基本操作 —— 也就是
push to back
、peek/pop from front
、size
和is empty
这些操作。
首先要知道队列的特点是“先进先出”,因为此特点,将队列1中的数据移动到队列2中时,数据的顺序不会变,如下:
数据的从队列1进队顺序是1、2、3、4,如直接从队列2出队,则出队顺序也是1、2、3、4,无法满足栈的“先进后出”的特点。因此,想要通过队列实现栈,要始终保证至少一个队列为空(若两个队列都为空,则只能执行判空和压入数据的操作),这样在出数据时,把不为空队列(假设有n个数据)的前n-1个数据移动到空队列中,再出最后一个数据,这样不断在两个队列之间导数据,就能实现把后入的数据先出出去,而想要压入数据时,直接在非空的队列队尾直接插入即可,这样就能实现栈“先进后出”的特点。
代码如下:
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
typedef struct
{Que p1;Que p2;
} MyStack;
//判空 :空返回1,非空返回0
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}
//初始化
void QueueInit(Que* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* p = cur->next;free(cur);cur = p;}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//入队
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = newnode;pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//出队
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));//要有数据if (pq->head->next == NULL)//只有一个节点{free(pq->head);pq->head = NULL;pq->tail = NULL;}else{QNode* cur = pq->head->next;free(pq->head);pq->head = cur;}pq->size--;
}
//取队头
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
//取队尾
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
//有效数据
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
//创建我的栈
MyStack* myStackCreate()
{MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->p1);QueueInit(&obj->p2);return obj;
}
//入栈
void myStackPush(MyStack* obj, int x)
{if (!QueueEmpty(&obj->p1)){QueuePush(&obj->p1, x);}else{QueuePush(&obj->p2, x);}
}
//出栈
int myStackPop(MyStack* obj)
{QDataType top = 0;if (!QueueEmpty(&obj->p1)){while (QueueSize(&obj->p1) > 1){QDataType a = QueueFront(&obj->p1);QueuePop(&obj->p1);QueuePush(&obj->p2, a);}top = QueueFront(&obj->p1);QueuePop(&obj->p1);}else{while (QueueSize(&obj->p2) > 1){QDataType a = QueueFront(&obj->p2);QueuePop(&obj->p2);QueuePush(&obj->p1, a);}top = QueueFront(&obj->p2);QueuePop(&obj->p2);}return top;
}
//取栈顶
int myStackTop(MyStack* obj)
{if (!QueueEmpty(&obj->p1)){return QueueBack(&obj->p1);}else{return QueueBack(&obj->p2);}
}
//判空
bool myStackEmpty(MyStack* obj)
{return (QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2));
}
//销毁我的栈
void myStackFree(MyStack* obj)
{QueueDestroy(&obj->p1);QueueDestroy(&obj->p2);free(obj);
}
运行结果:
相关文章:

栈和队列OJ题
有效括号问题: 题目描述: 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。左括号必须以正确的…...

36k字从Attention讲解Transformer及其在Vision中的应用(pytorch版)
文章目录 0.卷积操作1.注意力1.1 注意力概述(Attention)1.1.1 Encoder-Decoder1.1.2 查询、键和值1.1.3 注意力汇聚: Nadaraya-Watson 核回归1.2 注意力评分函数1.2.1 加性注意力1.2.2 缩放点积注意力1.3 自注意力(Self-Attention)1.3.1 自注意力的定义和计算1.3.2 自注意…...

网站怎么选择适合的服务器
IDC数据中心大致分为T1、T2、T3、T4 T1:基本机房基础设施(可用性99.671%、年平均故障时间28.8小时) 1) T1 基本数据中心拥有非冗余容量组件,以及一个单一的非冗余分配路径来为关键环境提供服务。T1 基础设施包括:IT …...

http协议和HTTP编程流程
目录 1、http协议 (1)概念 (2)使用的端口 (3)长连接和短连接 (4)常见web服务器 2、https(443) 3、浏览器连接服务器编程 1、http协议 (超文…...

【NPM】包的指令
npm 安装的包可以根据其用途和作用进行分类,一般可以分为以下几种类型: 普通依赖(Regular Dependencies): 这些是你项目中的实际依赖项,用于构建、运行或扩展你的应用程序。这些依赖会被包含在你的应用程序…...

音频4A算法导论
+我V hezkz17进数字音频系统研究开发交流答疑群(课题组) 一 音频4A算法是? 音频4A算法是指自动增益控制(Automatic Gain Control, AGC)、自动噪声抑制(Automatic Noise Suppression, ANS)和自动回声消除(Automatic Echo Cancellation, AEC),主动降噪ANC(Active Noi…...

SecureBridge安全文件下载的组件Crack
SecureBridge安全文件下载的组件Crack SecureBridge包括SSH、SSL和SFTP客户端和服务器组件。它使用SSH或SSL安全传输层协议和加密消息语法来保护任何TCP流量,这些协议为客户端和服务器提供身份验证、强数据加密和数据完整性验证。SecureBridge组件可以与数据访问组件…...

进程同步
目录 临界区(Critical Section): 互斥量(Mutex): 信号量(Semaphore): 事件(Event): 进程同步的四种方法 临界区(Critical Section): 通过对多线程的串行…...

Prometheus+Grafana+AlertManager监控Linux主机状态
文章目录 PrometheusGrafanaAlertManager监控平台搭建开始监控Grafana连接Prometheus数据源导入Grafana模板监控Linux主机状态 同系列文章 PrometheusGrafanaAlertManager监控平台搭建 Docker搭建并配置Prometheus Docker拉取并配置Grafana Docker安装并配置Node-Exporter …...

UI设计第一步,在MasterGo上开展一个新项目
我们都知道,一个完整的项目,要经历创建团队、搭建组件库、应用规范以及管理设计资产,那么今天小编就在MasterGo中带你从0到1开展一个全新的项目。 你一定遇到过这种情况,同团队的设计师,由于使用不同版本或不同软件&a…...

【校招VIP】TCP/IP模型之常用协议和端口
考点介绍: 大厂测试校招面试里经常会出现TCP/IP模型的考察,TCP/IP协议是网络基础知识,是互联网的基石,不管你是做开发、运维还是信息安全的,TCP/IP 协议都是你绕不过去的一环,程序员需要像学会看书写字一样…...

Spring统一功能处理
1. AOP存在的问题 获取参数复杂AOP的规则相对简单 2. 拦截器 2.1. 应用(以登录为例) 2.1.1. 自定义拦截器 新建interceptor文件夹 import org.springframework.web.servlet.HandlerInterceptor;import javax.servlet.http.HttpServletRequest; import javax.servlet.http…...

搭建CFimagehost私人图床,实现公网远程访问的详细指南
文章目录 1.前言2. CFImagehost网站搭建2.1 CFImagehost下载和安装2.2 CFImagehost网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar临时数据隧道3.2 Cpolar稳定隧道(云端设置)3.3.Cpolar稳定隧道(本地设置) 4.公网访问测…...

Python的logging.config模块
要使用Python的logging.config模块记录一个月的日志数据,你可以按照以下步骤进行操作: 首先,导入必要的模块: import logging import logging.config import datetime创建一个配置文件,例如logging.ini,用…...

【2023】LeetCode HOT 100——滑动窗口子串
目录 1. 无重复字符的最长子串1.1 C++实现1.2 Python实现1.3 时空分析2. 找到字符串中所有字母异位词2.1 C++实现2.2 Python实现2.3 时空分析3. 和为 K 的子数组3.1 C++实现3.2 Python实现3.3 时空分析4. 滑动窗口最大值4.1 C++实现4.2 Python实现4.3 时空分析5. 最小覆盖子串5…...

【云卓笔记】mavlink java文件
根据飞控提供的xml文件来生成的 生成的就是这样的java文件 准备工作: Mavlink协议生成 参考 1.安装mavlink : 使用MAVLink工具的要求是 Python 3.3 (recommended) or Python 2.7 Python future模块 (可选) PythonTklnter模块(如果需要使用图形用户界面)。 环境变量PYTHO…...

电机控制软件框架
应用层包括main 主函数模块,ISR 中断处理函数模块、时基Systick 模块和BLDC 应用接口模块;算法层包括BLDC Algorithm 模块和PID control 模块;驱动层(Driver layer):包括GD32Fxx_Standard_peripheral libra…...

SCCB与IIC的异同及FPGA实现的注意事项
文章目录 前言一、信号线二、SCCB数据传输格式三、SCCB写(与IIC完全一致)四、SCCB读五、SCCB和IIC的区别 前言 IIC接口有比较广泛的应用,而SCCB(Serial Camera Control Bus,串行摄像头控制总线)是由OV&…...

【开发】安防监控视频智能分析平台新功能:安全帽/反光衣/安全带AI识别详解
人工智能技术已经越来越多地融入到视频监控领域中,近期我们也发布了基于AI智能视频云存储/安防监控视频AI智能分析平台的众多新功能,该平台内置多种AI算法,可对实时视频中的人脸、人体、物体等进行检测、跟踪与抓拍,支持口罩佩戴检…...

数据结构 - 线性表的顺序存储
一、顺序存储定义: 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中。简言之,逻辑上相邻,物理上也相邻顺序表中,任一元素可以随机存取(优点) 二、顺序表中元素存储位置的计算 三、顺序表在算法中的实…...

栈和队列在数据结构中的应用
文章目录 理解栈和队列的概念及其特点栈的应用和操作队列的应用和操作结论 🎉欢迎来到数据结构学习专栏~探索栈和队列在数据结构中的应用 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页:IT陈寒的博客🎈该系列文章专栏:…...

AndroidStudio升级后总是Read Time Out的解决办法
AndroidStudio升级后在gradle的时候总是Time out,遇到过多次,总结一下解决办法 1、gradle下载超时 在工程目录../gradle/wrapper/gradle-wrapper.properties中找到gradle版本的下载链接,如下图: 将其复制到迅雷里下载࿰…...

升级Go 版本到 1.19及以上,Goland: file.Close() 报错: Unresolved reference ‘Close‘
错误截图 解决方法 File -> Settings -> Go -> Build Tags & Vendoring -> Custom tags -> 添加值 “unix” 原因 Go 1.19 引入了unix构建标签。因此,需要添加unix到自定义标签。 参考 https://blog.csdn.net/weixin_43940592/article/det…...

进程,线程,协程
1、进程 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间,不同进程通过进程间通信来通信。由于进程比较重量,占据独立的内存,所以上下…...

车联网技术介绍
上图是目前车联网架构图,基于“云-管-端”的车联网系统架构以支持车联网应用的实现, “云”是指 V2X 基础平台、高基于精度定位平台等基础能力,可实现车辆动态厘米级定位,这将满足现阶段以及未来车联网应用场景的定位精度需求。 “…...

并发-线程池
阻塞队列 笔记地址 点击进入 队列:先进先出 限定在一端进行插入,一端进行删除 出队为队头,入队为队尾 阻塞队列 BlockingQueue Queue接口继承Collection接口添加元素:add(),队列满了对抛出异常offer(),队…...

openCV实战-系列教程5:边缘检测(Canny边缘检测/高斯滤波器/Sobel算子/非极大值抑制/线性插值法/梯度方向/双阈值检测 )、原理解析、源码解读
打印一个图片可以做出一个函数: def cv_show(img,name):cv2.imshow(name,img)cv2.waitKey()cv2.destroyAllWindows() 1、Canny边缘检测流程 Canny是一个科学家在1986年写了一篇论文,所以用自己的名字来命名这个检测算法,Canny边缘检测算法…...

【数据仓库】Linux、CentOS源码安装Superset
Linux、CentOS源码安装Superset步骤,遇到的各种问题。 报错问题: Linux下pip版本问题 You are using pip version 8.1.2, however version 22.2.2 is available. 解决办法: 安装python3的pip yum install python3-pip再升级 pip3 install…...

高并发网站的负载均衡设计
大型高并发网站的负载均衡设计通常包含以下方面: 1. 硬件负载均衡器 在入口使用专业的硬件F5等负载均衡器,实现流量分发,并承担第一层保护。 2. DNS轮询/一致性哈希 结合DNS,使用轮询或一致性哈希方式将请求分散到后端不同的真实服务器。 3. CDN负载均衡 针对静态资源,使用C…...

Unity C# 之 Task、async和 await 、Thread 基础使用的Task的简单整理
Unity C# 之 Task、async和 await 、Thread 基础使用的Task的简单整理 目录 Unity C# 之 Task、async和 await 、Thread 基础使用的Task的简单整理 一、Task、async和 await 、Thread 基础概念 1、线程,多线程 2、Task 3、async (await )…...