【Java】Leetcode LCP03 机器人大冒险
·
题目:
力扣团队买了一个可编程机器人,机器人初始位置在原点(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)。
思路:
将一次循环后的所有位置嵌入数组
然后通过 helper 函数判断能否到达终点
达到终点前是否会碰到障碍物。
判断逻辑是 是否 有位置减去数组中的值的余数为零,且倍率相等。
是则证明在路径上。
是则返回 true
主函数根据情况进行处理。
class Solution {
public static boolean robot(String command, int[][] obstacles, int x, int y) {
int len = command.length();
int[][] dp = new int[len][2];
int xStep = 0,yStep = 0;
for(int i=0;i<len;i++){
char c = command.charAt(i);
if(c=='R') xStep++;
if(c=='U') yStep++;
dp[i][0] = xStep;
dp[i][1] = yStep;
}
if(!helper(dp,x,y,xStep,yStep)){
return false;
}
for(int[] data:obstacles){
if(data[0]>=x&&data[1]>=y)
continue;
if(helper(dp,data[0],data[1],xStep,yStep)){
return false;
}
}
return true;
}
public static boolean helper(int[][] dp, int x, int y, int xStep, int yStep) {
for(int[] tmp:dp){
if((x-tmp[0])%xStep==0&&(y-tmp[1])%yStep==0&&(x-tmp[0])/xStep==(y-tmp[1])/yStep){
return true;
}
}
return false;
}
}
DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐



所有评论(0)