建设微信网站要多少钱,网站平台选择,长沙人才招聘网长沙58同城招聘网,上门做网站哪家好目录
LeetCode 20、有效的括号
题目描述#xff1a;
思路解析#xff1a;
解题代码#xff1a;
通过代码#xff1a;
LeetCode 225、用队列实现栈
题目描述#xff1a;
思路解析#xff1a;
解题代码#xff1a;
通过代码#xff1a;
LeetCode 232、用栈…目录
LeetCode 20、有效的括号
题目描述
思路解析
解题代码
通过代码
LeetCode 225、用队列实现栈
题目描述
思路解析
解题代码
通过代码
LeetCode 232、用栈实现队列
题目描述
思路解析编辑
解题代码
通过代码
LeetCode 622、设计循环队列
题目描述
思路解析
解题代码
通过代码 LeetCode 20、有效的括号
题目描述 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 1 输入s ()
输出true示例 2 输入s ()[]{}
输出true示例 3 输入s (]
输出false提示 1 s.length 104s 仅由括号 ()[]{} 组成 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路解析
利用栈先进后出的特点让栈内元素依次与新元素比较。 解题代码
我们还是要先拷贝一份栈放在OJ题目上方并且注意我们需要更改STDataType为char类型我们要更改的不止这些我们还要改一下我们的assert我们要把暴力的判断变成温柔的判断其中重点是STPop和STTop 根据思路写出如下代码 我们根据我们的思路写出了如上代码实验后发现通过所有测试案例在提交时却出现错误经过调试后发现当传入一个括号时会跳过我们判错的代码直接来到判对 这就是我们的数量不匹配我们可以在最后进行一个判空如果最后栈没空说明数量不匹配。 这样一修改就可以啦。
通过代码
typedef char STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);if(!pst-top 0){return;}pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);if(!pst-top 0){return 0;}return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}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 {)){;}else{return 0;}}s;}bool ans STEmpty(st);STDestroy(st);return ans;
}
LeetCode 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双端队列来模拟一个队列 , 只要是标准的队列操作即可。 示例 输入
[MyStack, push, push, top, pop, empty]
[[], [1], [2], [], [], []]
输出
[null, null, null, 2, 2, false]解释
MyStack myStack new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False提示 1 x 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空 进阶你能否仅用一个队列来实现栈。 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路解析
首先我们先复习一下栈和队列的性质 此时我们的两个队列他们的功能分别是存储数据和导出数据
解题代码
此时因为我们需要用到队列所以我们需要先把我们写的队列拷贝一份在OJ代码上面 同时也别忘记我们在队列部分写过的函数我们可以不用自己判空在插入时哪个不为空我们就插入到哪个队列此时那个队列是专门用来存储数据的。 在删除时我们也可以使用QueueSize对队列数据的个数进行判断用QueueFront进行导入队头操作此时该队列承担的是导数据的任务 同时导入队头的同时不要忘记要将队头Pop出去。 在去栈首的时候我们取到的是队列的最后一个元素首先想到的肯定是返回我们导完数据后剩的那个元素直接CV上面的代码但是我们要能想到在写队列时我们写过取队尾函数QueueBack我们可以直接进行判空操作返回不为空队列的最后一个元素。 当然判空也很简单我们只需要同时判断两个队列即可。
最后free时我们可以直接释放我们malloc的MyStack* pst呢我们来画张图看一下
所以在free掉栈之前要把两个队列先free由于不知道哪个为空所以我们两个都free。
通过代码
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq); assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}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))QueuePush(obj-q1, x);elseQueuePush(obj-q2, x);
}int myStackPop(MyStack* obj)
{Queue* noneempty obj-q1;//用noneempty指向非空栈Queue* empty obj-q2;//用empty指向空栈if (!QueueEmpty(obj-q2)){noneempty obj-q2;empty obj-q1;}while (QueueSize(noneempty) 1){QueuePush(empty, QueueFront(noneempty));QueuePop(noneempty);}int top QueueFront(noneempty);QueuePop(noneempty);return top;
}int myStackTop(MyStack* obj)
{if (!QueueEmpty(obj-q1))return QueueBack(obj-q1);elsereturn QueueBack(obj-q2);
}bool myStackEmpty(MyStack* obj)
{return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj)
{QueueDestroy(obj-q1);QueueDestroy(obj-q1);free(obj);obj NULL;
}
LeetCode 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双端队列来模拟一个栈只要是标准的栈操作即可。 示例 1 输入
[MyQueue, push, push, peek, pop, empty]
[[], [1], [2], [], [], []]
输出
[null, null, null, 1, 1, false]解释
MyQueue myQueue new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false 提示 1 x 9最多调用 100 次 push、pop、peek 和 empty假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路解析 解题代码
我认为代码的唯一难点就是在于什么时候导数据在哪个函数时要把PushSt中的元素导入PushSt
我们可以在STPeek中导数据然后可以在STPop时再调用STPeek再进行STPop 通过代码
typedef char STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);if (!(pst-top 0)){return;}pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);if (!(pst-top 0)){return 0;}return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}typedef struct
{ST PushSt;ST PopSt;
} MyQueue;MyQueue* myQueueCreate()
{MyQueue* pq (MyQueue*)malloc(sizeof(MyQueue));STInit(pq-PushSt);STInit(pq-PopSt);return pq;
}void myQueuePush(MyQueue* obj, int x)
{STPush(obj-PushSt, x);
}int myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);STPop(obj-PopSt);return front;
}int myQueuePeek(MyQueue* obj)
{if (STEmpty(obj-PopSt)){while (!STEmpty(obj-PushSt)){STPush(obj-PopSt, STTop(obj-PushSt));STPop(obj-PushSt);}}return STTop(obj-PopSt);
}bool myQueueEmpty(MyQueue* obj)
{return obj-PopSt.top NULL obj-PushSt.top NULL;
}void myQueueFree(MyQueue* obj)
{STDestroy(obj-PopSt);STDestroy(obj-PushSt);free(obj);obj NULL;
}
LeetCode 622、设计循环队列
题目描述 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 你的实现应该支持如下操作 MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。 示例 MyCircularQueue circularQueue new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4 提示 所有的值都在 0 至 1000 的范围内操作数将在 1 至 1000 的范围内请不要使用内置的队列库。 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路解析 解题代码
我们先对我们存储容器进行定义这里我们以数组为例 然后先看一下我们刚才已经解决了的问题的代码块判空和判满 对于插入和删除我们只需要对front和back下标进行操作即可 但是不只只是这样就结束了我们在很多地方都应该判断队列是否满或者是否空比如插入时判断是否已满取头取尾时判断是否为空具体代码大家可以看通过代码。
通过代码
typedef struct
{int* a;int front;int back;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a (int*)malloc(sizeof(int) * (k 1));obj-front 0;obj-back 0;obj-k k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-front obj-back;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{return obj-front (obj-back 1) % (obj-k 1);
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if (myCircularQueueIsFull(obj)){return false;}obj-a[obj-back] value;obj-back;obj-back % (obj-k 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front % (obj-k 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return -1;}else if (obj-back 0){return obj-a[obj-k];}else{return obj-a[obj-back - 1];}
}void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}
