算法题目 堆栈（stack）

Posted by SunQH Blog on February 13, 2021

leetcode题目按类型

堆栈stack

✅(20m) 20. 有效的括号

注意: range(x)取不到x

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

有效字符串需满足：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例 1:
输入: "()"
输出: true
示例 2:

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

输入: "(]"
输出: false
示例 4:

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

输入: "{[]}"
输出: true


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# answer
# 主要思想:堆栈stack
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        # The stack to keep track of opening brackets.
        stack = []

        # Hash map for keeping track of mappings. This keeps the code very clean.
        # Also makes adding more types of parenthesis easier
        mapping = {")": "(", "}": "{", "]": "["}

        # For every bracket in the expression.
        for char in s:

            # If the character is an closing bracket
            if char in mapping:

                # Pop the topmost element from the stack, if it is non empty
                # Otherwise assign a dummy value of '#' to the top_element variable
                top_element = stack.pop() if stack else '#'

                # The mapping for the opening bracket in our hash and the top
                # element of the stack don't match, return False
                if mapping[char] != top_element:
                    return False
            else:
                # We have an opening bracket, simply push it onto the stack.
                stack.append(char)

        # In the end, if the stack is empty, then we have a valid expression.
        # The stack won't be empty for cases like ((()
        return not stack

1
2

solution = Solution() # 实例化!!!!!
solution.isValid(s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# try2:
class Solution:
    def isValid(self, s: str) -> bool:
        dec = {  '(': ')',
               '{': '}', 
               '[': ']' }
        s = list(s)
        print(s)
        if len(s) == 0:return True
        if (len(s) % 2) == 1:return False # 奇数个时  

#     def cellpop()
    
        while s:
            for i in range(int(len(s)/2)):  # 注意range(x)取不到x 
                print(i)
                if s[i] in dec:
                    if dec[s[i]] == s[i+1]:
                        s.pop(i+1)
                        s.pop(i)
                        print(('s=',s))
                        break
                    else:pass
            else:
                print('wrong')
                return False
        return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# try1:
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0:return True
        if (len(s) % 2) == 1:return False # 奇数个时      
        left = s[0]
        right_exp = dec[s[0]]
        right_ind = s.index(right_exp)
        if (s.index % 2) == 0:return False 
        else:
            s_cell = s[1:(s.index-1)]
            symbolcell(s_cell)
        print(left,right_exp,right_ind)
    
    def symbolcell(self, s_cell):
        for i in range(len(s_cell)-1):

1

nums1 = [1, 2] nums2 = [3, 4]

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def isValid(self, s: str) -> bool:
        bracket_map = {
            ')':'(',
            '}':'{',
            ']':'['
        }
        stack = []
        for bracket in s:
            if bracket in bracket_map.keys():
                if not stack or stack[-1] != bracket_map[bracket]:
                    return False
                else:
                    stack.pop()
            else:
                stack.append(bracket)
        return True if not stack else False

🚩(0.5h)32. 最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

1
2
3
4
5
6
7
8
9
10

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

栈的例子

栈底： stack=【-1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 栈

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        length = 0
        max_length = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)  # 对于遇到的每个‘(’ ，我们将它的下标放入栈中
            else:   # 如果是’)‘
                stack.pop()  # 弹出栈顶，表示匹配了当前’)‘
                if stack == []:
                    stack.append(i) # 括号结束，记录结束位置(更新「最后一个没有被匹配的右括号的下标」)
                else:  # 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
                    length = i-stack[-1]
                    max_length = max(max_length,length)
            print(i, stack, '  \tmax_length=',max_length)
        return max_length

1
2
3
4
5
6
7

from typing import List

nums = ")()())"
solution = Solution()
result = solution.longestValidParentheses(nums)
result

✅155. 最小栈

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

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

1

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 核心思想: 定义辅助栈helper() 提升查找最小值速度
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.mylist = []
        self.helper = []

    def push(self, x: int) -> None:
        self.mylist.append(x)
        if len(self.helper) == 0 or x <= self.helper[-1]:
            self.helper.append(x)

    def pop(self) -> None:
        top = self.mylist.pop()
        if self.helper and top == self.helper[-1]:
            self.helper.pop()
        return top

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

    def getMin(self) -> int:
        # 注意此处不能是等于 否则会改变一个另一个也会变
        if self.helper:
             return self.helper[-1]
           


# Your MinStack object will be instantiated and called as such:
obj = MinStack()
obj.push(-2)
obj.push(0)
obj.push(-3)
# obj.mylist
# print(obj.getMin())
# obj.pop()
obj.mylist
# print(obj.top())
print((obj.getMin()))

✅ 581. 最短无序连续子数组

注意中括号[]不能随便用,要表示先后关系只能用()

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

1
2
3
4
5
6
7
8
9

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :

输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。

1




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def findUnsortedSubarray(self, nums) -> int:
        nums_sorted = sorted(nums)
        print((nums,nums_sorted))
        if not [(nums > nums_sorted) - (nums < nums_sorted)]:
            return 0  
        else:
            end = 0
            start = 0
            for i in range(len(nums)):
                if nums[i] != nums_sorted[i]:
                    start = i
                    break
            for i in range(1,len(nums)):
                if nums[-i] != nums_sorted[-i]:
                    end = len(nums)-i
                    break

            length = end - start + 1
            return length

    
# nums = [2,6,4,8,9,22,15]
nums = [1,2,3,4]
solution = Solution()
result = solution.findUnsortedSubarray(nums)
result





                

                
                


                
                
                

                    

                

                
                

                
            
  

    
        
            

                

                    
                    

                        CATALOG
                    

                    
    
                
    
            
    
        

    
            
    

                
                



    
    
        
    
    
    FEATURED TAGS
    
    
    
        
        
        
        
        
        
                Paper
        
                summary
        
                job
        
                比赛项目
        
                AI算法
        
                数据结构
        
                C++
        
                算法
        
                Summary
    
    

    


                
                

    

    Other websites