查看: 1163|回复: 31
收起左侧

[Leetcode] 求助一道路径的问题

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (22)
 
 
8% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
给一个 n*n 的方格, 从左上起点到右下终点,返回出一条起点到终点的路径(可以不一定是最短),如果没有的话那么就返回None,
每个小格子上面有一个数字,移动的时候只能往小于等于自己的格子走,可以上下左右移动。
input:
grid1 = [[4,3,5],
[2,3,3],
[2,2,1]
]
output:
[4,3,3,2,1] 或者 [4,2,2,2,1] 或 [4,3,3,2,2,,2,1]

我用bfs 写的无法返回这样的结果,请教下大家怎么写这个题的代码,我可以学习下。希望大家发个正确的代码,谢谢啦
下面是我写的,但是结果不太对,感觉是把上面答案给混合了。

  1. ## (0,0) is source, (n-1, n-1) is target
  2. import collections
  3. def findPath(grid):
  4.         n = len(grid)
  5.         seen = set()
  6.         dirs = [(-1,0), (1,0), (0,1), (0,-1)]
  7.         res = []
  8.         queue = collections.deque()
  9.         queue.append((0,0))
  10.         res.append(grid[0][0])
  11.         while queue:
  12.                 i,j = queue.popleft()
  13.                 for x,y in dirs:
  14.                         new_i = x + i
  15.                         new_j = y + j
  16.                         if new_i<0 or new_i>=n or new_j<0 or new_j>=n or grid[new_i][new_j] > grid[i][j]:
  17.                                 continue
  18.                         if (new_i, new_j) in seen:
  19.                                 continue
  20.                         # print((new_i,new_j))
  21.                         # print(grid[new_i][new_j])
  22.                         res.append(grid[new_i][new_j])
  23.                         if new_i==n-1 and new_j == n-1:
  24.                                 return res
  25.                         seen.add((new_i, new_j))
  26.                         queue.append((new_i, new_j))
  27.         return None
复制代码







评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:微软近期高频面试题分享 + 分析(十一)
下一篇:弱问leetcode 98. Validate Binary Search Tree
thrillerの空 2021-7-21 14:15:40 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
本帖最后由 thrillerの空 于 2021-7-21 14:23 编辑

题主代码有误的地方主要是这里的逻辑没有理清:


  1.             # print((new_i,new_j))
  2.             # print(grid[new_i][new_j])
  3.             res.append(grid[new_i][new_j])
  4.             if new_i==n-1 and new_j == n-1:
  5.                 return res
  6.             seen.add((new_i, new_j))
  7.             queue.append((new_i, new_j))
复制代码



代码执行到这里,表示什么呢?意味着我们可以走到这个新位置(new_i,new_j),及不越界,也满足现在的数字小于等于之前走过的数字。那么,后续我们需要干什么呢?如果是一般的BFS,我们需要把当前位置的所有相邻位置全部打入queue中,但是这里需要么?答案是不需要的,只要我们能前进一部,无论是什么地方,我们就不需要再看其他相邻的位置了,所以题主的代码需要重构一下:


  1. # yes, append the position to the path,
  2. # as well as in the seen, and the queue
  3. res.append(grid[new_i][new_j])
  4. seen.add((new_i, new_j))
  5. queue.append((new_i, new_j))

  6. # at this point, we went to the next position
  7. # if reached the end position, return the res path
  8. if new_i == n - 1 and new_j == n - 1:
  9.     return res
  10. # else, no need to look at other neighbours
  11. else:
  12.     break
复制代码



我已经加上了注释,题主可以根据上面的例子在自己过一遍代码哦,最后附上完整代码:

  1. ## (0,0) is source, (n-1, n-1) is targetimport collections

  2. def isGoing(new_i, new_j, n, grid, i, j ):
  3.     return new_i < 0 or new_i >= n or new_j < 0 or new_j >= n or grid[new_i][new_j] > grid[i][j]

  4. def findPath(grid):
  5.     n = len(grid)
  6.     seen = set()
  7.     dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
  8.     res = []
  9.     queue = collections.deque()
  10.     queue.append((0, 0))
  11.     res.append(grid[0][0])

  12.     while queue:
  13.         i, j = queue.popleft()

  14.         # see if we can go to the four directions?
  15.         for x, y in dirs:
  16.             new_i = x + i
  17.             new_j = y + j

  18.             # No for two cases:
  19.             # 1. out of index or the current number > the previous one
  20.             if isGoing( new_i, new_j, n, grid, i, j ):
  21.                 continue
  22.             # 2. have seen this position before
  23.             if (new_i, new_j) in seen:
  24.                 continue

  25.             # yes, append the position to the path,
  26.             # as well as in the seen, and the queue
  27.             res.append(grid[new_i][new_j])
  28.             seen.add((new_i, new_j))
  29.             queue.append((new_i, new_j))

  30.             # at this point, we went to the next position
  31.             # if reached the end position, return the res path
  32.             if new_i == n - 1 and new_j == n - 1:
  33.                 return res
  34.             # else, no need to look at other neighbours
  35.             else:
  36.                 break
  37.     return None


  38. grid = [[4, 3, 5],
  39.         [2, 3, 3],
  40.         [2, 2, 1]]
  41. print(findPath(grid))
  42. [i]
