Leetcode 每日抑题 (LCP 03. 机器人大冒险)

本贴最后更新于 1276 天前,其中的信息可能已经渤澥桑田

LeetCode 的每日抑题系列 , LeetCode 会每天随机一道题作为签到题.我也是菜鸡,如果今天没 A 掉,那只能证明我离大神又进了一步.

PS: 最近几天的每日抑题都好水,我就不写了,最近的每日抑题是我自己找的中等难度的题,因为比赛的时候中等难度的题都有好多做不出来,困难题就更别说了.

题目链接

题名 通过率 难度
LCP 03. 机器人大冒险 20.4% 中等

力扣团队买了一个可编程机器人,机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令 command,机器人就会无限循环这条指令的步骤进行移动。指令有两种:

U: 向 y 轴正方向移动一格
R: 向 x 轴正方向移动一格。
不幸的是,在 xy 平面上还有一些障碍物,他们的坐标用 obstacles 表示。机器人一旦碰到障碍物就会被损毁。

给定终点坐标(x, y),返回机器人能否完好地到达终点。如果能,返回 true;否则返回 false。

 

示例 1:

输入:command = "URR", obstacles = [], x = 3, y = 2
输出:true
解释:U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。
示例 2:

输入:command = "URR", obstacles = [[2, 2]], x = 3, y = 2
输出:false
解释:机器人在到达终点前会碰到(2, 2)的障碍物。
示例 3:

输入:command = "URR", obstacles = [[4, 2]], x = 3, y = 2
输出:true
解释:到达终点后,再碰到障碍物也不影响返回结果。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/programmable-robot
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

其实蛮简单的题,就是因为数量级的问题导致模拟的方式会出现超时,但是可以简化.

  1. 计算出点可能在第几次循环
  2. 判断这几次的循环是否覆盖障碍点.

java 代码

/**
 * 描述:
 *
 * @author ludengke
 * @create 2020-09-29 11:42
 */
public class LeetCodeLCP03 {
    public boolean robot(String command, int[][] obstacles, int x, int y) {
        /**
         * 用于记录第一个循环的走过的x,y坐标, 以及走过的横向和纵向偏移量
         */
        int[] pointX = new int[command.length()];
        int[] pointY = new int[command.length()];
        int startX = 0, startY = 0, xMax = 0, yMax = 0;
        for (int i = 0; i < command.length(); i++) {
            if (command.charAt(i)=='U'){
                startY += 1;
            }else if(command.charAt(i)=='R'){
                startX += 1;
            }
            pointX[i] = startX;
            pointY[i] = startY;
            xMax = pointX[i] > xMax?pointX[i]:xMax;
            yMax = pointY[i] > yMax?pointY[i]:yMax;
        }
        for (int i = 0; i < obstacles.length; i++) {
            if(obstacles[i][0] <= x && obstacles[i][1] <= y){
                /**
                 * 计算出到达obstacles[i]可能需要几个循环,保险起见上下各加一个
                 * 双层循环判断某点是否在某个循坏上.
                 */
                int num = obstacles[i][0] / xMax;
                for(int k = num-1;k <= num+1;k++){
                    for (int j = 0; j < command.length(); j++) {
                        if(startX * k + pointX[j] == obstacles[i][0] && startY * k + pointY[j] == obstacles[i][1]){
                            return false;
                        }
                    }
                }
            }
        }

        /**
         * 计算出到达终点可能需要几个循环,保险起见上下各加一个
         * 双层循环判断终点是否在某个循坏上, 判断机器人是否能够到达终点
         */
        int num = x / xMax;
        for(int k = num-1;k <= num+1;k++){
            for (int j = 0; j < command.length(); j++) {
                if(startX * k + pointX[j] == x && startY * k + pointY[j] == y){
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        LeetCodeLCP03 l = new LeetCodeLCP03();
//        System.out.println(l.robot());
    }
}

算法 or 数据结构

  1. 模拟
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 每日抑题
    6 引用 • 3 回帖
  • 模拟
    2 引用 • 6 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...