算法修炼：深度遍历

深度优先搜索是一种用于遍历或搜索树或图形数据结构的算法，该算法从根节点开始（在图形的情况下，选择一些任意节点作为根节点），并在回溯之前尽可能沿着每个分支进行探索。因此，基本思想是从根节点或任意节点开始，标记该节点，接着移至相邻的未标记节点，然后继续此循环，直到没有未标记的相邻节点为止。最后回溯并检查其他未标记的节点并遍历它们。

采用深度优先搜索解题的要点：

1. 设置初始条件；
2. 利用变量防止循环或者已经遍历过的节点；
3. 确定下一个阶段需要遍历的节点。

深度优先搜索的应用

深度优先搜索（DFS）是用于遍历图形的算法（或技术）。使用DFS可以解决很多问题：

1. 对于加权图，图的深度优先遍历将生成最小生成树和所有对最短路径树。可参考https://leetcode.com/problems/path-sum/。
2. 检测图中的周期，当且仅当在深度优先搜索期间看到后边缘时，图形才会循环。因此，可以为图形运行深度优先搜索并检查后边缘。请参考Error! Hyperlink reference not valid.https://leetcode.com/ problems/graph-valid-tree/。
3. 寻路。可以专门使用深度优先搜索算法寻找两个给定顶点u和z之间路径。

• 以u为起始顶点调用DFS（G，u）。
• 使用堆栈S跟踪起始顶点和当前顶点之间的路径。
• 一旦遇到目标顶点z，则将路径返回为堆栈内容。

4. 拓扑排序。拓扑排序主要用于根据作业之间的给定依赖性来调度作业，在计算机科学中，这种类型的应用出现在指令调度，重新计算电子表格中的公式值时，公式单元格评估顺序、逻辑综合，确定要在makefile中执行的编译任务的顺序，数据序列化以及解析链接器中的符号依存关系。请参考https://leetcode.com/problems/ course-schedule/。
5. 测试图是否为二部图。当第一次发现一个新顶点时，可以对BFS或DFS进行增强，对它的对应边进行着色，对于彼此的边，检查它是否不链接相同颜色的两个顶点。任何连接的组件中的第一个顶点可以是红色或黑色！请参考https://leetcode. com/problems/is-graph-bipartite/。
6. 迷宫问题。通过仅在访问集中的当前路径上包含节点，DFS可以适用于找到迷宫的所有解决方案。请参考https://leetcode.com/ problems/the-maze-ii/。

实例1: 太平洋大西洋水流

示例： 给定一个m×n的非负整数矩阵，表示一个大陆中每个单位单元的高度，“太平洋”触及矩阵的左边缘和上边缘，而“大西洋”触及右边缘和下边缘。

水只能从四个单元（向上、向下、向左或向右）从一个单元流向另一个高度等于或更低的单元。查找水流向太平洋和大西洋的网格坐标列表。

思路： 这道题目如果使用深度遍历的话，可以从太平洋接触的上边缘和左边缘的点出发，看看能到达哪些点，另外，同时从大西洋接触的右边缘和下边缘出发，看看能到达哪些点。

基于深度遍历的算法

class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        if not matrix or not matrix[0]:
            return []
        R, C = len(matrix), len(matrix[0])
        pacific, atlantic = set(), set()
        def dfs(r, c, seen):
            if (r, c) in seen:
                return
            seen.add((r, c))
            for nr, nc in ((r, c+1), (r, c-1), (r+1, c), (r-1, c)):
                # 下一个点要高于当前点
                if 0 <= nr < R and 0 <= nc < C and matrix[nr][nc] >= matrix[r][c]:
                    dfs(nr, nc, seen)
        for r, c in [(r, 0) for r in range(R)] + [(0, c) for c in range(C)]:
            dfs(r, c, pacific)
        for r, c in [(r, C-1) for r in range(R)] + [(R-1, c) for c in range(C)]:
            dfs(r, c, atlantic)
        return pacific & atlantic 

