leetcode 有效括号和循环队列

leetcode 有效括号和循环队列

1. 有效的括号

本题目来源于leetcode有效的括号

1.1 题目描述

leetcode 有效括号和循环队列

提示

leetcode 有效括号和循环队列

1.1.1 接口函数

bool isValid(char * s){

}

1.2 大致框架

虽然数组也可以解决问题但是不太好,后面有些题目就会出现问题 我们尝试用栈来解决问题

直接用c肯定是栈要自己写的,因为没有库,所以如果我们这里要用c语言实现这道题,需要自己写一个栈

1.2.1 想法思路

题目的说输入的情况只有左括号或者右括号,所以我们不用管其他的输入可能性

利用栈的先进后出特性,所以我们可以把是左括号类型(有({【)的都放入栈中,然后右括号则开始匹配,如果匹配失败,则直接false,如果成功则通过StackPop把栈最上面一个拿掉,然后判断下一个是否匹配,直到最后一个返回true或者中途不匹配返回false

1.2.2 具体步骤

先得c语言自己实现一下栈

声明

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType ;
struct Stack
{
	STDataType* a;
	int capacity;	//容量,方便增容
	int top;	//栈顶
};

typedef struct Stack Stack;

void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//性质决定了在栈顶数据出入
STDataType StackTop(Stack* pst);
void  StackPop(Stack* pst);

bool StackEmpty(Stack* pst);
int StzckSize(Stack* pst);

函数

void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;

}
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//容量翻倍
		STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity =newCapacity;
	} 
	pst->a[pst->top] = x;
	pst->top++;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];//从高下标往低下标  
}
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));

	pst->top--;
}
bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;//布尔来判断
}

int StzckSize(Stack* pst)
{
	assert(pst);
	return pst->top;//恰好是size
}

然后构建isValid(char * s)

注意事项:

  • 循环里面要由一个分支判断是左括号还是右括号,左括号进栈,右括号判断

  • 不能忘记走完一个分支后s指针要往前继续走

  • 最后如果是空则说明匹配,不空说明不匹配,因为加入最后剩下一个就不判断了会直接返回true,其实应该要false,所以最后应该还是要有一个判断,可以用StackEmpty判断

bool isValid(char * s){
    Stack st;
    StackInit(&st);
    while(*s)
    {
        //左括号入栈
        //右括号找最近的做括号匹配
        if(*s  =='['
           ||*s=='{'
           ||*s=='(')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
              if(StackEmpty(&st))//说明没有前括号
            {
                StackDestroy(&st);
                return false;
            }
            char top=StackTop(&st);
            if((top=='['&&*s!=']')
            ||(top=='('&&*s!=')')
            ||(top=='{'&&*s!='}'))
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                //匹配的
                StackPop(&st);
                ++s;
            }
        }
    } 
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

1.3 整体实现

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType;
struct Stack
{
	STDataType* a;
	int capacity;	//容量,方便增容
	int top;	//栈顶
};

typedef struct Stack Stack;

void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//性质决定了在栈顶数据出入
STDataType StackTop(Stack* pst);
void  StackPop(Stack* pst);
bool StackEmpty(Stack* pst);
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;

}
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//容量翻倍
		STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity =newCapacity;
	} 
	pst->a[pst->top] = x;
	pst->top++;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];//从高下标往低下标  
}
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));

	pst->top--;
}
bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;//布尔来判断
}

bool isValid(char * s){
    Stack st;
    StackInit(&st);
    while(*s)
    {
        //左括号入栈
        //右括号找最近的做括号匹配
        if(*s  =='['
           ||*s=='{'
           ||*s=='(')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
              if(StackEmpty(&st))//说明没有前括号
            {
                StackDestroy(&st);
                return false;
            }
            char top=StackTop(&st);
            if((top=='['&&*s!=']')
            ||(top=='('&&*s!=')')
            ||(top=='{'&&*s!='}'))
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                //匹配的
                StackPop(&st);
                ++s;
            }
        }
    } 
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

小结:

这道题目用c++的话会简单很多,因为可以直接调接口,但是c语言就得自己实现一个栈,会比较麻烦

2. 设计循环队列

本题目来源于leetcode 622. 设计循环队列

这道题目涉及到的可能会深一点,难度会高一点

2.1 题目描述

leetcode 有效括号和循环队列提示

leetcode 有效括号和循环队列

2.1.1 接口函数

typedef struct {

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

}

int myCircularQueueFront(MyCircularQueue* obj) {

}

int myCircularQueueRear(MyCircularQueue* obj) {

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

}

