题目
874. 模拟行走机器人
分析
这道题就是个简单的模拟
主要有两点考察点:
- 对方向数组的运用
方向数组存储的是各个方向的单位向量,也即:
方向 | X | Y |
---|---|---|
向北 | 0 | 1 |
向东 | 1 | 0 |
向南 | 0 | -1 |
向西 | -1 | 0 |
存储在数组中,则是方向数组:
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
我们很容易发现:文章来源:https://www.toymoban.com/news/detail-599355.html
dx[0] //北方
dx[1] //东方
dx[2] //南方
dx[3] //西方
我们可以使用一个变量j
来指示当前处于什么方向,j
始终只有0、1、2、3这四个取值,指示北、东、南、西四个方向,那么怎么实现j
在这三个取值之间来回有序切换呢?
我们可以利用去模运算,假设我们初始面向北方,即j
为0,那么当我们想向左转的时候,是面向西方,则j
要相应的变为3,这时,我们进行的操作是(j-1+4)%4
,为什么还要+4
呢?因为负数对正数去模,还是负数,就出了范围,这里我们通过加上一个模数4的倍数,来使结果始终为正数。
因此,我们总结转向操作的实现:文章来源地址https://www.toymoban.com/news/detail-599355.html
j = (j-1+4)%4; // 左转
j = (j+1+4)%4; // 右转
- 怎么实现快速判断当前点是否在障碍物点集中
这里我们可以利用HashSet
把障碍物点以String
字符串的形式存放在HashSet
中。
在Java中,如果您在HashSet
中存放字符串,那么每次调用contains
方法,底层判断两个字符串相等与否时,调用的是equals
方法而不是==
运算符。
这是因为==
运算符比较的是两个对象的引用地址,即它们是否指向同一个内存地址。而String
类重写了equals
方法,比较的是两个字符串的内容是否相等,而不是它们的引用地址。
代码
class Solution {
public int robotSim(int[] commands, int[][] obstacles) {
// 设置方向数组 初始为y轴方向 往大是向右转,往小是向左转
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int cur_x = 0,cur_y = 0; // 当前位置 初始为0
int max_dis = 0; // 最大欧氏距离
// 创建一个障碍物点集
PointSet pointSet = new PointSet(obstacles);
int j = 0; //控制方向 始终在0 1 2 3的范围内
for(int i=0;i<commands.length;i++){
int op = commands[i];
if(op>=1&&op<=9){
int[] point = new int[2]; //下一步试探点
while(op>0){
point[0] = cur_x+dx[j];
point[1] = cur_y+dy[j];
//试探下一步能不能走
if(pointSet.contains(point)) //被建筑物挡住不能走
break;
else{ //能走,则走,且在走的过程中把最大欧氏距离的平方更新
cur_x = cur_x+dx[j];
cur_y = cur_y+dy[j];
max_dis = Math.max(max_dis,cur_x*cur_x+cur_y*cur_y);
}
op--;
}
}
else if(op==-2){
j = (j-1+4)%4; // 左转
continue;
}
else if(op==-1){
j = (j+1+4)%4; // 右转
continue;
}
}
return max_dis;
}
}
//哈希set 高效判断该点是否存在
public class PointSet {
private HashSet<String> pointSet;
// 构造函数 参数是一个二维点集
public PointSet(int[][] points) {
pointSet = new HashSet<>();
// 把点集中的点都加进去
for (int[] point : points) {
pointSet.add(point[0] + "," + point[1]); //以字符串形式存储
}
}
public boolean contains(int[] point) {
return pointSet.contains(point[0] + "," + point[1]);
}
}
到了这里,关于暑期代码每日一练Day3:874. 模拟行走机器人的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!