一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

码农求职神器Triplebyte
不用海投
内推多家公司面试

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 183|回复: 3
收起左侧

[Leetcode] 64Minimum Path Sum 能帮忙看看用Dijkstra不可以吗?

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
ygmm | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (142)
 
 
2% (4)    👎

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

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

x
本帖最后由 ygmm 于 2019-8-23 15:13 编辑

请问这道题是不是不可以用Dijkstra 算法做? 或者能用,但是我的代码错了?
我弄了很久都没找出来问题所在

[Java] 纯文本查看 复制代码
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int V = m * n;  // total count of nodes
        int[][] directions = {{1, 0},{-1, 0},{0, -1},{0, 1}};  
         
        boolean[] settled = new boolean[V];
        int[] distance = new int[V];
        for(int i = 0; i < V; i++){
            distance[i] = Integer.MAX_VALUE;
            settled[i] = false;
        }
        distance[0] = grid[0][0];   // set starting node
        
        for(int vcount = 0; vcount < V; vcount++){
            int index = findmin(distance, settled);
            settled[index] = true;
            
            int i = index / n;
            int j = index % n;
            for(int[] direction : directions){
                int newi = i + direction[0];
                int newj = j + direction[1];
                if(newi < 0 || newj < 0 || newi >= m|| newj >= n){
                    continue;
                }
                int toindex = newi * n + newj;
                if(settled[toindex] == false && distance[index] + grid[newi][newj] < distance[toindex]){
                  distance[toindex] = distance[index] + grid[newi][newj];
                }
            }
        }
            return distance[V-1];
    }[/i][/i]
[i][i]// find node having current minimum path from(0,0)
    private int findmin(int[] distance, boolean[] settled){
        int min = Integer.MAX_VALUE;
        int index = -1;
        for(int i = 0; i < distance.length; i++){
            if(settled[i] == false && distance[i] < min){
                min = distance[i];
                index = i;
            }
        }
        return index;
    }    
}



很多测试用例都能通过,但是有几个不行,结果有出入。 不知道为什么。
测试用例
{{5,4,2,9,6,0,3,5,1,4,9,8,4,9,7,5,1},
{3,4,9,2,9,9,0,9,7,9,4,7,8,4,4,5,8},
{6,1,8,9,8,0,3,7,0,9,8,7,4,9,2,0,1},
{4,0,0,5,1,7,4,7,6,4,1,0,1,0,6,2,8},
{7,2,0,2,9,3,4,7,0,8,9,5,9,0,1,1,0},
{8,2,9,4,9,7,9,3,7,0,3,6,5,3,5,9,6},
{8,9,9,2,6,1,2,5,8,3,7,0,4,9,8,8,8},
{5,8,5,4,1,5,6,6,3,3,1,8,3,9,6,4,8}}

代码算下来是72, 正确是73.

请有兴趣用脑子debug的朋友帮忙看看。。。。我看了很久也没看出来,用debug去跟踪,太长了,实在难以坚持。 这是严格按照Dijkstra算法写的啊。。。也没有负数。。。



上一篇:mental math有什么网站推荐吗
下一篇:只以面试为目的,395 lintcode Coins in a line II这种题目是不是最好直接放弃?
我的人缘0
 楼主| ygmm 2019-8-23 15:17:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (142)
 
 
2% (4)    👎
请有兴趣用肉眼debug的朋友也帮忙看看
回复

使用道具 举报

我的人缘0
步惊云 2019-8-23 23:53:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   87% (623)
 
 
12% (87)    👎
Note: You can only move either down or right at any point in time.

回复

使用道具 举报

我的人缘0
 楼主| ygmm 2019-8-24 08:53:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (142)
 
 
2% (4)    👎
步惊云 发表于 2019-8-23 23:53
Note: You can only move either down or right at any point in time.

谢谢。审题错误,哎
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-9-18 21:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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