温州做网站建设多少钱千锋教育课程

题目

874. 模拟行走机器人

---

分析

这道题就是个简单的模拟
主要有两点考察点：

• 对方向数组的运用
  方向数组存储的是各个方向的单位向量，也即：

方向	X	Y
向北	0	1
向东	1	0
向南	0	-1
向西	-1	0

存储在数组中，则是方向数组：

int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};

我们很容易发现：

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的倍数，来使结果始终为正数。
因此，我们总结转向操作的实现：

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; // 当前位置 初始为0int 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]);}
}

---