505.迷宫 II#

题目描述#

题目地址 代码

由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。 给定球的起始位置，目的地和迷宫，找出让球停在目的地的最短距离。距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。如果球无法停在目的地，返回  -1。 迷宫由一个 0 和 1 的二维数组表示。 1 表示墙壁，0 表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

提示

可以买卖多次

示例 1#

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出：true
解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。

示例 2#

输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出：false
解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。

限制#

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= startrow, destinationrow <= m
  • 0 <= startcol, destinationcol <= n
  • 球和目的地都在空地上，且初始时它们不在同一位置
  • 迷宫 至少包括 2 块空地

题解#

思路 1：暴力循环#

算法流程：

2 次循环分别找出最大价格和最小价格

复杂度分析：

  • 时间复杂度 O(N^2))
  • 空间复杂度 O(1)

代码#

```go func maxProfit_1(prices []int) int { ans := 0 for i := 0; i < len(prices); i++ { for j := i + 1; j < len(prices); j++ { ans = max(ans, prices[j]-prices[i]) } } return ans } ```

总结#

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：awesome-golang-algorithm

Backward 0501-0600 0700-0799 Forward