力扣面试题08.02.:迷路的机器人(可回溯、可动态规划)

一、题目内容

       力扣面试题08.02.:迷路的机器人(可回溯、可动态规划)

 二、题目分析

        机器人从左上角开始运动,每次只可以向右或者向下运动,不可以经过障碍物,到达右下角为成功。

        那我们从(0,0)点开始,分别向右向下运动,如果运动的坐标超出的边界或者碰到障碍物或者坐标被访问过,就返回,如果是正常可访问的坐标,就将它放到数组中去,并且给它标记为已访问。

        接下来我们需要判断,当前访问的点是否是右下角的点,如果是,就结束一切操作,否则继续向下个坐标进发。

class Solution {
    boolean flag=false; 
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
         int m=obstacleGrid.length;
    int n=obstacleGrid[0].length;
        boolean [][]visited=new boolean[m][n];
        List<List<Integer>> list=new ArrayList<>();
        backtrack(list,0,0,obstacleGrid,visited);
        return list;
    }
    public void backtrack(List<List<Integer>> list,int i,int j,int [][]obstacleGrid,boolean[][]visited)
    {
        if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1||visited[i][j])
        {
            return;
        }
        list.add(Arrays.asList(i, j));
         visited[i][j]=true;
       
        if((i==obstacleGrid.length-1)&&(j==obstacleGrid[0].length-1))
            flag=true;
        if(flag==false)
            backtrack(list,i+1,j,obstacleGrid,visited);
        if(flag==false)
            backtrack(list,i,j+1,obstacleGrid,visited);
        if(flag==false)
            list.remove(list.size()-1);
    }
}

        这部分是未经优化的代码,可以看到我用了大量的额外空间去标记它的访问情况,但是其实访问过的点可以直接将它设置为1,也就是看做障碍物,这样也可以达到不重复访问的效果。

        还有一点就是,我重复的使用了诸如obstacleGrid.length之类复杂的语句,可以将它们直接定义为类的属性,简化代码。

         另外还有一点需要提一下,在下面这句判断中

 if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1)
        {
            return;
        }

     obstacleGrid[i][j]==1这句一定要写在最后面,因为前面的语句只要有一个正确,就会直接进入底下的return,不会执行  obstacleGrid[i][j]==1。但是如果将它放在第一个,可能i,j下标越界而错误。

          最后就是为什么最后要写三个if语句,而不是将这三个语句写到一个if里。因为第一个

backtrack(list,i+1,j,obstacleGrid,visited);

 执行完之后,可能已经访问到最后一个点了,flag为true,可以直接退出了,但是如果写在一个if里,那么上面的程序执行完之后,还需要继续执行,显然有问题。

底下是简化后的代码:

class Solution {
    boolean flag=false; 
    int m,n;
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        m=obstacleGrid.length;
        n=obstacleGrid[0].length;
        backtrack(0,0,obstacleGrid);
        return list;
    }
    public void backtrack(int i,int j,int [][]obstacleGrid)
    {
        if(i>=obstacleGrid.length||j>=obstacleGrid[0].length||i<0||j<0||obstacleGrid[i][j]==1){
            return;
        }
        list.add(Arrays.asList(i, j));
        obstacleGrid[i][j]=1;       
        if((i==m-1)&&(j==n-1))
            flag=true;
        if(flag==false)
            backtrack(i+1,j,obstacleGrid);
        if(flag==false)
            backtrack(i,j+1,obstacleGrid);
        if(flag==false)
            list.remove(list.size()-1);
    }
}

        力扣面试题08.02.:迷路的机器人(可回溯、可动态规划)

        这个题目我已经全都在原数组操作了,但是内存消耗还是很大, 可以试试用动态规划做,先判断起点到终点是否可达,再倒序求路径。

(这部分非原创)
class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> res;
        int rows = obstacleGrid.size();
        int cols = obstacleGrid[0].size();
        // 先排除边缘情况,起点和重点不可达
        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows-1][cols-1] ==1)
        {
            return res;
        }

        // 初始化
        bool d[rows][cols];
        memset(d, 0, sizeof(bool)*rows*cols);
        d[0][0] = 1;
        // 首列
        for (int i = 1; i < rows; ++i)
        {
            d[i][0] = (obstacleGrid[i][0] == 0) && d[i-1][0];
        }
        // 首行
        for (int j = 1; j < cols; ++j)
        {
            d[0][j] = (obstacleGrid[0][j] == 0) && d[0][j-1];
        }

        // 计算
        for (int i = 1; i < rows; ++i)
        {
            for (int j = 1; j < cols; ++j)
            {
                // 这里把两种情况都合并在一起了
                // 先判断是否为0
                // 再判断上一次位置是否可达
                d[i][j] = (obstacleGrid[i][j] == 0) && (d[i-1][j] || d[i][j-1]);
            }
        }

        // 结果
        // 如果不可达,直接返回空结果
        if (!d[rows-1][cols-1])
        {
            return res;
        }
        // 可达,倒序计算
        int i = rows-1;
        int j = cols-1;
        while (i > 0 || j > 0)
        {
            // cout << i << "," << j << endl;
            res.push_back({i, j});
            // 判断上一步是上方的情况是否可达
            if (i > 0 && d[i-1][j])
            {
                --i;
            }
            else
            {
                // 因为最后是可达,所以这里必然有一个可达的, 考虑上一步是左边的情况
                --j;
            }
        }
        // 插入起点
        res.push_back({0,0});
        // 倒序
        reverse(res.begin(), res.end());
        return res;
    }
};

        

力扣面试题08.02.:迷路的机器人(可回溯、可动态规划)

 三、感言

        动态规划几天没写,怎么手生了呢? ctmd....

上一篇:C# 中判断DBNull?


下一篇:postgres获取普通的操作所影响的行数