栈

题目给出一个字符串 s（仅含有小写英文字母和括号）。 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。 注意，结果中不应包含任何括号。 方法一：栈思路    对于括号序列相关的题，通用的解法是用递归或者栈。     从左至右地遍历整个字符串，用字符串 str 来记录当前层所遍历到的小写英文字母。对于当前遍历的字母： 如果是左括号：把 str 插入到栈中，并且把 str 置空，进入到下一层 如果是右括号：遍历到了右括号，说明当前层的字母已经遍历完了，把 str 反转，并把栈顶的字符串弹出，将反转后的 str 插入到弹出字符串的末尾，将结果赋值给 str 如果是小写英文字母：追加到 str 末尾     可以看到，只有在遍历到了右括号（第一个出现的右括号是最里面的）才会对字符串进行操作，这样可以保证能从括号里到外处理字符串 代码实现import java.util.*;public class test{ publi ...

    针对王道考研第三章（栈与队列）的拓展思考题–最小栈的实现。本文会探讨三种方法来实现，分别是辅助类、单个栈和双栈。 题目    请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。 注：这里要求的是常量级的时间里找到最小值，所以先排序、再查找是不行的，我们必须在需要的时候就要得到最小值 方法一：辅助类（链表类）思路    我们知道，栈其实是一种操作受限的线性表，所以栈的一些操作可以通过链表来实现。这里要我们设计一个栈，而栈的实现我们可以使用链表，先定义一个链表类。 class ListNode{ public int val; public int min; //最小值 public ListNode next; public ListNode(int val, int min, ListNode next){ ...

题目给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 示例：{()}，()[]，都是有效匹配，{()]为无效匹配 方法：栈思路由题目可以知道，要有效匹配，就得左括号和右括号匹配，后出现的左括号总是和先出现的右括号匹配，遵循后进先出的特点，而这一特点就和栈的特点类似 代码实现import java.util.*;public class test{ public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isVaild("{[]}")); }}class Solution{ //算法主体 public boolean isVaild(String s)&# ...