Loading...
墨滴

algolearn

2021/09/26  阅读:24  主题:默认主题

存储结构 - 栈 stack

1 概述

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为先进后出表。

栈:后入先出

2 实现

在 LIFO 数据结构中,将首先处理添加到队列中的最新元素。

与队列不同,栈是一个 LIFO 数据结构。通常,插入操作在栈中被称作入栈 push 。与队列类似,总是在堆栈的末尾添加一个新元素。但是,删除操作,退栈 pop ,将始终删除队列中相对于它的最后一个元素。

#%%
class Mystack:
    def __init__(self, capacity):
        self.data = []
        self.capacity = capacity

    def push(self, elem):
        if len(self.data) < self.capacity:
            self.data.append(elem)
        else:
            raise IndexError('栈满了')

    def pop(self):
        if len(self.data) > 0:
            return self.data.pop(-1)
        else:
            raise IndexError('栈空了')

    def is_full(self):
        return len(self.data) == self.capacity

s = Mystack(3)
s.push(1)
s.push(2)
s.push(3)
print(s.pop())
print(s.is_full())

2.1 最小栈 155

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

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。
class MinStack(object):
    def __init__(self):
        self.stack = []
        self.min = None
    
    def push(self, x):
        self.stack.append(x)
        if self.min == None or x < self.min:
            self.min = x
    
    def pop(self):
        x = self.stack.pop(-1)
        if len(self.stack) == 0:
            self.min = None
            return x
        if x == self.min:
            self.min = self.stack[0]
            for i in self.stack:
                if i < self.min:
                    self.min = i
        return x
    
    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min

2.3 有效的括号

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

class Solution(object):
    def isValid(self, s):
        stack = []
        for i in s:
            if i == '{':
                stack.append('}')
            elif i == '(':
                stack.append(')')
            elif i == '[':
                stack.append(']')
            elif len(stack) == 0 or stack.pop(-1) != i:
                return False
        return len(stack) == 0

2.4 每日温度 739

请根据每日 气温 列表 temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """

        days = len(temperatures)
        if days == 1:
            return [0]
        stack = []
        res = [0] * days
        for i in range(days):
            while len(stack) > 0 and temperatures[stack[-1]] < temperatures[i]:
                index = stack.pop(-1)
                res[index] = i - index
            stack.append(i)
        return res

2.5 逆波兰表达式求值 150

根据 逆波兰表示法,求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

class Solution:
    def evalRPN(self, tokens):
        stack = []
        for i in tokens:
            if i not in ["+""-""*""/"]:
                stack.append(int(i))
            else:
                b, a = stack.pop(), stack.pop()
                if i == "+":
                    c = a + b
                elif i == "-":
                    c = a - b
                elif i == "*":
                    c = a * b
                elif i == "/":
                    c = a //b
                    c = c + 1 if c < 0 and a % b != 0 else c
                stack.append(c)
        return stack[0]  

3 栈与深度优先搜索 DFS

DFS常用模板

/*
 * 模板1: Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

/*
 * 模板2: Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

3.1 岛屿数量 200

# BFS
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        row = len(grid)
        col = len(grid[0])
        neighbors = [(-10), (10), (0-1), (01)]
        num_islands = 0
        for i in range(row):
            for j in range(col):
                search_list = deque()
                if grid[i][j] == '1':
                    search_list.append((i, j))
                    num_islands += 1
                    while search_list:
                        d_row, d_col = search_list.popleft()
                        for x, y in neighbors:
                            neighbor_row = d_row + x
                            neighbor_col = d_col + y
                            if 0 <= neighbor_row < row and 0 <= neighbor_col < col and grid[neighbor_row][neighbor_col] == '1':
                                grid[neighbor_row][neighbor_col] = '0'
                                search_list.append([neighbor_row, neighbor_col])
        return num_islands

# DFS
class Solution:
    def numIslands(self, grid):
        row, col = len(grid), len(grid[0])
        neighbors = [[10], [-10], [01], [0-1]]
        def dfs(i, j):
            grid[i][j] = '0'
            for x, y in neighbors:
                i_, j_ = i + x, j + y
                if 0 <= i_ < row and 0 <= j_ < col and grid[i_][j_] == '1':
                    dfs(i_, j_)
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    dfs(i, j)
                    res += 1
        return res

3.2 克隆图 133

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""


class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """

        lookup = {}
        def dfs(node):
            if not node: 
                return
            if node in lookup:
                return lookup[node]
            clone = Node(node.val, [])
            lookup[node] = clone
            for n in node.neighbors:
                clone.neighbors.append(dfs(n))
            return clone
        return dfs(node)

3.3 目标和 494

  • 利用dfs深度优先搜索
  • 设置一个哈希表(字典),键是一个元祖,元祖第一位是目前的位数,第二位是目前的和。值是这个元祖推导到最后能有多少个解。
  • 例如d[(4,5)] = 1 代表读到4位的时候,正好有一个解符合条件(那么在这个例子中符合条件的S就是5),然后倒导d([3,5]) = 2 ......(在这种情况下,第4位是0,总共就4位)
  • 初始化节点为(0,0),代表已经读了0位,现在和为0
  • 开始深度优先搜索,当i比位数小,说明可以深入。为了避免重复运算,要看当前节点是否在d里已经出现过。
  • 每次深入的结果,就是d[(i, cur)] = dfs(cur + nums[i], i + 1, d) + dfs(cur - nums[i], i + 1, d)。意思就是当前节点推导到最后有多少个可能性呢?这个节点再读取一位,要么是加上这一位,要么是减掉这一位,所以这个节点的可能性就是对加上下一位的可能性与减掉下一位的可能性之和。
  • 当深入到最后一位时,再深入就超了位数限制了,此时可以直接判断这个节点的和(即元祖的第二位)是否等于需要的S。是了为1,否则为0。因为dfs可能遍历到重复节点,所以return一行写作d.get((i, cur), int(cur == S))。如果是重复节点直接返回字典里对应值就完事儿(ง •̀_•́)ง
class Solution:
    def findTargetSumWays(self, nums, S):
        d = {}
        def dfs(cur, i, d):
            if i < len(nums) and (cur, i) not in d: # 搜索周围节点
                d[(cur, i)] = dfs(cur + nums[i], i + 1, d) + dfs(cur - nums[i],i + 1, d)
            return d.get((cur, i), int(cur == S))   
        return dfs(00, d)

3.4 二叉树的中序遍历 94

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root):
        res = []
        stack = []
        while stack or root:
            # 不断往左子树方向走,每走一次就将当前节点保存到栈中
            # 这是模拟递归的调用
            if root:
                stack.append(root)
                root = root.left
            # 当前节点为空,说明左边走到头了,从栈中弹出节点并保存
            # 然后转向右边节点,继续上面整个过程
            else:
                tmp = stack.pop()
                res.append(tmp.val)
                root = tmp.right
        return res

欢迎关注微信公众号(算法工程师面试那些事儿),建号初期,期待和大家一起刷leecode,刷机器学习、深度学习面试题等,共勉~

算法工程师面试那些事儿
算法工程师面试那些事儿

algolearn

2021/09/26  阅读:24  主题:默认主题

作者介绍

algolearn