(C语言版)力扣(LeetCode)栈和队列面试题

news/2024/2/27 22:31:47

在这里插入图片描述

栈和队列面试题

  • 20. 有效的括号
    • 题目
    • 解法一:建立栈解决
    • 解法二:数组模拟栈解决
  • 225. 用队列实现栈
  • 题目
    • 解法:两个队列实现栈
  • 232. 用栈实现队列
    • 题目
    • 解法:两个栈实现队列
  • 622. 设计循环队列
    • 题目
    • 解法一:数组
    • 解法二:链表
  • 结语

20. 有效的括号

题目

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

题目链接:有效的括号

解法一:建立栈解决

代码如下:

typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void StackPop(ST* ps)
{assert(ps);ps->top--;
}STDataType StackTop(ST* ps)
{assert(ps);return ps->a[ps->top - 1];
}int StackSize(ST* ps)
{assert(ps);return ps->top;
}bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}bool isValid(char * s){ST st;StackInit(&st);while(*s){if(*s == '('|| *s == '{'|| *s == '['){StackPush(&st,*s);++s;}else{if(StackEmpty(&st)){StackDestroy(&st);return false;}STDataType top = StackTop(&st);StackPop(&st);if((*s == '}') && top != '{'|| (*s == ']') && top != '['|| (*s == ')') && top != '('){StackDestroy(&st);return false;}else{++s;}}}bool ret=StackEmpty(&st);StackDestroy(&st);return ret;
}

在C语言中,因为没有现成的栈可以调用,所以这里首先我们建立一个栈结构及各种操作函数建立,以便于这里的函数实现进行调用,这里我们首先建立一个栈st,初始化栈st,第一层while循环判定数组中有没有元素,进入循环后如果首元素为左括号入栈,并将指针位置后移一位,再看else语句,如果栈为空,说明上一段条件语句没执行,直接返回false,不执行这句,说明栈中有元素,则先将栈顶值记录,再删除栈顶元素,再进行括号匹配,如果s此时指向的是右括号并且top不等于左括号,说明不匹配,等于就将指针位置后移再进行匹配,最后遍历完,如果栈为空,则都匹配,否则就不匹配。这种写法代码虽然长,但是相对来说很好理解。
如下图:
在这里插入图片描述

解法二:数组模拟栈解决

代码如下:

char pairs(char a)
{if(a==')') return '(';if(a=='}') return '{';if(a==']') return '[';return 0;
}
bool isValid(char * s){int n=strlen(s);if(n%2==1)return false;int stk[n],i=0,top=0;for(i=0;i<n;i++){char ch=pairs(s[i]);if(ch){if(top==0||stk[top-1]!=ch)return false;top--;}elsestk[top++]=s[i];}return top==0;
}

这里我们创建一个pairs函数进行返回匹配,如果a是右括号则返回左括号,否则返回0,再看我们的主调函数,我们首先记录字符串长度,如果长度为奇数,直接返回false,如果没进入条件语句,则执行下面语句,首先我们建立字符串长度的数组stk,然后就是一个for循环,循环次数为字符串长度(防止最坏情况,全为左括号),首先记录第一个字符调用pairs函数进行匹配,如果是左括号,返回0;进入else语句,stk首元素记录第一个字符,top+1,再进行第二次循环,如果为右括号,则ch记录为左括号,进行匹配,如果相同,top-1,不相同则直接返回false,循环结束,如果top等于0,则返回ture,否则为false,其实这种写法原理和上面是一样的,只不过编写形式不一样。
如下图:
在这里插入图片描述

225. 用队列实现栈

题目

