目录
一、乘积最大数组
1.1 具体思路
1.2 思路展示
1.3 代码实现
1.4 复杂度分析
1.5 运行结果
二、乘积为正数的最长子数组长度
2.1 具体思路
2.2 思路展示
2.3 代码实现
2.4 复杂度分析
2.5 运行结果
三、迷宫中离入口最近的出口
3.1 具体思路
3.2 思路展示
3.3 代码实现
3.4 运行结果
四、访问所有节点的最短路径
4.1 思路一：动态规划
4.2 思路二：状态压缩
新年快乐
一、乘积最大数组
力扣第152题
本题采用动态规划的思想解决
1.1 具体思路
（1）首先定义状态：
使用两个状态数组 dp_min 和 dp_max，其中 dp_min[i]表示以 nums[i]结尾的子
数组中乘积最小的值，dp_max[i]表示以 nums[i]结尾的子数组中乘积最大的值。
（2）确定状态转移方程：
当 nums[i]为正数时，dp_max[i] = max(dp_max[i-1]*nums[i], nums[i]), dp_min[i]
= min(dp_min[i-1]*nums[i], nums[i])；
当 nums[i]为负数时，dp_max[i] = max(dp_min[i-1]*nums[i], nums[i]), dp_min[i] =
min(dp_max[i-1]*nums[i], nums[i])；
当 nums[i]为 0 时，dp_max[i] = dp_min[i] = 0。
（3）得到最终结果：
遍历完整个数组后，最大乘积即为 dp_max 数组中的最大值。
1.2 思路展示
初始状态：
dp_min = [0, 0, 0, 0]
dp_max = [0, 0, 0, 0]
遍历数组进行状态转移：
对于第一个元素 2：
dp_min[0] = dp_max[0] = 2
对于第二个元素 3：
由于 3 为正数，所以更新状态：
dp_max[1] = max(dp_max[0] * 3, 3) = max(2 * 3, 3) = 6
dp_min[1] = min(dp_min[0] * 3, 3) = min(2 * 3, 3) = 3
对于第三个元素 -2：
由于 -2 为负数，所以更新状态：
dp_max[2] = max(dp_min[1] * (-2), -2) = max(3 * (-2), -2) = -2
dp_min[2] = min(dp_max[1] * (-2), -2) = min(6 * (-2), -2) = -12
对于第四个元素 4：
由于 4 为正数，所以更新状态：
dp_max[3] = max(dp_max[2] * 4, 4) = max((-2) * 4, 4) = 4
dp_min[3] = min(dp_min[2] * 4, 4) = min((-12) * 4, 4) = -48
最终，dp_max 数组中的最大值为 6，即为最大乘积。
1.3 代码实现
1. def maxProduct(nums):
2. n = len(nums)
3. if n == 0:
4. return 0
5. dp_min = [0] * n
6.
dp_max = [0] * n
7.
dp_min[0] = dp_max[0] = nums[0]
8.
for i in range(1, n):
9.
if nums[i] >= 0:10.
dp_max[i] = max(dp_max[i - 1] * nums[i], nums[i])
11.
dp_min[i] = min(dp_min[i - 1] * nums[i], nums[i])
12.
else:
13.
dp_max[i] = max(dp_min[i - 1] * nums[i], nums[i])
14.
dp_min[i] = min(dp_max[i - 1] * nums[i], nums[i])
15. return max(dp_max)
16.
17.
18. # 测试用例 1
19. nums1 = [2, 3, -2, 4]
20. print(maxProduct(nums1)) # 输出: 6
21.
22. # 测试用例 2
23. nums2 = [-2, 0, -1]
24. print(maxProduct(nums2)) # 输出: 0
1.4 复杂度分析
时间复杂度分析：
遍历数组的时间复杂度为 O(n)，其中 n 是数组的长度。
在每个位置，进行状态转移的操作时间复杂度为 O(1)。 因此，总体的时间复杂
度为 O(n)。
空间复杂度分析：
我们使用了两个辅助数组 dp_min 和 dp_max 来记录状态。
这两个数组的长度与输入数组 nums 的长度相同，因此空间复杂度为 O(n)。
综上所述，该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。
1.5 运行结果
两个测试用例如下
# 测试用例 1
nums1 = [2, 3, -2, 4]
# 测试用例 2
nums2 = [-2, 0, -1]
二、乘积为正数的最长子数组长度
力扣第1567题
本题依旧采用动态规划的思想
2.1 具体思路
首先，我们需要定义两个状态数组 dp_max 和 dp_min，分别用于记录以当前位
置为结尾的乘积最大值和乘积最小值。
然后，我们遍历数组 nums，对于每个元素，我们根据其正负性来更新状态数组：
如果当前元素是正数，则乘积最大值为前一个位置的乘积最大值乘以当前元素或
者只包含当前元素，即 dp_max[i] = max(dp_max[i-1]*nums[i], nums[i])；
如果当前元素是负数，则乘积最大值为前一个位置的乘积最小值乘以当前元素或
者只包含当前元素，即 dp_max[i] = max(dp_min[i-1]*nums[i], nums[i])；
同时，我们还需要考虑到乘积为正数的子数组长度要求，因此我们设置一个变量
max_len 来保存乘积为正数的子数组的最大长度。每次更新乘积最大值的时候，
我们也更新 max_len。
最后，返回 max_len 即可。
2.2 思路展示
假设我们有以下输入数组 nums：
nums = [1, -2, -3, 4]首先，我们初始化两个状态数组 dp_max 和 dp_min，长度与 nums 数组相同，
初始值都为 0。
dp_max = [0, 0, 0, 0]
dp_min = [0, 0, 0, 0]
接下来，我们遍历数组 nums，对于每个元素，根据其正负性来更新状态数组
dp_max 和 dp_min。
对于第一个元素 1，它是正数，所以乘积最大值和乘积最小值都只包含当前元素1。
dp_max = [1, 0, 0, 0]
dp_min = [1, 0, 0, 0]
对于第二个元素 -2，它是负数，所以乘积最大值应该是前一个位置的乘积最小
值乘以当前元素或者只包含当前元素 -2。乘积最小值应该是前一个位置的乘积
最大值乘以当前元素或者只包含当前元素 -2。
dp_max = [1, -2, 2, 0]
dp_min = [1, -2, -2, 0]
对于第三个元素 -3，它是负数，同样地，乘积最大值应该是前一个位置的乘积
最小值乘以当前元素或者只包含当前元素 -3。乘积最小值应该是前一个位置的
乘积最大值乘以当前元素或者只包含当前元素 -3。
dp_max = [1, -2, 2, 6]
dp_min = [1, -2, -2, -6]
对于最后一个元素 4，它是正数，所以乘积最大值和乘积最小值都应该是前一个
位置的乘积最大值乘以当前元素或者只包含当前元素 4。
dp_max = [1, -2, 2, 6]
dp_min = [1, -2, -2, -6]
在更新状态数组 dp_max 的同时，我们还需要记录乘积为正数的子数组的最大
长度 max_len。在这个例子中，最大长度为 4。
最后，返回 max_len。
2.3 代码实现
def getMaxLen(nums):
2. n = len(nums)
3. if n == 0:
4. return 0
5. 6. dp_max = [0] * n
7. dp_min = [0] * n
8. dp_max[0] = dp_min[0] = 1 if nums[0] > 0 else 0
9. max_len = dp_max[0]
10. 11. for i in range(1, n):
12. if nums[i] > 0:
13. dp_max[i] = max(dp_max[i - 1] * nums[i], nums[i])
14. dp_min[i] = min(dp_min[i - 1] * nums[i], nums[i])
15. elif nums[i] < 0:
16. dp_max[i] = max(dp_min[i - 1] * nums[i], nums[i])
17. dp_min[i] = min(dp_max[i - 1] * nums[i], nums[i])
18. 19. if dp_max[i] > 0:
20. max_len = max(max_len, i + 1)
21. 22. return max_len
23. # 示例 1
24. nums1 = [1,-2,-3,4]
25. print(getMaxLen(nums1)) # 输出: 4
26. 27. # 示例 2
28. nums2 = [-1,-2,-3,0,1]
29. print(getMaxLen(nums2)) # 输出: 3
2.4 复杂度分析
假设输入数组的长度为 n。
时间复杂度分析：
初始化两个长度为 n 的状态数组 dp_max 和 dp_min，时间复杂度为 O(n)。
使用循环遍历数组，每次更新 dp_max 和 dp_min 的值，时间复杂度为 O(n)。
在循环中比较并更新最大长度 max_len，时间复杂度为 O(1)。 所以，总的时间
复杂度为 O(n)。
空间复杂度分析：
使用了两个长度为 n 的状态数组 dp_max 和 dp_min，额外空间复杂度为 O(n)。
使用了常量空间存储其他变量，空间复杂度为 O(1)。 所以，总的空间复杂度为
O(n)。
综上所述，代码的时间复杂度为 O(n)，空间复杂度为 O(n)。
2.5 运行结果
# 示例 1
nums1 = [1,-2,-3,4]
# 示例 2
nums2 = [-1,-2,-3,0,1]
与预期结果一致
三、迷宫中离入口最近的出口
力扣第1926题
本题采用 BFS 的思想求解
3.1 具体思路
定义一个队列 queue，用于存储待遍历的节点。初始时，将入口 entrance 加入
队列中。
定义一个二维数组 directions，表示四个方向的移动：上、下、左、右。
定义一个二维数组 visited，用于记录每个格子是否被访问过。初始时，所有格
子都未被访问过。
定义一个变量 steps，用于记录从入口到当前节点的步数。
进行 BFS 遍历：
当队列不为空时，进行以下操作：
弹出队列中的节点，并将其坐标保存到变量 cur 中。
检查 cur 是否位于迷宫的边界上，如果是，则返回 steps 作为最短路径的步数。
遍历四个方向：
计算下一个节点的坐标 next_x 和 next_y。
检查 next_x 和 next_y 是否越界，或者迷宫中的格子已经被访问过，如果是，
则跳过当前方向。
将 next_x 和 next_y 添加到队列中，并将 visited[next_x][next_y] 设置为 True。
增加步数 steps。如果遍历结束后仍未找到边界上的出口，则返回 -1。
3.2 思路展示
假设现在有一个迷宫如下图所示，其中 "S" 表示入口，"E" 表示出口，"." 表示
可以通行的路径，"+" 表示障碍物。
我们可以从入口开始，按照 BFS 的方式一层一层地遍历迷宫，并标记每个节点
是否被访问过。具体步骤如下：
将入口加入队列中，初始步数为 0。
弹出队列中的第一个节点 "S"，并将其标记为已访问。
在四个方向上寻找可通行的路径：
向上走，发现上面有障碍物，跳过该方向；
向下走，发现下面是一个空地，将其加入队列中，并标记为已访问；
向左走，发现左边是一个墙壁，跳过该方向；
向右走，发现右边是一条路径，将其加入队列中，并标记为已访问。
此时队列中有两个节点，分别为下方的节点和右方的节点。我们按照先进先出的
原则，先弹出下方的节点。并将其标记为已访问。
继续在四个方向上寻找可通行的路径：
向上走，发现上面是一个墙壁，跳过该方向；
向下走，发现下面也是一个空地，将其加入队列中，并标记为已访问；
向左走，发现左边是一条路径，将其加入队列中，并标记为已访问；
向右走，发现右边也是一条路径，将其加入队列中，并标记为已访问。
此时队列中有三个节点，分别为右下方的节点、下方的节点和右方的节点。我们
按照先进先出的原则，先弹出右下方的节点。并将其标记为已访问。
继续在四个方向上寻找可通行的路径：
向上走，发现上面是一个墙壁，跳过该方向；
向下走，发现下面也是一条路径，将其加入队列中，并标记为已访问；
向左走，发现左边也是一条路径，将其加入队列中，并标记为已访问；
向右走，发现右边也是一条路径，将其加入队列中，并标记为已访问。
此时队列中有三个节点，分别为下方的节点、右方的节点和右下方的节点。我们
按照先进先出的原则，先弹出下方的节点。并将其标记为已访问。
继续在四个方向上寻找可通行的路径：
向上走，发现上面也是一条路径，将其加入队列中，并标记为已访问；
向下走，发现下面是一个墙壁，跳过该方向；
向左走，发现左边也是一条路径，将其加入队列中，并标记为已访问；
向右走，发现右边也是一条路径，将其加入队列中，并标记为已访问。
此时队列中有两个节点，分别为右方的节点和右下方的节点。我们按照先进先出的原则，先弹出右方的节点。并将其标记为已访问。
继续在四个方向上寻找可通行的路径：
向上走，发现上面也是一条路径，将其加入队列中，并标记为已访问；
向下走，发现下面也是一条路径，将其加入队列中，并标记为已访问；
向左走，发现左边也是一条路径，将其加入队列中，并标记为已访问；
向右走，发现右边是出口 "E"，返回当前步数 2，即为最短路径的步数。
从上面的示意图可以看出，BFS 的过程就是按层遍历节点，寻找可通行的路径，
直到找到目标节点为止。这样可以保证我们找到的路径一定是最短的。
3.3 代码实现
from collections import deque
2.
3.
4. def nearestExit(maze, entrance):
5. m, n = len(maze), len(maze[0])
6. directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
7. visited = [[False] * n for _ in range(m)]
8.
9. queue = deque()
10. queue.append((*entrance, 0))
11. visited[entrance[0]][entrance[1]] = True
12.
13. while queue:
14. x, y, steps = queue.popleft()
15.
16. if x == 0 or x == m - 1 or y == 0 or y == n - 1:
17. return steps
18.
19. for dx, dy in directions:
20. next_x, next_y = x + dx, y + dy
21.
22. if (
23. next_x < 0
24. or next_x >= m
25. or next_y < 0
26. or next_y >= n
27. or maze[next_x][next_y] == "+" 28. or visited[next_x][next_y]
29. ):
30. continue
31.
32. queue.append((next_x, next_y, steps + 1))
33. visited[next_x][next_y] = True
34.
35. return -1
36.
37.
38. # 示例测试
39. maze1 = [["+", "+", ".", "+"], [".", ".", ".", "+"], ["+", "+", "+", "+"]]
40. entrance1 = [1, 2]
41. print(nearestExit(maze1, entrance1)) # 输出：1
42.
43. maze2 = [["+", "+", "+"], [".", ".", "."], ["+", "+", "+", "+"]]
44. entrance2 = [1, 0]
45. print(nearestExit(maze2, entrance2)) # 输出：2
3.4 运行结果
两个示例如下：
四、访问所有节点的最短路径
力扣第847题
4.1 思路一：动态规划
（1）具体思路
我们可以用一个二维的 DP 数组 dp[state][i] 来表示从节点 i 出发，经过状态
state（用二进制位表示已经访问过的节点），访问所有节点的最短路径长度。
首先，我们需要初始化 DP 数组。对于任意的节点 i，初始状态下只访问过节点
i，其他节点都未访问过，所以 dp[1< 然后，我们开始状态转移。对于每个状态 state，我们遍历所有的节点 i，如果节 点 i 在状态 state 中已经被访问过，则跳过。然后，对于节点 i 的相邻节点 j， 在当前状态 state 上更新 dp[state|(1< 1)，表示从节点 i 经过边 (i, j) 到达节点 j，并将节点 j 加入到新的状态中。 最后，我们需要找到从任意一个节点出发，访问所有节点的最短路径长度。遍历 所有的起点 i，更新答案为 min(ans, dp[(1< （2）代码实现 1. from typing import List 2. 3. 4. class Solution: 5. def shortestPathLength(self, graph: List[List[int]]) -> int: 6. n = len(graph) 7. INF = float('inf') 8. dp = [[INF] * n for _ in range(1 << n)] 9. 10. # 初始化 DP 数组 11. for i in range(n): 12. dp[1 << i][i] = 0 13. 14. # 状态转移 15. for state in range(1 << n): 16. repeat = True 17. while repeat: 18. repeat = False 19. for i in range(n): 20. if not (state & (1 << i)): 21. continue 22. for j in graph[i]: 23. new_state = state | (1 << j) 24. if dp[state][i] + 1 < dp[new_state][j]: 25. dp[new_state][j] = dp[state][i] + 1 26. if new_state != state: 27. repeat = True 28. 29. # 搜索所有起点，得到最短路径长度 30. ans = INF 31. for i in range(n): 32. ans = min(ans, dp[(1 << n) - 1][i]) 33. return ans 34. 35. 36. if __name__ == '__main__': 37. s = Solution() 38. graph1 = [[1, 2, 3], [0], [0], [0]] 39. print(s.shortestPathLength(graph1)) # expected output: 4 40. 41. graph2 = [[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]] 42. print(s.shortestPathLength(graph2)) # expected output: 4 （3）复杂度分析 初始化 DP 数组：时间复杂度为 O(n^2)，其中 n 是图中节点的数量。 状态转移：外层循环的状态总数是 2^n，内层循环的时间复杂度最坏情况下为 O(n^2)（每个节点都与其他节点相邻），因此总的时间复杂度为 O(2^n * n^3)。 搜索所有起点：时间复杂度为 O(n)。 整体的时间复杂度为 O(2^n * n^3)。 空间复杂度上，DP 数组占用的空间为 O(2^n * n)，因此总的空间复杂度为 O(2^n * n)。 4.2 思路二：状态压缩 注：状态压缩思想与动态规划思路两者相连度很高 （1）具体思路 具体来说，我们可以将每个节点表示为二进制数的一位，这样就可以使用二进制 数来表示所有节点是否访问过。 假设当前访问的节点为 i，已经访问过的节点集合为 visited，我们可以枚举下一 个要访问的节点 j，如果 j 还没有被访问过，则可以从 i 节点到达 j 节点，此 时需要更新 visited 集合，并计算从 j 出发访问所有未访问节点的最短路径长度。 因为节点数量不超过 12，所以可以使用状态压缩 DP 的方式解决该问题。具体 来说，我们可以定义状态 dp[i][visited] 表示从节点 i 出发，已经访问过的节点 集合为 visited 的情况下，访问所有未访问节点的最短路径长度。初始状态为 dp[i][2^i] = 0，表示从节点 i 出发，只访问过 i 节点，其他节点都未访问的情况 下，路径长度为 0。 状态转移方程为： dp[i][visited] = min(dp[i][visited], dp[j][visited|(1< 其中，dis(i, j) 表示从节点 i 到节点 j 的距离，visited|(1< 的 visited 集合，表示从 i 节点到达 j 节点后，可以访问的节点集合。 dp[j][visited|(1< 的最短路径长度。 最终的答案为 min{dp[i][(1< 的最短路径长度。 （2）代码实现 1. class Solution: 2. def shortestPathLength(self, graph: List[List[int]]) -> int: 3. n = len(graph) 4. INF = 0x3f3f3f3f 5. # 初始化状态转移数组 6. dp = [[INF] * (1 << n) for _ in range(n)] 7. for i in range(n): 8. dp[i][1 << i] = 0 9. 10. # 枚举所有状态 11. for s in range(1 << n): 12. for i in range(n): 13. if s & (1 << i): 14. # 当前状态已经包含了节点 i，枚举下一个节点 j 15. for j in graph[i]: 16. if not (s & (1 << j)): 17. # 下一个节点 j 还没有被包含在当前状态中 18. # 更新状态转移方程 19. dp[j][s | (1 << j)] = min(dp[j][s | (1 << j)], dp[i][s] + 1) 20. 21. # 搜索所有起点，得到最终答案 22. ans = INF 23. for i in range(n): 24. ans = min(ans, dp[i][(1 << n) - 1]) 25. return ans （3）运行结果 结果与预期结果一致 新年快乐 推荐链接
您阅读本篇文章共花了：
发表评论