【每日一题】Day0006:CSDN每日一练:不同路径 II

【每日一题】Day0006:CSDN每日一练:不同路径 II,第1张

【每日一题】Day0006:CSDN每日一练:不同路径 II

先放链接:

每日一练-做题 每日一练-做题https://dailycode.csdn.net/practice/1779831昨天发现CSDN上也有每日一练,感觉难度相对力扣简单一些,可能更适合自己现在的状态,颇感兴趣就尝试了一下。今天C/C++这道不同路径II很有意思,做完之后用Java实现并加上注释做为自己的理解和巩固。

代码如下:

package cn.daycode.csdncode;

public class UniquePathsWithObstacles {
    public static void main(String[] args) {
        int[][] grids = {{0,0,0,0,0},{0,1,1,0,0},{0,1,0,0,0},{0,1,0,0,0},{0,0,0,0,0}};
        int row_size = grids.length;
        int col_size = grids[0].length;

        System.out.println(uniquePathsWithObstacles(grids,row_size,col_size));

    }

    public static int uniquePathsWithObstacles(int[][] obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize){
        int row, col;
        int reset = 0;
        
        //根据只能往右走或往下走,如果第0列的某行值为1,则下面的所有值为1(障碍物)
        for (row = 0; row < obstacleGridRowSize; row++){ 
            if (reset == 1){
                obstacleGrid[row][0] = 1;
            }else{
                if (obstacleGrid[row][0] == 1) {
                    reset = 1;
                }
            }
        }
        reset = 0;
        //同理,第0行的某列为1开始,其他列都改为1
        for (col = 0; col < obstacleGridColSize; col++) { 
            if (reset == 1) {
                obstacleGrid[0][col] = 1;
            }else{
                if (obstacleGrid[0][col] == 1) {
                    reset = 1;
                }
            }
        }
        // 将修改后的数组,每一格的1改为0,0改为1,用于计算总路径
        for (row = 0; row < obstacleGridRowSize; row++) { 
            int[] line = obstacleGrid[row];
            for (col = 0; col < obstacleGridColSize; col++) {
                line[col] ^= 1;
            }
        }
        // 将每一格的值改为其左面一格和上面一格之和(从第二列第二行开始)
        for (row = 1; row < obstacleGridRowSize; row++) { 
            int[] last_line = obstacleGrid[row - 1];
            int[] line = obstacleGrid[row];
            for (col = 1; col < obstacleGridColSize; col++) {
                if(line[col] != 0) {
                    line[col] = line[col - 1] + last_line[col];
                }
            }
        }
        // 返回最右下角格最终的值就是最大路径数
        return obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize - 1];
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5672321.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存