请你仅使用两个队列实现一个后入先出(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 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

题目链接:用队列实现栈

解法:两个队列实现栈

代码如下:

typedef struct {int queue1[100];int queue2[100];int front1;int front2;int rear1;int rear2;
} MyStack;MyStack* myStackCreate() {MyStack* stack=malloc(sizeof(MyStack));stack->front1=0;stack->front2=0;stack->rear1=0;stack->rear2=0;return stack;
}void myStackPush(MyStack* obj, int x) {obj->queue1[(obj->rear1)++]=x;
}int myStackPop(MyStack* obj) {int front1=obj->front1;int front2=obj->front2;int rear1=obj->rear1;int rear2=obj->rear2;while(rear1-front1>1){obj->queue2[rear2++]=obj->queue1[front1++];}int top=obj->queue1[front1++];while(front2!=rear2){obj->queue1[rear1++]=obj->queue2[front2++];}obj->front1=front1;obj->front2=front2;obj->rear1=rear1;obj->rear2=rear2;return top;
}int myStackTop(MyStack* obj) {return obj->queue1[obj->rear1-1];
}bool myStackEmpty(MyStack* obj) {return obj->queue1[obj->front1]==obj->queue2[obj->front2];
}void myStackFree(MyStack* obj) {obj->front1=obj->front2=obj->rear1=obj->rear2=0;
}

具体思路如下图:
请添加图片描述
入栈
请添加图片描述
入栈
请添加图片描述

请添加图片描述
请添加图片描述
出栈
请添加图片描述

232. 用栈实现队列

题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

解法:两个栈实现队列

代码如下:

typedef struct {int* stk;int stksize;int stkcapacity;
}Stack;Stack* createStack(int capacity)
{Stack* ret=malloc(sizeof(Stack));ret->stk=malloc(sizeof(int)*capacity);ret->stksize=0;ret->stkcapacity=capacity;return ret;
}void stackpush(Stack* obj,int x)
{obj->stk[obj->stksize++]=x;
}void stackpop(Stack* obj)
{obj->stksize--;
}int stacktop(Stack* obj)
{return obj->stk[obj->stksize-1];
}bool stackempty(Stack* obj)
{return obj->stksize==0;
}void stackfree(Stack* obj)
{free(obj->stk);
}typedef struct {Stack* inqueue;Stack* outqueue;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret=malloc(sizeof(MyQueue));ret->inqueue=createStack(100);ret->outqueue=createStack(100);return ret;
}void inout(MyQueue* obj)
{while(!stackempty(obj->inqueue)){stackpush(obj->outqueue,stacktop(obj->inqueue));stackpop(obj->inqueue);}
}void myQueuePush(MyQueue* obj, int x) {//stackpush(obj->inqueue,x);obj->inqueue->stk[obj->inqueue->stksize++]=x;
}int myQueuePop(MyQueue* obj) {if(stackempty(obj->outqueue)){inout(obj);}int x=stacktop(obj->outqueue);stackpop(obj->outqueue);return x;
}int myQueuePeek(MyQueue* obj) {if(stackempty(obj->outqueue)){inout(obj);}return stacktop(obj->outqueue);
}bool myQueueEmpty(MyQueue* obj) {return (stackempty(obj->inqueue)&&stackempty(obj->outqueue));
}void myQueueFree(MyQueue* obj) {stackfree(obj->inqueue);stackfree(obj->outqueue);
}

具体思路如下图:
在这里插入图片描述

622. 设计循环队列

题目

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

题目链接:设计循环队列

解法一:数组

代码如下:

typedef struct {int front;//队首int rear;//队尾int capacity;//容量int* elem;//元素
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* ret=malloc(sizeof(MyCircularQueue));ret->capacity=k+1;ret->elem=malloc(sizeof(int)*ret->capacity);ret->front=ret->rear=0;return ret;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if((obj->rear+1)%obj->capacity==obj->front)return false;obj->elem[obj->rear]=value;obj->rear=(obj->rear+1)%obj->capacity;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(obj->front==obj->rear)return false;obj->front=(obj->front+1)%obj->capacity;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(obj->front==obj->rear)return -1;return obj->elem[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(obj->front==obj->rear)return -1;return obj->elem[(obj->rear-1+obj->capacity)%obj->capacity];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%obj->capacity==obj->front;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->elem);free(obj);
}

首先是队列结构体的建立,然后是队列初始化创建,和普通队列不同的是这里的capacity是给定值k+1,这里的用处在后面的函数会体现。

入队列:首先判定队尾下标+1模上容量等于队首下标,说明队列已经满了,返回false。入队为队尾值为下标,更新队尾值为+1模上容量,而不是直接++。

出队列:题目要求是直接删除,返回逻辑值,所以这里直接删除队首值对应下标元素,同样是队首值+1模上容量,实际此时并没删除,但是等到队尾值对应下标访问该位置入队列时会直接覆盖,而且此时这个位置也不是合法位置,所以不需要直接将其删除。

返回队首值:题目要求队列为空返回-1,只有队首等于队尾时,队列才为空,否则直接返回队首值对应下标元素即为队首。

返回队尾值:为空和上面一样,否则返回队尾值-1加上容量值再%上容量,很多人看不懂这句,举个例子,假设这时队列是满的,那么如果队尾值为0,减去1的话为负值,再去取余数就出现了越界,而且返回值是错的。

返回队列是否为空:返回队首队尾是否相等即可

返回队列是否已满:队尾值+1模上容量如果等于front,那就满了

讲到这你会发现容量的初始值设定非常的奇妙,它是循环队列思路的关键。

解法二:链表

代码如下:

typedef struct {struct ListNode *head;//队首指针struct ListNode *tail;//队尾指针int capacity;//容量int size;//长度
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));obj->capacity = k;obj->size = 0;obj->head = obj->tail = NULL;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (obj->size >= obj->capacity) {return false;}struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));node->val = value;node->next = NULL;if (!obj->head) {obj->head = obj->tail = node;} else {obj->tail->next = node;obj->tail = node;}obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->size == 0) {return false;}struct ListNode *node = obj->head;obj->head = obj->head->next;  obj->size--;free(node);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj->size == 0) {return -1;}return obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->size == 0) {return -1;}return obj->tail->val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {for (struct ListNode *curr = obj->head; curr;) {struct ListNode *node = curr;curr = curr->next;free(node);}free(obj);
}

