来源leetcode热题HOT100中46,98,105,114,207,337,394

46.全排列

• 题目描述
  • 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
• 示例

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

• 题解：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 深度搜索主程序
        def dfs(nums,size,depth,path,used,res):
            if depth == size:
                res.append(path[:])
                return
            for i in range(size):
                if not used[I]:
                    used[i] = True
                    path.append(nums[I])
                    
                    dfs(nums,size,depth+1,path,used,res)
                    used[i] = False
                    path.pop()
        '''
        depth:表示当前递归到第几层
        为了区分不同阶段，用两个状态变量记录：
        (1)path:已经选了哪些数，到叶节点时，这些数就构成一个全排列
        (2)布尔数组used，初始化为false表示都没有被选择
        '''
        size = len(nums)
        if len(nums) == 0:
            return []
        
        used = [False for _ in range(size)]
        res = []
        dfs(nums,size,0,[],used,res)
        return res

98.验证二叉搜索树

• 题目描述
  • 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
    假设一个二叉搜索树具有如下特征：
    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

• 示例

示例 1:

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

• 题解

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def dfs(node, min_val, max_val):
            if not node:  # 边界条件，如果node为空肯定是二叉搜索树
                return True
            # 如果当前节点超出上下界范围，肯定不是
            if not min_val < node.val < max_val:  
                return False
            # 走到下面这步说明已经满足了如题所述的二叉搜索树的前两个条件
            # 那么只需要递归判断当前节点的左右子树是否同时是二叉搜索树即可
            return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)
        # 对于根节点，它的上下限为无穷大和无穷小
        return dfs(root, float('-inf'), float('inf')) 

105.从前序和中序遍历序列构造二叉树

• 题目描述
  • 根据一棵树的前序遍历与中序遍历构造二叉树。
• 示例

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

• 题解

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

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:  # 递归终止条件
            return
        root = TreeNode(preorder[0])  # 先序为“根左右”，所以根据preorder可以确定root
        idx = inorder.index(preorder[0])  # 中序为“左根右”，根据root可以划分出左右子树
        # 下面递归对root的左右子树求解即可
        root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])
        root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])
        return root

114.二叉树展开为链表

• 题目描述：

  • 给定一个二叉树，将它展开为一个单链表。

• 示例：

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

• 题解：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        while root:
            if root.left:   #左子树存在的话才进行操作
                sub_left = root.left
                while sub_left.right:   #左子树的右子树找到最深
                    sub_left = sub_left.right
                sub_left.right = root.right #将root的右子树挂到左子树的右子树的最深
                root.right = root.left      #将root的左子树挂到右子树
                root.left = None            #将root左子树清空
            root = root.right               #继续下一个节点的操作

207.课程表

• 题目描述：
  • 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
    在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
    给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
• 示例

示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的