复制代码


另外,如果要求所有可能的路径,用楼上的DFS可能要简单一点哦,BFS不是很好写,至于这个思路,楼上已经用java给出答案了哦。
最后,拓展一下哒,如果要追求效率,这一题应该可以用动态规划,和机器人走格子的题目很像,只是这里有更多的限制条件:

1. 不能走更大的数字;
2. 可以上下左右;

但是这些都可以在O(1)之内完成,所以最后的时间复杂度和机器人的题目是一样的哦。 先说到这里哒,有什么问题欢迎追问哒~




补充内容 (2021-07-21 15:53 +8:00):
写的有问题,大家看另外一个童鞋的解答就好哦,又不能覆盖,希望不要误人子弟e

补充内容 (2021-07-21 17:25 +8:00):
别点赞了,别点赞了,人都要傻啦

补充内容 (2021-07-21 17:26 +8:00):
这道题需要更快的效率,可以看成图,如果非负,Dijkstra算法,O(m+n)线性时间就能解决,如果有负数,Bellman Ford,O(n^2)平方时间内就能解决。两种情况都比DFS要好太多哦。

评分

参与人数 1大米 +10 收起 理由
14417335 + 10

查看全部评分

回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   78% (334)
 
 
21% (89)    👎
thrillerの空 发表于 2021-07-21 21:33:47
你的分析思路有点问题哦,无论是一条,还是穷举所有条,都是必须遍历所有的路径,只是一条只要我们找到一条就结束算法,穷举需要全遍历,但是一条下最坏还是得全遍历。比如,我们假象下面这个极端情况,也就是除了终
没仔细看代码,但是最中间的1走过一次发现走不通就不用再走了呀
回复

使用道具 举报

nullas 2021-7-22 18:29:51 来自APP | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (122)
 
 
0% (0)    👎
在bfs的时候,用一个n*n matrix 记录每个节点的上一个节点。然后从终点开始就找上一个节点,就能重构出一条路径。

评分

参与人数 1大米 +1 收起 理由
银河系搞钱指南 + 1 赞一个

查看全部评分

回复

使用道具 举报

abcd12344 2021-7-21 13:07:00 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
可以参考leetcode 675


补充内容 (2021-07-21 13:12 +08:00):
抱歉,又看了一下和675不太一样

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

abcd12344 2021-7-21 13:46:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
本帖最后由 abcd12344 于 2021-7-21 02:43 编辑

这样可以返回所有结果,如果只要一个的话稍微改一下就行。
  1. import java.util.ArrayList;
  2. import java.util.HashSet;
  3. import java.util.List;
  4. import java.util.Set;

  5. public class FindPath {
  6.     static List<Integer> curr;
  7.     static List<List<Integer>> ans;
  8.     public static void main(String[] args) {
  9.         List<List<Integer>> r = findPath(new int[][]{{4, 3, 5},{2, 3, 3},{2, 2, 1}});
  10.         for(List<Integer> l : r){
  11.             System.out.println(l);
  12.         }
  13.     }

  14.     public static List<List<Integer>> findPath(int[][] grid){
  15.         curr = new ArrayList<>();
  16.         ans = new ArrayList<>();
  17.         curr.add(grid[0][0]);
  18.         backtrack(grid, new HashSet<>(), 0, 0);
  19.         return ans;
  20.     }
  21.     public static void backtrack(int[][] grid, Set<Integer> seen, int x, int y){
  22.         // if you jsut need to return one path, update this line and the ans list
  23.         //  if(ans != null) return;
  24.         int m = grid.length;
  25.         int n = grid[0].length;
  26.         if(x == m - 1 && y == n - 1) {
  27.             ans.add(new ArrayList<>(curr));
  28.             return;
  29.         }
  30.         int[][] Dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  31.         for(int[] dir: Dirs){
  32.             int nextX = x + dir[0];
  33.             int nextY = y + dir[1];
  34.             if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n &&
  35.                     !seen.contains(nextX * m + nextY) && grid[nextX][nextY] <= grid[x][y]){
  36.                 seen.add(x * m + y);                curr.add(grid[nextX][nextY]);
  37.                 backtrack(grid, seen, nextX, nextY);
  38.                 curr.remove(curr.size() - 1);
  39.                 seen.remove(x * m + y);
  40.             }
  41.         }
  42.     }
  43. }
复制代码



评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分

回复

使用道具 举报

abcd12344 2021-7-21 14:53:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
thrillerの空 发表于 2021-7-21 02:15
题主代码有误的地方主要是这里的逻辑没有理清:

[mw_shl_code=python,true]

