首页 > 腾讯PCG一面面经
头像
1024。
编辑于 2021-08-17 11:35
+ 关注

腾讯PCG一面面经

部门介绍
项目介绍
计算机网络八股文
操作系统八股文
算法:左上角到右下角的路有几条?(中间存在障碍)
 private static int findPath(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        if (n == 0 || grid[0][0] == 1) {
            return 0;
        }
        int[][] dp = new int[n][m];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) { // 第一行
            if (grid[0][i] == 1) { // 遇到障碍
                dp[0][i] = 0;
            } else {
                dp[0][i] = dp[0][i - 1];
            }
        }
        for (int i = 1; i < n; i++) { // 第一列
            if (grid[i][0] == 1) { // 遇到障碍
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (grid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[n - 1][m - 1];
    }  
讨论:这个题目是LC还是牛客的题? 有没有大佬给个递归解法???


更多模拟面试

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