实例2: 预测获胜者

给定分数数组，这些分数是非负整数。玩家1从数组的任一端选择一个数字，接着玩家2，然后是玩家1，依此类推。每当玩家选择一个号码时，该号码将不可用于下一个玩家。继续进行直到选择了所有分数为止，得分最高的玩家获胜。

输入：[1、5、2]
输出：错误

说明： 最初，玩家1可以在1和2之间选择。如果他选择2（或1），则玩家2可以从1（或2）和5中选择。如果玩家2选择5，则玩家1将剩下1（或2）。因此，玩家1的最终得分为1 + 2 = 3，而玩家2为5。因此，玩家1永远不会是赢家，最后需要返回False。

思路： 这种问题一般是利用minmax的方法求解，就是说对于第一个玩家来说，如果取第一个，对于第二个人，他可以取剩下的第一个或最后一个，因此对于第一个人来说就加上剩下数组中较小的一个。

图 15 1 第一个玩家取走第一个元素所能获得的最大分数值。

当然，第一个玩家也可以取最后一个，第二个玩家就在数组剩余的元素中，要么取其中第一个或者最后一个，就要加上数组剩余较小的一个元素。

预测获胜者

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        sum = 0
        for num in nums:
            sum+=num
        first = self.dfs(nums,0,len(nums)-1)
        second = sum-first
        return first>=second
    def dfs(self,nums:List[int],s:int,e:int) ->int:
        if s > e:return 0
        start = nums[s]+min(self.dfs(nums,s+1,e-1),self.dfs(nums,s+2,e))
        end = nums[e]+min(self.dfs(nums,s+1,e-1),self.dfs(nums,s,e-2))
        return max(start,end)
        

实例3: 表达式加运算符

给定一个仅包含数字0-9和目标值的字符串，返回所有在数字之间添加二进制运算符（非一元）+，-或*的所有可能性，以便通过运算符得到目标值。

范例1：
输入：num =“ 123”，目标= 6
输出：[“ 1 + 2 + 3”，“ 1 * 2 * 3”]
范例2：
输入：num =“ 232”，目标= 8
输出：[“ 2 * 3 + 2”，“ 2 + 3 * 2”]
范例3：
输入：num =“ 105”，目标= 5
输出：[“ 1 * 0 + 5”，“ 10-5”]

思路：以范例1为例，利用深度遍历的方式。需要注意的是，如果遇到乘法，需要把以前的数字减掉，乘上当前的数字，前一个数字需要保存下来。另外，还要注意，选取的下一个数字第一位不能为零。

表达式运算符

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        res = []
        self.target = target
        
        for i in range(1, len(num) + 1):
            if i==1 or (i>1 and num[0] != '0'):
                self.dfs(num[i:], num[:i], int(num[:i]), int(num[:i]), res)
        return res
    
    def dfs(self, num, fstr, fval, flast, res):
        # fstr = string of current formula
        # fval = value of current formula
        # flast = last value for +- and last computing result for * in formula. 
        # For example, if fstr=2+3, then flast=3, if fstr=2-3, then flast=-3, if fstr=2+3*4, then flast=3*4=12
        if not num:
            if fval == self.target:
                res.append(fstr)
            return
        
        for i in range(1, len(num)+1):
            val=num[:i]
            if i == 1 or (i>1 and num[0] != '0'):
                self.dfs(num[i:], fstr + '+' + val, fval + int(val), int(val), res)
                self.dfs(num[i:], fstr + '-' + val, fval - int(val), -int(val), res)
                self.dfs(num[i:], fstr + '*' + val, fval-flast+flast*int(val), flast*int(val), res)

《硅谷Python工程师面试指南》

点击上图了解及购买

推荐语：本书是一本全面的Python技术及面试指南，旨在帮助读者深入理解Python编程语言的核心概念，并掌握在技术面试中取得成功的关键技巧。