这种写法是使用双向循环链表的写法,个人觉得这种写法比上面的要更好理解
首先是队列结构体的建立和初始化队列

入队列:如果长度等于容量队列已满,返回false,这里插入分两种情况,第一种是第一次插入时,首位指针都指向该元素结点,之后每次插入为第二种情况,一直挪动尾指针即可,插入成功,size+1,返回true

出队列:如果size为0,返回false,头指针指向下一结点,size-1,返回true

返回队首值:直接返回队首指针指向元素即为队首。

返回队尾值:直接返回队尾指针指向元素即为队尾。

返回队列是否为空:返回队首size是否为0。

返回队列是否已满:size等于capacity就满了。

结语

这里的解法代码部分来自力扣官方和作者自己的解法,作者只是进行了详细的剖析和部分改动方便大家理解和提升自己,学会多角度观察问题,解决问题。

有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!
制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!
在这里插入图片描述


http://www.ppmy.cn/news/70013.html

相关文章

赫夫曼树和赫夫曼编码详解

目录 何为赫夫曼树&#xff1f; 赫夫曼树算法 赫夫曼编码 编程实现赫夫曼树 编程实现赫夫曼编码 编程实现WPL 总代码及分析 何为赫夫曼树&#xff1f; 树的路径长度&#xff1a;从树根到每一结点的路径长度之和 结点的带权路径长度&#xff1a;从树根到该结点的路径长度…

【sed编辑器】

目录 一、sed编辑器二、sed的命令格式操作命令1.1、命令演示 二、替换三、插入 一、sed编辑器 1、sed是一种流编辑器&#xff0c;流编辑器会在编辑器处理数据之前基于预先提供的一组规则来编辑数据流。 2、sed编辑器可以根据命令来处理数据流中的数据&#xff0c;这些命令要么…

【冰糖Python】scikit-learn中的random_state参数

随机化是机器学习方法的一部分&#xff0c;使用伪随机是方法结果可再现的关键。 sklearn中的一个重要参数是random_state&#xff0c;用于控制随机数生成器&#xff0c;即设定随机种子。 比如&#xff0c;在train_test_split&#xff0c;svm.SVC中均存在random_state参数。 …

支持AI算法定制的4G摄像头模组解决方案

随着科技的不断发展&#xff0c;现在人们对于监控摄像头的需求越来越高&#xff0c;但是市场上的大多数摄像头组件都是标准化的&#xff0c;很难满足不同应用场景的需求。 不过&#xff0c;现在有了这款支持AI算法定制的4G摄像头模组解决方案&#xff0c;这个问题就完美的解决了…

麻了,真的不想做测试了...

前言 有不少技术友在测试群里讨论&#xff0c;近期的面试越来越难了&#xff0c;要背的八股文越来越多了,考察得越来越细&#xff0c;越来越底层&#xff0c;明摆着就是想让我们徒手造航母嘛&#xff01;实在是太为难我们这些测试工程师了。 这不&#xff0c;为了帮大家节约时…

需求管理(三)需求过程

一、需求规格说明 1.1需求规格说明概述 需求获取的目标是得到用户的需求——收集需求信息 需求分析的目标是更深刻的理解用户的需求——界定能够让用户满意的解决方案和准则 需求规格说明的目标是定义用户的需求——准确描述其需求和解决方案 需求规格说明文档的撰写流程如下图…

保护个人隐私和数据安全的方法与策略

引言 随着信息技术的普及和发展&#xff0c;我们享受到了便捷的互联网服务&#xff0c;但与此同时&#xff0c;个人隐私和数据安全问题也日益受到威胁。在这个所谓的"裸奔"时代&#xff0c;网络攻击、数据泄露和隐私侵犯已经成为常态。然而&#xff0c;我们并不无助…

下载和安装appuploader

转载&#xff1a;下载和安装appuploader IOS开发工具官网地址 Appuploader home -- A tool improve ios develop efficiency such as submit ipa to appstore and manage ios certificate 最新版本已经优化了没支付688给apple的账号登录流程&#xff0c;无需再安装其他软件。…

自监督ViT:DINO-v1和DINO-v2

1. 概述 基于ViT&#xff08;Vision Transformer&#xff09;自监督在最近几年取得了很大进步&#xff0c;目前在无监督分类任务下已经超过了之前的一些经典模型&#xff0c;同时在检测分割等基础任务领域也展现出了强大的泛化能力。这篇文章将主要基于DINO系列自监督算法介绍…

