python 栈【测试题】

1.删除最外层的括号

信息

有效括号字符串为空 ("")、"(" + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 “(()(()))” 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

要求

示例 1：

输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

答案

class Solution(object):
    def removeOuterParentheses(self, S):
        """
        :type S: str
        :rtype: str
        """
        last, cur_len = 0, 0
        result = []

        for i, each in enumerate(S):
            if each == '(':
                cur_len += 1
            if each == ')':
                cur_len -= 1
            if cur_len == 0:
                result.append(S[last + 1:i])
                last = i + 1
        return ''.join(result)

solution = Solution()
print(solution.removeOuterParentheses('()()'))

2.棒球比赛

信息

你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
2. “+”（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. “D”（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. “C”（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。

每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。

示例

示例 1:

输入: [“5”,“2”,“C”,“D”,"+"]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
示例 2:

输入: [“5”,"-2",“4”,“C”,“D”,“9”,"+","+"]
输出: 27
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。
注意：

输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。

答案

class Solution:
    def calPoints(self, ops):
        """
        :type ops: List[str]
        :rtype: int
        """
        res = []
        for i in range(len(ops)):
            if ops[i] == "C":
                res.pop()
            elif ops[i] == "D":
                res.append(res[-1] * 2)
            elif ops[i] == '+':
                res.append(res[-1] + res[-2])
            else:
                res.append(int(ops[i]))
        return sum(res)

3. 用栈实现队列

要求

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

答案

from collections import deque
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.Myqueue = deque()
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.Myqueue.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self.Myqueue) > 0:
            return self.Myqueue.popleft()
        else:
            return None

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.Myqueue) > 0:
            return self.Myqueue[0]
        else:
            return None
        
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.Myqueue) == 0

4.用队列模拟栈

描述

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

注意

你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

答案

class MyStack(object):

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.stack = []
    self.length = 0

def push(self, x):
    """
    Push element x onto stack.
    :type x: int
    :rtype: None
    """
    self.stack.append(x)
    self.length += 1


def pop(self):
    """
    Removes the element on top of the stack and returns that element.
    :rtype: int
    """
    if self.empty() is False:
        self.length -= 1
        return self.stack.pop()

def top(self):
    """
    Get the top element.
    :rtype: int
    """
    if self.empty() is False:
        return self.stack[self.length - 1]

def empty(self):
    """
    Returns whether the stack is empty.
    :rtype: bool
    """
    if len(self.stack) == 0:
        return True
    return False

5.下一个更大的元素（未解）

信息：

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。

示例：

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于num1中的数字2，第二个数组中的下一个较大数字是3。
对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。

注意:

nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。

答案：

未解

6.删除字符串中的所有相邻重复项

信息

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：“abbaca”
输出：“ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

答案：

class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack=[]  # 定义一个栈
        for i in S:
            if not stack: # 如果当前栈为空
                stack.append(i)
            elif i == stack[-1]: # 如果当前元素与栈顶元素相等
                stack.pop()
            else:
                stack.append(i)
        return ''.join(stack)

7. 获取栈中的最小元素 (时间复杂度较大)

信息

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

答案

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.flag=0
    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        if  self.stack:
            self.stack.pop()
            

    def top(self) -> int:
        if self.stack:
            return self.stack[-1]

    def getMin(self) -> int:
        self.flag = self.stack[0]
        for i in self.stack:
            if self.flag  > i:
                self.flag  = i
        return self.flag

执行结果：

执行用时 :
2828 ms, 在所有 Python3 提交中击败了5.02%的用户
内存消耗 :
16 MB, 在所有 Python3 提交中击败了99.88%的用户

8.比较包含退格的两个字符串(复杂度都比较低)

信息

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

示例：

示例 1：

输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：

输入：S = “ab##”, T = “c#d#”
输出：true
解释：S 和 T 都会变成 “”。
示例 3：

输入：S = “a##c”, T = “#a#c”
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：

输入：S = “a#c”, T = “b”
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

答案

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        # 新建两个栈
        stack_a = []
        stack_b = []   
        for i in S:
            if i != '#':
                stack_a.append(i)
            elif i == '#' and stack_a:
                stack_a.pop()
        for i in T:
            if i != '#':
                stack_b.append(i)
            elif i == '#' and stack_b:
                stack_b.pop()
        return stack_a == stack_b

执行结果：
执行用时 :44 ms, 在所有 Python3 提交中击败了96.89%的用户
内存消耗 :13 MB, 在所有 Python3 提交中击败了98.24%的用户

9.判断是否是有效的括号（很巧妙）

信息：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例：

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

答案：

class Solution:
    def isValid(self, s: str) -> bool:
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

10.二叉树的中序遍历（左跟右）

信息

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

答案

 class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
    def __init__(self):
        self.stack = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return self.stack
        if root.left:
            self.inorderTraversal(root.left)
        self.stack.append(root.val)
        if root.right:
            self.inorderTraversal(root.right)
        return self.stack

11.二叉树的前序遍历（根左右）

信息

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

答案

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
    def __init__(self):
        self.stack = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return self.stack
        self.stack.append(root.val)
        if root.left:
            self.preorderTraversal(root.left)
            
        if root.right:
            self.preorderTraversal(root.right)
            
        return self.stack

12.二叉树的后序排列（顺序是：左右根）

信息

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

答案

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
    def __init__(self):
        self.stack = []
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return self.stack
        if root.left:
            self.postorderTraversal(root.left)
        if root.right:
            self.postorderTraversal(root.right)
        self.stack.append(root.val)
        return self.stack

13.使括号有效的最少添加（巧妙）

信息

给定一个由 ‘(’ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(’ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例

示例 1：

输入："())"
输出：1
示例 2：

输入："((("
输出：3
示例 3：

输入："()"
输出：0
示例 4：

输入："()))(("
输出：4

提示：

S.length <= 1000
S 只包含 '(' 和 ')' 字符。

答案

class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        while '()' in S:
            S= S.replace('()','')
        return len(S)

14.二叉搜索树迭代器

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

信息

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示：

next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

答案

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        """
        @return the next smallest number
        """
        
        temp = self.stack.pop()
        res = temp.val
        temp = temp.right
        while temp:
            self.stack.append(temp)
            temp = temp.left
        return res
        
    def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        return self.stack != []

15.扁平化嵌套列表迭代器

信息

给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的项或者为一个整数，或者是另一个列表。

示例：

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,4,6]。

答案

最后

以上就是靓丽苗条为你收集整理的python 栈【测试题】的全部内容，希望文章能够帮你解决python 栈【测试题】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。