void myCircularQueueFree(MyCircularQueue* obj) {

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

2.2 大致框架

2.2.1 想法思路

用数组或链表实现

要实现循环队列肯定是得用到循环链表了,不能光单链表不是吗,当然数组也可以,链表的话更像是一个环

按照题目的意思我们要实现的功能是能使用之前用过的空间,要求队列满了不能再插入,但是没满或者满了再删了之后,我们可以用之前的位置存放数据

leetcode 有效括号和循环队列

解决空和满

要想完成这样一个题目的要求是不是我们要有两个指针

leetcode 有效括号和循环队列

但是这个想法的话是无法判断这个循环队列里面是空还是满的

所以要区分两种情况,什么时候判定算满,什么时候判定算空

这里采取空出一个位置不存数据来解决,比如说这个队列4个数据就满,则我只存3个那么这时可以判断了

  • 以下的图例上方的是链表,下方演示的是数组
  1. 满就``tail->nextfront`
    leetcode 有效括号和循环队列
  2. 空就tail==front

leetcode 有效括号和循环队列

那么此时我们也能实现poppush操作

小结:

我们一般什么时候会用到这个循环队列呢?

比如说操作系统中的生产者和消费者问题

leetcode 有效括号和循环队列

2.2.2 具体步骤

我们用数组实现一下,因为数组比链表可能实现的简单一点

注意以下步骤实现的函数仍有问题,后面会在找报错问题时解决,整体实现里是正确的代码

myCircularQueueCreate

typedef struct {
int * a;
int k;//队列最多能存多少个数据
int front;  //头
int tail;  //尾(队尾数据的下一个)
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
 MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
 obj->a=(int*)malloc(sizeof(int)*(k+1));//留一个
 obj->front=0;
 obj->tail=0;
 obj->k=k;
 return obj;
}

myCircularQueueIsEmpty

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}

myCircularQueueIsFull

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	int tailNext = obj->tail + 1;
	if (tailNext == obj->k + 1)//防止next走出去
	{
		tailNext = 0;
	}
	return tailNext == obj->front;
}

myCircularQueueEnQueue

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	else
	{
		obj->a[obj->tail] = value;
		++obj->tail;
		if (obj->tail == obj->k + 1)
		{
			obj->tail = 0;
		}
		return true;
	}
}

myCircularQueueDeQueue

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	else
	{
		++obj->front;
		if (obj->front == obj->k + 1)
		{
			obj->front = 0;
		}
		return true;
	}
}

myCircularQueueFront

int myCircularQueueFront(MyCircularQueue* obj) {
	return obj->a[obj->front];
}

myCircularQueueRear

int myCircularQueueRear(MyCircularQueue* obj) {
	int tailPrev = obj->tail - 1;
	if (tailPrev == -1)//防止prev走出去
	{
		tailPrev = obj->k;
	}
	return obj->a[tailPrev];
}

myCircularQueueFree

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

2.2.3 寻找报错问题

leetcode 有效括号和循环队列

说明问题出在Front上,按照值钱的输入的话,在执行这个Front之前这个循环队列里面是没有数据的,所以返回的Front应该是空的,所以说明这个点没有考虑到,如果为空返回-1即可

myCircularQueueFront

int myCircularQueueFront(MyCircularQueue* obj) {
   if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->front] ;
    }
}

那么myCircularQueueRear应该也是一样,虽然没有提示但是可以想到

int myCircularQueueRear(MyCircularQueue* obj) {
	int tailPrev = obj->tail - 1;
	if (tailPrev == -1)//防止prev走出去
	{
		tailPrev = obj->k;
	}
 if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
      return obj->a[tailPrev];
    }
}

2.3 整体实现

#include<stdbool.h>
typedef struct {
	int* a;
	int k;//队列最多能存多少个数据
	int front;  //头
	int tail;  //尾(队尾数据的下一个)
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->a = (int*)malloc(sizeof(int) * (k + 1));//留一个
	obj->front = 0;
	obj->tail = 0;
	obj->k = k;
	return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	int tailNext = obj->tail + 1;
	if (tailNext == obj->k + 1)//防止next走出去
	{
		tailNext = 0;
	}

	return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	else
	{
		obj->a[obj->tail] = value;
		++obj->tail;
		if (obj->tail == obj->k + 1)
		{
			obj->tail = 0;
		}
		return true;
	}
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	else
	{
		++obj->front;
		if (obj->front == obj->k + 1)
		{
			obj->front = 0;
		}
		return true;
	}
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	else
	{
		return obj->a[obj->front];
	}
}

int myCircularQueueRear(MyCircularQueue* obj) {
	int tailPrev = obj->tail - 1;
	if (tailPrev == -1)//防止prev走出去
	{
		tailPrev = obj->k;
	}
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	else
	{
		return obj->a[tailPrev];
	}
}

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

leetcode 有效括号和循环队列

小结:

栈和队列的难点主要在于结构复杂,不在于单个逻辑,写多了就会感觉好多了

后面更难的栈和队列的题目之后会使用c++的stl库再实现

如果老铁们有收获的话,希望给个一键三连哦,谢谢

上一篇:JavaWeb


下一篇:0202 JDBC