leecode刷题笔记（二）

根据不同的解答方法，总结leecode不同题型。

方法二：栈

栈是一种后进先出的数据结构，Last In First Out，简称 LIFO，常常用来实现dfs，或处理被用于数组中不同位置之间含有 嵌套关系 的题目

python实现

一般直接用list

l = []
l.append(i)
j = l.pop()

应用一：嵌套关系

同时，也可以处理嵌套关系 的题目。嵌套关系是指出栈时得到的栈顶元素与当前判断是否入栈元素的关系，以此作为切入点套入计算题目结果所需的俩个元素是涉及栈的关键。例如用单调栈来求右边第一个大于它的元素。

739. 每日温度

难度中等413收藏分享切换为英文关注反馈

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解答：

class Solution(object):
    def dailyTemperatures(self, T):
        num = [0]*len(T)
        stack = []
        
        for n,i in enumerate(T):
            while stack and i>stack[-1][1]:
                a,b = stack.pop()
                num[a] = n-a
            stack.append((n,i))
        return num

总结：

初始化stack，num

在温度内循环

如果温度大于栈顶温度

则栈顶出栈

否则入栈

用单调递减栈来求右边第一大的元素。

list空的话，是false

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

解答：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [(-1,-1)]
        heights.append(-1)
        num = 0
        for n, i in enumerate(heights):
            while i < stack[-1][1]:
                a,b = stack.pop()
                if b*(n-stack[-1][0]-1)>num:
                    num = b*(n-stack[-1][0]-1)
            stack.append((n,i))
        return num

总结：

用单调递增的栈，求得右边第一个比它小的，左边第一个比它小的。

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解答：

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        rain = 0
        
        for i in range(len(height)):
            while stack and height[i]>height[stack[-1]]:
                c = stack.pop()
                if stack:
                    rain += (min(height[stack[-1]],height[i])-height[c])*(i-stack[-1]-1)
            stack.append(i)
        return rain

用单调递减栈来求第一个比它大的元素。

这道题费时较长。

主要思想是每一条的积水，受限于前后两个大于它的元素。

每列积水等于前后两个大于它的元素减它本身再乘距离。

相等的情况不是很好分析。可以试一下不相等。

456. 132模式

难度中等169

给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

注意：n 的值小于15000。

示例:

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

输出: True

解释: 序列中有 1 个132模式的子序列： [1, 4, 2].

解答：

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        if len[nums]<3:
            return False
        
        min_l=nums[0]
        min_list=[]
        n = len(nums)
        for i in range(n):
            if nums[i] < min_l:
                min_l = nums[i]
            min_list.append(min_l)
            
        stack = []
        for i in range(n):
            while stack and nums[n-1-i]>nums[stack[-1]]:
                c = stack.pop()
                if nums[c] > min_list[n-1-i]:
                    return True
            stack.append(n-1-i)
        return False

总结：

本质上是对于一个中间元素j，找左边最小元素i，右边小于次元素最大元素是否大于左边最小元素。

实际上就是先找个list，判断左边最小元素。然后从后往前找个单调栈，每次出栈的时候，都判断对应的是否大于对应左边最小元素。

735. 行星碰撞

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 ：

输入: 
asteroids = [5, 10, -5]
输出: [5, 10]
解释: 
10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。

解答：

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        a = 0
        a=1
        while asteroids and min(asteroids)*max(asteroids)<0:
            a = 0
            for i in range(len(asteroids)-1):
                if asteroids[i]>0 and asteroids[i+1]<0:
                    if asteroids[i]>0:
                        if asteroids[i]>-asteroids[i+1]:
                            asteroids.pop(i+1)
                            a=1
                            break
                        elif asteroids[i]==-asteroids[i+1]:
                            asteroids.pop(i)
                            asteroids.pop(i)
                            a=1
                            break
                        else:
                            asteroids.pop(i)
                            a=1
                            break
                    else:
                        if -asteroids[i]>asteroids[i+1]:
                            asteroids.pop(i+1)
                            a=1
                            break
                        elif -asteroids[i]==asteroids[i+1]:
                            asteroids.pop(i)
                            asteroids.pop(i)
                            a=1
                            break
                        else:
                            asteroids.pop(i+1)
                            a=1
                            break
            if a==0:
                break
        return asteroids

解法2：

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for i in asteroids:
            while stack and stack[-1]>0 and i<0:
                if abs(stack[-1]) < abs(i):
                    stack.pop()
                elif abs(stack[-1]) == abs(i):
                    stack.pop()
                    break
                else:
                    break
            else:
                stack.append(i)
        return stack

应用二：DFS

队列经常用在图的深度优先搜索（DFS）中，深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。正如树的遍历中所提到的，我们可以用 DFS 进行 前序遍历，中序遍历 和 后序遍历。在这三个遍历顺序中有一个共同的特性：除非我们到达最深的结点，否则我们永远不会回溯。

133. 克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

解答：

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        lookup = {}

        def dfs(node):
            #print(node.val)
            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)

总结：

建立字典收集已经复制过的节点

建立节点，并且对节点的每一个邻居，采取dfs

剑指 Offer 12. 矩阵中的路径

难度中等95

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b“,”c”,”e”],
[“s”,”f“,”c“,”s”],
[“a”,”d”,”e“,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

解答：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        try:
            m=len(board)
            n=len(board[0])
            k=len(word)
            around=((0,1),(1,0),(0,-1),(-1,0))
        except:
            return False
        
        def dfs(i,j,a):
            if len(a)==k:
                return True
            for a1,a2 in around:
                a1+=i;a2+=j
                if 0<=a1<m and 0<=a2<n and (a1,a2) not in a and board[a1][a2]==word[len(a)]:
                    a.append((a1,a2))
                    if dfs(a1,a2,a):
                        return True
                    a.pop()
            return False

        for i in range(m):
            for j in range(n):
                if board[i][j]==word[0]:
                    a=[]
                    a.append((i,j))
                    if dfs(i,j,a):
                        return True
        return False

总结：因为要判断，所以每次dfs走到头的话，返回的是一个true就可以

剑指 Offer 13. 机器人的运动范围

难度中等116

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

解答：

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def canget(i,j):
            n = 0
            i=str(i);j=str(j)
            for i1 in i:
                n = int(i1) + n 
            for j1 in j:
                n = int(j1) + n
            return n <= k

        around = ((0,1),(1,0),(0,-1),(-1,0))
        num=1      
        l = []
        visit=set()
        l.append((0,0))
        while l:
            a,b = l.pop()
            visit.add((a,b))
            for i,j in around:
                i+=a;j+=b
                if 0<=i<m and 0<=j<n and canget(i,j) and (i,j) not in l and (i,j) not in visit:
                    l.append((i,j))
            
        return len(visit)

总结：因为要计算路径，所以每次出栈一个，都要加入visit来计数。其余技巧和bfs相似

总结

例如单调递减栈，

• 初始化stack
• 循环元素
  • 对于大于的元素，进行循环
    • 出栈
    • 计算相应的性质。
  • 对于小于的元素，入栈

赏

谢谢你请我吃糖果