代码随想录算法训练营第九天|232.用栈实现队列，225.用队列实现栈，20.有效的括号，1047.删除字符串中的所有相邻重复项

232.用栈实现队列看到题目的第一想法熟悉栈的操作看完代码随想录的第一想法用栈模拟队列需要定义输入栈和输出栈将内容放到输入栈中再将内容放到输出栈中取出来就是队列的先进先出用自己的话描述设置两个栈 stackIn 和 stackOut。push 操作直接压入 stackIn。pop/peek 操作时如果 stackOut 为空就把 stackIn 的所有元素依次弹出并压入 stackOut这样顺序就反转了相当于队列的先进先出。然后从 stackOut 弹出/查看顶部元素。关键点是 dumpstackIn() 只在 stackOut 为空时才执行均摊时间复杂度 O(1)。代码classMyQueue{StackIntegerstackIn;StackIntegerstackOut;publicMyQueue(){stackInnewStack();stackOutnewStack();}publicvoidpush(intx){stackIn.push(x);}publicintpop(){dumpstackIn();returnstackOut.pop();}publicintpeek(){dumpstackIn();returnstackOut.peek();}publicbooleanempty(){returnstackIn.isEmpty()stackOut.isEmpty();}privatevoiddumpstackIn(){if(!stackOut.isEmpty())return;while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}}实现过程中遇到哪些困难没有困难今日收获记录一下自己的学习时长学习时长18 分钟225.用队列实现栈看到题目的第一想法模拟栈操作用一个队列好像没有好方法用两个队列倒是有点思路看完代码随想录的第一想法确实是用两个队列来模拟栈用自己的话描述用两个队列模拟栈直接让输入的元素进入副队列然后将主队列的旧元素放到副元素的队尾即可然后交换元素引用解决问题代码classMyStack{//先创建两个栈QueueIntegerqueue1;QueueIntegerqueue2;publicMyStack(){//堆两个栈进行初始化queue1newLinkedList();queue2newLinkedList();}publicvoidpush(intx){//先放入副队列queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}//交换引用QueueIntegerqueueTemp;queueTempqueue1;queue1queue2;queue2queueTemp;}publicintpop(){//直接弹出队头元素returnqueue1.poll();}publicinttop(){//查看队头元素returnqueue1.peek();}publicbooleanempty(){//主队列不为空returnqueue1.isEmpty();}}/** * Your MyStack object will be instantiated and called as such: * MyStack obj new MyStack(); * obj.push(x); * int param_2 obj.pop(); * int param_3 obj.top(); * boolean param_4 obj.empty(); */实现过程中遇到哪些困难没什么困难就是语法不熟悉今日收获记录一下自己的学习时长收获了队列语法的使用学习时长20 分钟20.有效的括号看到题目的第一想法将符号一一对应消除确实是没想法看完代码随想录的第一想法用栈这个数据结构确实是可以解决用自己的话描述了解了数据结构用简单的if判断一下很快就出来了。总体而言就是先把内容放进去然后再判断是否对应然后进行弹出只不过我代码里的把内容放进去是在判断的字符的后面不过也必须要在判断字符的后面因为字符内容需要先判断清楚才能放入代码classSolution{publicbooleanisValid(Strings){//先定义一个栈StackCharacterstacknewStack();for(charc:s.toCharArray()){//判断字符的另一半如果存在就弹出如果不存在就存入if(c)!stack.isEmpty()stack.peek()(){stack.pop();}elseif(c}!stack.isEmpty()stack.peek(){){stack.pop();}elseif(c]!stack.isEmpty()stack.peek()[){stack.pop();}else{stack.push(c);}}//如果stack为空那就正常返回true反之为falsereturnstack.isEmpty();}}实现过程中遇到哪些困难对栈的类不太熟悉思路不清晰今日收获记录一下自己的学习时长学习到了 Stack 这个栈学习时长16 分钟9:42-9:581047.删除字符串中的所有相邻重复项看到题目的第一想法都是消消乐的类型应该也是用到栈去解决看完代码随想录的第一想法确实是用到了栈这个数据结构消消乐的思想和上一题基本差不多不过这题学习新的类用自己的话描述将字符串拆成一个个字符放入栈每一次放入都看看栈顶是不是不一样或空符合就放入发现一样就拿出栈顶元素剩下的就是倒序的字符了然后排个序即可代码classSolution{publicStringremoveDuplicates(Strings){//定义一个双端队列来做栈,一个字符变量用来接单个字符ArrayDequeCharacterdequenewArrayDeque();charc;//遍历字符串如果栈为空或栈顶元素不一样就放进去如果发现一样就消除for(inti0;is.length();i){cs.charAt(i);if(deque.isEmpty()||deque.peek()!c){deque.push(c);}else{deque.pop();}}//剩下的元素就是删除所有相邻重复项之后的元素但是为倒序Stringstr;//倒序数特殊处理一下while(!deque.isEmpty()){strdeque.pop()str;}returnstr;}}实现过程中遇到哪些困难不了解 ArrayDeque 这个数据结构今日收获记录一下自己的学习时长了解了 ArrayDeque 这个数据结构学习时长28 分钟10:05-10:33