shell脚本之“sed“命令

文章目录 1.sed编辑器概述2.sed命令常用选项3.sed命令常用操作4.sed命令演示操作部分5.总结 1.sed编辑器概述 sed是一种流编辑器&#xff0c;流编辑器会在编辑器处理数据之前基于预先提供的一组规则来编辑数据流。 sed编辑器可以根据命令来处理数据流中的数据&#xff0c;这些…

企业战略管理:精要

一、企业战略管理的概念与流派 国内外学者对企业战略和企业战略管理的各种理解— 安索夫&#xff1a;企业在确定战略前&#xff0c;应该先确定自己的经营性质安德鲁斯&#xff1a;企业战略管理是一个决策模式&#xff0c;决定企业的目标&#xff0c;提出实现目标的方针和计划&…

getx的使用场景,详细举例

Getx是一种在Flutter中使用的状态管理框架&#xff0c;它提供了许多便利的功能&#xff0c;包括路由、依赖注入、状态管理等&#xff0c;以下是一些Getx的使用场景和详细的举例&#xff1a; 路由管理&#xff1a;Getx可以帮助我们在Flutter中管理路由&#xff0c;例如可以使用…

【Python 爬虫之requests库】零基础也能轻松掌握的学习路线与参考资料

文章目录 一、概述二、Requests 库基本用法三、爬虫中的优秀实践四、参考资料 一、概述 Python 爬虫中&#xff0c;常用来请求网页的库有 urllib、urllib2、httplib等&#xff0c;但是这些库用起来比较麻烦&#xff0c;需要写很多代码。Requests 库正是为了解决这个问题而生的…

【分布族谱】正态分布和对数正态分布的关系

文章目录 正态分布对数正态分布的推导测试 正态分布 正态分布&#xff0c;最早由棣莫弗在二项分布的渐近公式中得到&#xff0c;而真正奠定其地位的&#xff0c;应是高斯对测量误差的研究&#xff0c;故而又称Gauss分布。。测量是人类定量认识自然界的基础&#xff0c;测量误差…

SaleSmartly聊天机器人如何帮助您的电商业务

从基于规则的机器人到虚拟助手&#xff0c;聊天机器人正在成为网络交互的标准。越来越多的企业正在使用它们来吸引客户、改善客户服务并增强用户体验。现在有非常多的软件也提供聊天机器人的帮助&#xff0c;比如SaleSmartly&#xff08;ss客服&#xff09;&#xff0c;本文以它…

如何提高跨职能团队的绩效和成果

在50年代&#xff0c;当计算机仍被视为复杂的计算器时&#xff0c;西北互助人寿保险公司就计算机对未来业务的影响进行了研究。有趣的是&#xff0c;该公司的首席执行官为这项研究设立了一个不同寻常的团队——由来自多个部门的员工组成&#xff0c;每个人都看到了计算机在保险…

计网笔记 数据链路层 (1-2) 封装成帧、差错控制、流量控制与可靠传输、停止等待协议、后退N帧协议(GBN)、选择重传协议(SR)

文章目录 前言在这里插入图片描述 零、数据链路层基本概念一、功能0、数据链路层功能概述1、封装成帧和透明传输1.1封装成帧1.2 透明传输1.3组帧方法 2、数据链路层的差错控制2.0差错从何而来2.1位错&#xff08;比特错&#xff0c;1变成0&#xff0c;0变成1&#xff09;2.2帧错…

记一次靶场搭建与渗透测试

渗透目标 通过Windows7打入工作组环境&#xff0c;穿透两层内网拿到DC&#xff08;域控制器&#xff09;权限 环境搭建 环境搭建 网络拓扑 虚拟机网络配置 渗透测试 永恒之蓝外网打点 nmap -sS 192.168.2.0/24扫描外网存活主机&#xff0c;发现两台主机192.168.2.128和192…

7.机器学习诊断法

怎样评估机器学习算法的性能&#xff1f; 利用机器学习诊断法来评估机器学习算法的性能。诊断法是一种测试法&#xff0c;通过这种测试能够了解算法在哪里出了问题&#xff0c;这也能够告诉我们要想改进一种算法的效果、什么样的尝试才是有意义的。 7.1 评估假设 评价算法学…

0702可分类变量的微分方程-微分方程

文章目录 1 一阶微分方程变形2 可分离变量的微分方程2.1 定义2.2 解法 3 例题结语 1 一阶微分方程变形 本节至第四节我们学习的都是一阶微分方程 ​ y ′ f ( x , y ) y^{}f(x,y) y′f(x,y) &#xff08;2-1&#xff09; 一阶微分方程对称形式 p ( x , y ) d x Q ( x , …
最新文章