抱歉,没看懂您说的只走一个邻居。有没有可能这个邻居后面是死路呢?这样这条路就没办法走下去,最后只能返回空。
回复

使用道具 举报

abcd12344 2021-7-21 14:57:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
另外贴一个用bfs的方法帮助楼主理解。因为bfs保存路径比较难,我用了一个新的class来保存路径。
  1. import java.util.*;

  2. public class FindPath2 {
  3.     public static void main(String[] args) {
  4.         List<Integer> l= findPath(new int[][]{{4, 3, 5},
  5.                                                     {2, 3, 3},
  6.                                                     {2, 2, 1}});
  7.             System.out.println(l);
  8.     }
  9.     static class Node{
  10.         public Node prev;
  11.         public int x, y, val;
  12.         public Node(Node prev, int x, int y, int val){
  13.             this.prev = prev;
  14.             this.x = x;
  15.             this.y = y;
  16.             this.val = val;
  17.         }
  18.     }

  19.     public static List<Integer> findPath(int[][] grid){
  20.         int[][] Dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  21.         int m = grid.length;
  22.         int n = grid[0].length;
  23.         Node start = new Node(null, 0, 0 , grid[0][0]);
  24.         Queue<Node> queue = new LinkedList<>();
  25.         Set<Integer> seen = new HashSet<>();
  26.         queue.offer(start);
  27.         while(!queue.isEmpty()){
  28.             Node currNode = queue.poll();
  29.             if(currNode.x == m - 1 && currNode.y == n - 1){
  30.                 //found ont path
  31.                 return(printPath(currNode));
  32.             }
  33.             seen.add(currNode.x * m + currNode.y);
  34.             for(int[] dir: Dirs){
  35.                 int nextX = currNode.x + dir[0];
  36.                 int nextY = currNode.y + dir[1];
  37.                 if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n &&
  38.                         grid[nextX][nextY] <= currNode.val &&
  39.                         !seen.contains(nextX * m + nextY)){
  40.                     queue.offer(new Node(currNode, nextX, nextY, grid[nextX][nextY]));
  41.                 }
  42.             }
  43.         }
  44.         return new ArrayList<>();
  45.     }
  46.     public static List<Integer> printPath(Node tail){
  47.         List<Integer> list = new ArrayList<>();
  48.         Node curr = tail;
  49.         while (curr != null){
  50.             list.add(curr.val);
  51.             curr = curr.prev;
  52.         }
  53.         Collections.reverse(list);
  54.         return list;
  55.     }
  56. }
复制代码

评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分

回复

使用道具 举报

thrillerの空 2021-7-21 15:52:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
abcd12344 发表于 2021-7-21 14:53
抱歉,没看懂您说的只走一个邻居。有没有可能这个邻居后面是死路呢?这样这条路就没办法走下去,最后只能 ...

哎呀,搞错了,那我说的有问题哦,还是看你的好了,用BFS没有太好的办法,不好意思哦
回复

使用道具 举报

thrillerの空 2021-7-21 16:01:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
本帖最后由 thrillerの空 于 2021-7-21 16:03 编辑
abcd12344 发表于 2021-7-21 14:53
抱歉,没看懂您说的只走一个邻居。有没有可能这个邻居后面是死路呢?这样这条路就没办法走下去,最后只能 ...

你看看能不能把点赞取消哦,现在不能覆盖答案,影响不太好哦。我去关注题主代码为什么又多余的数字,没有注意dead end 的情况,太失误了哦
回复

使用道具 举报

thrillerの空 2021-7-21 17:25:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
本帖最后由 thrillerの空 于 2021-7-21 17:28 编辑
abcd12344 发表于 2021-7-21 14:57
另外贴一个用bfs的方法帮助楼主理解。因为bfs保存路径比较难,我用了一个新的class来保存路径。
[mw_shl_c ...

后面想了想,这道题用DFS最简单,BFS要复杂一些,但是这两个方法的时间复杂度都不太行,应该是O( (n^2)! ),因为最坏情况我们要搜索所有的路径一次,也就是所有数字的排列组合,一共n ^ 2 个数字,那么组合最多就是(n^2)!。
而且这题用动态规划也没不太行,因为关系式写出来,会有当前项取决于未知项的问题。那么如果需要更快的解决这个问题,需要把这个二维数组转换成图来做,这样就可以把这个题目转换成图的最短路径问题,依据给的条件,如果数组都是非负,Dijkstra算法,O(m+n)线性时间就能解决,如果有负数,Bellman Ford算法,O(n^2)平方时间内就能解决。两种情况都比DFS要好太多哦。

图的转换方法如下图所示:




本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分

回复

使用道具 举报

abcd12344 2021-7-22 04:18:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
thrillerの空 发表于 2021-7-21 05:25
后面想了想,这道题用DFS最简单,BFS要复杂一些,但是这两个方法的时间复杂度都不太行,应该是O( (n^2)!  ...

如果只返回一个路径的话,不应该是O(N^2)吗?因为每个点最多只走一遍。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表