Airbnb coding test2

有人做过那个airbnb 的coding test2 吗？
由个题是 number of paths in a matrix， 有几个testcase就是过不去？

求做过的人指点下


补充内容 (2017-8-20 05:42):
这个是coding test， 每个人都可以做的

补充内容 (2017-8-20 05:43):
http://redirect.viglink.com/?for ... 5661055772b4297e8ca

补充内容 (2017-8-20 05:49):
链接里的第三题

nirvanagth 发表于 2017-8-20 12:31
请问楼主是用dp做的还是搜索做的？我也有四个case通不过，也没法下载case来看。。。不知道怎么debug

static int numberOfPaths(int[][] a) {
        if(a.length == 0 || a[0].length == 0) return 0;
        
        int[][] res = new int[a.length][a[0].length];
               
        for(int i = 0; i < a.length; i++){
            if(a[i][0] == 0) break;
            res[i][0] = 1;
        }
        
        for(int i = 0; i < a[0].length; i++){
            if(a[0][i] == 0) break;
            res[0][i] = 1;
        }
        
        for(int i = 1; i < a.length; i++){
            for(int j = 1; j < a[0].length; j++){
                if(a[i][j] == 0) res[i][j] = 0;
                else res[i][j] = (res[i-1][j]% 1000000007 + res[i][j-1]% 1000000007)% 1000000007;
            }
        }
        
        return res[a.length - 1][a[0].length - 1] % 1000000007;      
    }

哥，　第三题要module　10^9 + 7

额，这个做了airbnb会联系么？还是就是用来练习下的？

面壁者 发表于 2017-8-20 07:06
额，这个做了airbnb会联系么？还是就是用来练习下的？

只是练习的，之前就有人发过了

面壁者 发表于 2017-8-20 07:06
额，这个做了airbnb会联系么？还是就是用来练习下的？

你做出来了吗？

xxcchh 发表于 2017-8-20 10:30
哥，　第三题要module　10^9 + 7

这是什么意思啊？

补充内容 (2017-8-20 10:38):
我把结果 %1000000007， 还是有case通不过

补充内容 (2017-8-20 10:40):
感谢，解决了

请问楼主是用dp做的还是搜索做的？我也有四个case通不过，也没法下载case来看。。。不知道怎么debug

wxl3691 发表于 2017-8-20 12:53
static int numberOfPaths(int[][] a) {
        if(a.length == 0 || a[0].length == 0) return 0;
   ...

只能用DP， 用dfs会超时， 最后4个case跟溢出，精度有关

wxl3691 发表于 2017-8-20 12:53
static int numberOfPaths(int[][] a) {
        if(a.length == 0 || a[0].length == 0) return 0;
   ...

多谢多谢！