好题分享(2023.11.12——2023.11.18)

目录

前情回顾:

 前言:

题目一:《有效括号》

思路:

总结:

题目二:《用队列实现栈》

思路:

总结:

题目三:《用栈实现队列》 

思路:

总结 :

总结:


 

 

前情回顾:

我们在上一篇好题分析中,分析了以下几题:

《反转链表》《相交链表》《环形链表(一)》《环形链表(二)》《随机链表的复制》《合并两个有序链表》

《链表中倒数第K个节点》《链表分割》《链表的回文结构》

上一篇的好题分析的blog:

好题分享(2023.11.5——2023.11.11)-CSDN博客

 前言:

本次《好题分享》当中,我们主要熟悉我们刚刚所学的《栈和队列》这一部分内容。

通过三道Leecode题目使我们对于《栈和队列》能有一个更好的认识。

以下是我们需要解决的三道题目:

《有效括号》《用队列实现栈》《用栈实现队列》

 这三道题的代码量都会非常的长,那是由于我们现在处于初学阶段,没有办法使用一些高效的方法来解决这些题目,但是不用怕,因为我们不仅仅实现过《栈》也实现过《队列》。

对于《栈和队列》的讲解可以去访问我的上一篇blog

《栈和队列》的模拟实现(顺序栈) (链队列)-CSDN博客

里面有需要实现本次题目的代码,打开我的Gitee即可获取。

在做题目之前我们首先需要将我们实现好的《栈》或者《队列》的代码粘贴到题目最前面的位置。

那么现在我们就来动手实践以及讲解 


题目一:《有效括号》

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

 

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst)
{
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = -1;
}

void STDestory(ST* pst)
{
	assert(pst);
	free(pst);
	pst = NULL;
}

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top || pst->top == -1)
	{
		int newCapacity = (pst->capacity == 0) ? 4 : 2 * (pst->capacity);
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(ST)*newCapacity);
		if (tmp == NULL)
		{
			perror("STPush -> realloc");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->top++;
	pst->a[pst->top] = x;
}

void STPop(ST* pst)
{
	assert(pst);
	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	return pst->a[pst->top];
}

bool STEmpty(ST* pst)
{
	assert(pst);
	if (pst->top == -1)
	{
		return true;
	}
	return false;
}

int STSize(ST* pst)
{
	assert(pst);
	return (pst->top) + 1;
}

void STPrint(ST* pst)
{
	assert(pst);
	while (pst->top != -1)
	{
		printf("%d\n", STTop(pst));
		STPop(pst);
	}
}





bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
        if(*s == '[' || *s == '(' || *s == '{')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
            {
                return false;
            }
            else
            {
                char top = STTop(&st);
                STPop(&st);
             if((top == '(' && *s != ')')
                 ||(top == '{' && *s != '}')
                 || (top == '[' && *s != ']'))
             {
                return false;
             }
            }
        }
        s++;
            
    }

    if(!STEmpty(&st))
    {
        return false;
    }

    return true;

}

思路:

 

本题的思路就是利用《栈》的性质——先进后出

因为是匹配括号,我们不妨假设其本质就是一个《栈》。

我们先去遍历字符串,如果访问到左括号,例如

"{"                   "("                "["

就直接入栈。

而如果访问到右括号,我们就与栈顶的括号匹配,如果左右括号匹配成功就删除栈顶的括号,字符串继续遍历,直到遍历完成。

如图:

 

 

 栈顶的括号与s指向的括号相匹配

 

此时相匹配,则删除栈顶元素:

 

如此继续遍历。

 

此时s指向'\0'代表遍历结束,而如果《栈》为空,就代表着字符串为有效括号,就可以return true

总结:

1.创建《栈》

2.遍历字符串,左括号入《栈》

3.遍历到右括号,则于《栈》顶的左括号相匹配

4.当字符串遍历完后,《栈》为空则return true;

但是这里存在一个细节,需要去注意

例如,如果我们在遍历字符串时遍历到有括号时,可是《栈》中没有栈顶元素与之匹配,则直接返回false。

 

题目二:《用队列实现栈》

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

 

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int sz;
}Queue;




void QueueInit(Queue* pq)
{
	pq->sz = 0;
	pq->phead = pq->ptail = NULL;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* cur = pq->phead->next;

	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	free(pq->phead);
	pq->phead = pq->ptail = cur = NULL;

}

void QueuePop(Queue* pq)
{
	assert(pq);
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
	}
	pq->sz--;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush -> malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->sz++;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->phead == NULL)
	{
		return true;
	}
	return false;
}

int QueueSize(Queue* pq)
{
	return pq->sz;
}

void QueuePrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}


typedef struct {
	Queue q1;
	Queue q2;
} MyStack;

MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&pst->q1);
	QueueInit(&pst->q2);
	return pst;
}

void myStackPush(MyStack* obj, int x) {
	if (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		if (!QueueEmpty(&obj->q1))
		{
			QueuePush(&obj->q1, x);
		}
		else
		{
			QueuePush(&obj->q2, x);
		}
	}
}

int myStackPop(MyStack* obj) {

	if (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
	{
		return 0;
	}
	else
	{
		if (!QueueEmpty(&obj->q1))
		{
			int n = QueueSize(&obj->q1) - 1;
			while (n)
			{
				int top = QueueFront(&obj->q1);
				QueuePush(&obj->q2, top);
				QueuePop(&obj->q1);
				n--;
			}
			int top = QueueFront(&obj->q1);
			QueuePop(&obj->q1);
			return top;
		}
		else
		{
			int n = QueueSize(&obj->q2) - 1;
			while (n)
			{
				int top = QueueFront(&obj->q2);
				QueuePush(&obj->q1, top);
				QueuePop(&obj->q2);
				n--;
			}
			int top = QueueFront(&obj->q2);
			QueuePop(&obj->q2);
			return top;
		}
	}
}

int myStackTop(MyStack* obj) {
	if (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
	{
		return 0;
	}
	else
	{
		if (!QueueEmpty(&obj->q1))
		{
			return QueueBack(&obj->q1);
		}
		else
		{
			return QueueBack(&obj->q2);
		}
	}
}

bool myStackEmpty(MyStack* obj) {
	if (!QueueEmpty(&obj->q1) || !QueueEmpty(&obj->q2))
	{
		return false;
	}
	return true;

}

void myStackFree(MyStack* obj) {
	if (!QueueEmpty(&obj->q1) && !QueueEmpty(&obj->q2))
	{
		if (!QueueEmpty(&obj->q1))
		{
			QueueDestroy(&obj->q1);
		}
		else
		{
			QueueDestroy(&obj->q2);
		}
	}
}


/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

该题目的代码量会非常长,刚开始做题时是会产生恐惧,但是不用害怕,因只要我们了解了其中代码的秘密,我们就能迎刃而解了。

思路:

 由题意,就是让我们创建两个栈,然后通过两个栈之间的操作,完成一个队列的基本实现。

我们想要插入12345,那么对于栈来说

1就是《栈》底元素,5就是《栈》顶元素。

出栈也只能出5

但是对于队列而言呢?

队头是1,队尾是5

出队列也只能出1.

所以对于“出栈”就可以利用两个队列:

先让12345插入到队列1,即q1

再让q1中的各个元素一个个的进到队列q2中

 

 

如此不断循环

直到q1只剩一个元素,那个元素就是对应的“栈顶”。

我们将这个元素删除即可:

 

 

 最后则返回top:

以上就是“出栈”的函数实现,那么对于入栈来说,就是哪个队列不为空就插入到哪个队列中。

具体的代码还是好实现的。后续的函数我也不做过多的赘述。

总结:

对于这道题我们讲解关于“出栈”函数的实现就可以解决大部分问题。

但是这道题的自定义数据类型可能会有人绕不清楚,接下来我画一张图大家就可以理解了:

 

我们在上一篇blog也讲过,创建一个结构体用来保存头指针和尾指针对象,可以大大提高传输效率,也可以使人理解透彻!

 

题目三:《用栈实现队列》 

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = -1;
}

void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = -1;
	pst->capacity = 0;
}

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	int newcapacity = (pst->capacity == 0) ? 4 : 2 * (pst->capacity);
	STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
	if (tmp == NULL)
	{
		perror("STPush -> realloc");
		exit(-1);
	}
	pst->a = tmp;
	pst->capacity = newcapacity;
	pst->top++;
	pst->a[pst->top] = x;

}

void STPop(ST* pst)
{
	assert(pst);
	if (pst->top != -1)
	{
		pst->top--;
	}
}

STDataType STTop(ST* pst)
{
	assert(pst);
	if (pst->top != -1)
	{
		return pst->a[pst->top];
	}
	return -1;
}

bool STEmpty(ST* pst)
{
	assert(pst);
	if (pst->top == -1)
	{
		return true;
	}
	return false;
}

int STSize(ST* pst)
{
	assert(pst);
	return pst->top + 1;
}

void STPrint(ST* pst)
{
	assert(pst);
	for (int i = 0; i <= pst->top; i++)
	{
		printf("%d  ", pst->a[i]);
	}
}


typedef struct {
    ST SPush;
    ST SPop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->SPush);
    STInit(&obj->SPop);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->SPush,x);
}

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);
    STPop(&obj->SPop);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->SPop))
    {
        while(!STEmpty(&obj->SPush))
        {
            STPush(&obj->SPop,STTop(&obj->SPush));
            STPop(&obj->SPush);
        }
    }
    return STTop(&obj->SPop);
}

bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&obj->SPush) && STEmpty(&obj->SPop))
    {
        return true;
    }
    return false;
}

void myQueueFree(MyQueue* obj) {
    STDestory(&obj->SPop);
    STDestory(&obj->SPush);

    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

本题的代码与上题一样,先将实现栈的函数粘贴到该题目中。

思路:

 我们还是先来讲讲“出队列”这个思路。

“出队列”秉持一个原则,就是先进先出

而出缺是后进先出,所以我们不得不继续用到两个栈。

但是这里我们不同于上一道题,我们必须定义两个栈

即一个栈只能入数据,一个栈是用来出数据的。

 比如我还是将12345入栈。

如果是队列的话,只能实现先进先出,即将1删除。

所以我们可以借鉴上题那样,先将SPush里面的所以元素移到SPop中 :

这样一来,我们只需要删除SPop的栈顶元素即可。

如果我们想要继续输入数据,也不需要将SPop里面的数据再倒入SPush中,只需要再SPush里面继续添加新数据。

反正,只要SPop这个栈里有数据,就先删除栈顶的,而对于添加数据,只需要向SPush里面添加即可。

 

当删完SPop后如果还想删数据,则继续将SPush里面的数据倒入SPop即可。

 

总结 :

当然还是会有人对数据类型不是很理解,我还是画个图给大家观看:

 

 

总结:

 本文主要以巩固《栈和队列》为主,从此以后的好题分析,我们主要给大家讲解最关键思路,以及部分重难点函数的实现。

同学们下来可以自己动手尝试编写编写。

记住

“坐而言不如起而行!”

Aciton speak louder than words!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CodeWhisperer 一款好玩的 AI 插件

忙里抽闲&#xff0c;今天试了试 CodeWhisperer 这款插件&#xff0c;我是在 IDEA 中做的测试&#xff0c;下面是我的一些使用感想&#xff1a; 安装 CodeWhisperer 插件&#xff1a;在 IntelliJ IDEA 中&#xff0c;可以通过插件管理器安装 CodeWhisperer 插件&#xff0c;然…

ChatGPT 也并非万能,品牌如何搭上 AIGC「快班车」

内容即产品的时代&#xff0c;所见即所得&#xff0c;所得甚至超越所见。 无论是在公域的电商平台、社交媒体&#xff0c;还是品牌私域的官网、社群、小程序&#xff0c;品牌如果想与用户发生连接&#xff0c;内容永远是最前置的第一要素。 01 当内容被消费过&#xff0c;就…

GD32替换STM32使用HAL库开发问题

GD32HAL库开发问题 1can初始化进入error handle2发送邮箱不能按照填写顺序发送3 GD32修改代码被stm32cudemx覆盖问题 1can初始化进入error handle HAL库的HAL_CAN_Init中&#xff0c;hcan->Instance->MSR寄存器无法清零&#xff0c;STM32先清零&#xff0c;再退出睡眠模…

LL(1)语法分析程序设计与实现

制作一个简单的C语言词法分析程序_用c语言编写词法分析程序-CSDN博客文章浏览阅读322次。C语言的程序中&#xff0c;有很单词多符号和保留字。一些单词符号还有对应的左线性文法。所以我们需要先做出一个单词字符表&#xff0c;给出对应的识别码&#xff0c;然后跟据对应的表格…

AMEYA360:村田首款1608M尺寸/100V静电容量1µF的MLCC实现商品化

株式会社村田制作所成功开发了用于基站、服务器和数据中心48V线路的多层陶瓷电容器“GRM188D72A105KE01”并已量产。该产品在1608M(1.60.8mm)尺寸、100V的额定电压下可实现1μF的超大静电容量(村田调查数据&#xff0c;截至2023年11月20日)。目前可向村田申请免费样品。 随着5G…

Python入门教学——输入任意长度的int整型一维数组

使用python输入一个任意长度的整型一维数组&#xff1a; nums input("请输入整数数组&#xff0c;用空格分隔&#xff1a; ") nums [int(i) for i in nums.split( )] # 将每个数转换为整型后输出 运行结果&#xff1a; 【注】如果不强制转换类型&#xff0c;数字…

2023 极客巅峰线上

linkmap 考点: 栈溢出ret2csu栈迁移 保护: 开了 Full RELRO 和 NX, 所以这里不能打 ret2dl 题目给了一些有用的函数: 在这个函数中, 我们可以把一个地址的数据存放到 BSS 段上. 漏洞利用 可以把一个 libc 地址比如 readgot 读取到 bss 上, 然后在修改其为 syscall. 后面就是…

【云原生】初识 Service Mesh

目录 一、什么是Service Mesh 二、微服务发展历程 2.1 微服务架构演进历史 2.1.1 单体架构 2.1.2 SOA阶段 2.1.3 微服务阶段 2.2 微服务治理中的问题 2.2.1 技术栈庞杂 2.2.2 版本升级碎片化 2.2.3 侵入性强 2.2.4 中间件多&#xff0c;学习成本高 2.2.5 服务治理功…

Vue-报错No “exports“ main defined in xx

vue报错&#xff1a;No "exports" main defined in F:\wjh\vue#Practice\EasyQuestionnaire-web-master\EasyQuestionnaire-web-master\node_modules\babel\helper-compilation-targets\package.json 1.在文件中找到该路径的package.json文件&#xff0c; 2.按照提示…

值得考虑的10大开源的ERP系统

有许多开源的企业资源计划&#xff08;ERP&#xff09;系统可供选择。这些系统提供了一整套业务管理工具&#xff0c;涵盖了财务、人力资源、供应链管理等多个领域。以下是一些知名的开源ERP产品&#xff1a; NO1.Odoo ERP 了解更多&#xff1a;http://www.odoochina.com.cn/…

赛轮集团SAILUN方程式赛车轮胎震撼登场,开启新篇章

11月初&#xff0c;在厦门国际赛车场&#xff0c;SAILUN方程式赛车轮胎展现出令人瞩目的实力&#xff0c;成功完成了首次震撼亮相。这一引人注目的表现为未来的赛车轮胎技术发展打开了崭新的一页。 在这次首次亮相的测试中&#xff0c;职业车手巧妙操控着SAILUN方程式赛车轮胎&…

Python Pandas简介及基础教程+实战示例。

文章目录 前言一、Pandas简介二、Python Pandas的使用关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战案例③Python小游戏源码五、面试资料六、Python兼职渠道 前言 Pan…

『亚马逊云科技产品测评』活动征文|AWS 存储产品类别及其适用场景详细说明

授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚马逊云科技官方渠道 目录 前言、AWS 存储产品类别 1、Amazon Elastic Block Store (EBS) …

matplotlib violinplot换颜色

本来用的是箱图&#xff0c;后来发现这个图更好看&#xff0c;就想要学习一下&#xff0c;官方有给教程&#xff0c;当然可以直接学习 https://matplotlib.org/stable/gallery/statistics/customized_violin.html 以上是官方给的&#xff0c;效果是这个样子的 这个从最基本的蓝…

详解自动化之单元测试工具Junit

目录 1.注解 1.1 Test 1.2 BeforeEach 1.3 BeforeAll 1.4 AfterEach 1.5 AfterAll 2. 用例的执行顺序 通过 order() 注解来排序 3. 参数化 3.1 单参数 3.2 多参数 3.3 多参数(从第三方csv文件读取数据源) 3.4 动态参数ParameterizedTest MethodSource() 4. 测试…

解决vue element - ui 弹窗打开表单自动校验问题

1 打开弹窗清除自动校验 在data 里面把所有表单字段都定义一下 2 弹窗关闭事件 清除校验

Vue批量全局处理undefined和null转为““ 空字符串

我们在处理后台返回的信息&#xff0c;有的时候返回的是undefined或者null&#xff0c;这种字符串容易引起用户的误解&#xff0c;所以需要我们把这些字符串处理一下。 如果每个页面都单独处理&#xff0c;那么页面会很冗余&#xff0c;并且后期如果有修改容易遗漏&#xff0c…

Banana Pi BPI-R3 Mini 开源路由器,也能拍出艺术美感

香蕉派BPI-R3 Mini路由器板开发板采用联发科MT7986A(Filogic 830)四核ARM A53芯片设计&#xff0c;板载2G DDR 内存&#xff0c;8G eMMC和128MB SPI NAND存储&#xff0c;是一款非常高性能的开源路由器开发板&#xff0c;支持Wi-Fi6 2.4G/5G&#xff08;MT7976C&#xff09;&am…

ImportError: Unknown magic number 3495 in test.pyc

在进行pyc文件反编译时遇到如下报错&#xff1a; 这个问题是我们生成的pyc文件本身存在的问题 pyc文件生成时&#xff0c;头部的magic number被清理&#xff0c;需要我们另外补上。 我们先观察对比一下正确的pyc文件头与报错的pyc文件头&#xff1a; 正常的pyc文件 丢头部的…

开源之夏 2023 | Databend 社区项目总结与分享

开源之夏是由中科院软件所“开源软件供应链点亮计划”发起并长期支持的一项暑期开源活动&#xff0c;旨在鼓励在校学生积极参与开源软件的开发维护&#xff0c;培养和发掘更多优秀的开发者&#xff0c;促进优秀开源软件社区的蓬勃发展&#xff0c;助力开源软件供应链建设。 官…