• 题解：

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        '''
        有向无圈图DAG，如果构成环路是不成立的
        通过拓扑排序判断是否是DAG：
            对DAG对顶点进行排序，使得每一条有向边(u,v),均符合y比v先出现
        DFS解法
        借助一个列表flags用于判断每个节点的状态：
            未被访问，i==0
            已被其他节点启动的DFS访问，i==-1
            已被当前节点启动的DFS访问，i==1
        对numCourses个节点依次执行DFS，判断是否有环：
            当flags[i]==-1,被其他节点访问过，返回True
            当flags[i]==1,已在本轮搜索中访问过，即有环，返回False
            将当前节点i对应flags[i]置为1，表示本轮访问过
            递归访问当前节点i的所有邻接节点j，发现环返回False
            当前节点的所有邻接节点也被遍历，则当前节点置为-1，返回True
        如果整个图DFS结束都没发现环，返回True
        '''
        def dfs(i,adjacency,flags):
            #终止条件
            if flags[i] == -1:
                return True
            if flags[i] == 1:
                return False
            #当前点置为1
            flags[i] = 1
            #对当前节点对所有邻接点进行dfs
            for j in adjacency[I]:
                if not dfs(j,adjacency,flags):
                    return False
            #没有环则当前节点置为-1，下次不需要再进行dfs了，返回True
            flags[i] = -1
            return True
        #
        adjacency = [[] for _ in range(numCourses)]
        flags = [0 for _ in range(numCourses)]
        for cur,pre in prerequisites:
            adjacency[pre].append(cur)
        #对所有节点进行dfs
        for i in range(numCourses):
            if not dfs(i,adjacency,flags):
                return False
        return True

        '''
        BFS解法：
        统计课程安排图中每个节点的入度，生成入度表indegrees
        借助一个队列queue，将所有入度为0的节点入队
        当queue不为空，依次队首节点出队，在课程安排图中删除此节点pre
            并不是真正从邻接表删除，而是此节点对应所有邻接节点cur-1
            当入度-1后邻接节点cur的入度为0，说明cur的前驱节点已经被删除，此时cur入队
        在每次pre出队时，执行numCourses--
            若课程安排图是DAG，则所有节点都出队入队过
            如图中存在环，则一定有节点的入度始终不为0
            拓扑排序出队次数等于课程个数，返回numCourses==0可以判断是否成功
        '''
        
        #入度表
        indegrees = [0 for _ in range(numCourses)]
        #课程的依赖
        adjacency = [[] for _ in range(numCourses)]
        queue = collections.deque()
        # 入度表记录所有节点的入度，
        for cur,pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        #入度不为0的加入队列
        for i in range(len(indegrees)):
            if not indegrees[I]:
                queue.append(i)
        #BFS
        while queue:
            #取出队首数据
            pre = queue.popleft()
            numCourses -= 1
            #遍历队首的所有邻接元素
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                #如果邻接元素入度-1后还不为0，则将其加入队列
                if not indegrees[cur]:
                    queue.append(cur)
        return numCourses == 0
        

337.打家劫舍三

• 题目描述

  • 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
    计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

• 示例

  
  
  image.png

• 题解

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

class Solution:
    '''
    每一个节点有偷与不偷两种选择：
    每一个节点如果偷的话值为：
        左侧子节点不偷的值 + 右侧子节点不偷的值 + 该节点的值
    每一个节点如果不偷的话值为：
        左侧子节点的最大值 + 右侧子节点的最大值
    '''
    def rob(self,root):
        # a为一个二维数组，为root的[偷值,不偷值]
        a = self.helper(root)
        # 返回两个值的最大值
        return max(a[0],a[1])
    #参数为root节点，返回二维数组，root的[偷值,不偷值]
    def helper(self,root):
        if not root:
            return [0,0]
        left = self.helper(root.left)
        right = self.helper(root.right)
        # root的偷值
        robValue = left[1] + right[1] +root.val
        # root的不偷值
        skipValue = max(left[0],left[1]) + max(right[0],right[1])
        return [robValue,skipValue]

394.字符串解码

• 题目描述

  • 给定一个经过编码的字符串，返回它解码后的字符串。
    编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
    你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
    此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

• 示例

  
  
  image.png

• 题解

  • 题解来源于Krahets

class Solution:
    def decodeString(self, s: str) -> str:
        '''
        辅助栈法
        构建辅助栈stack，遍历字符串s中的每个字符c：
            当c为数字时，将数字字符转换为数字multi
            当c为字母时，在res结尾添加c
            当c为[时，将当前multi和res入栈，并分别置空
                记录此[前当临时结果res入栈，用于发现对应]后的拼接操作
                记录[前的multi入栈，用于发现对应]后，获取multi*[]字符串
            当c为]时，stack出栈，拼接字符串res = last_res + cur_multi*res
                last_res是上个[到当前[的字符串
                cur_multi是当前[到]内字符串的重复次数
        '''
        stack = []
        res = ''
        multi = 0
        for c in s:
            if c == '[':
                stack.append([multi,res])
                res,multi = '',0
            elif c == ']':
                cur_multi,last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                #处理数字不是个位数的情况
                multi = multi*10 + int(c)
            else:
                res += c
        return res