Leetcode每日一题 —— 874. 模拟行走机器人
- 内容介绍
- 文章标签
- 相关推荐
874. 模拟行走机器人 - 力扣（LeetCode）
874. 模拟行走机器人 - 机器人在一个无限大小的 XY 网格平面上行走，从点(0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ： * -2 ：向左转90 度 * -1 ：向右转 90 度 * 1 <= x <= 9 ：向前移动x个单位长度 在网格上有一些格子被视为障碍物obstacles 。第 i个障碍物位于网格点 obstacles[i] = (xi, yi)...
思路
可以发现每一步最多只会走 9 步，因此模拟完全是 OK 滴 ദ്ദി(˵ •̀ ᴗ - ˵ ) ✧。用哈希表标记障碍物后逐步判断是否与障碍物相撞即可。
注意左转和右转时的坐标变换，左转和右转都会交换 X 和 Y 方向上的行进增量，区别在于左转后 X 方向增量取负、右转是 Y 方向增量取负。
如果这题每次走的步数可以很大，那就麻烦了，可能涉及到二分，在范围内查询点。
代码
238. 除了自身以外数组的乘积 - 力扣（LeetCode） 136. 只出现一次的数字 - 力扣（LeetCode）class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
// 模拟题
// 先把障碍物加入哈希表
unordered_map<int,unordered_map<int,bool>> oMap;
for(auto& ob:obstacles){
oMap[ob[0]][ob[1]]=true;
}
// 前进时可能被障碍物阻断，每步最多只能走九步其实挺好办，不然涉及二分查询点是否在范围中
int deltaX=0, deltaY=1;
int currX=0,currY=0;
int res=0;
for(int c:commands){
switch(c){
case -2:
// 左旋 90°
swap(deltaX,deltaY);
deltaX=-deltaX;
break;
case -1:
swap(deltaX,deltaY);
deltaY=-deltaY;
break;
default:
for(int i=0;i<c;i++){
int newX=currX+deltaX;
int newY=currY+deltaY;
if(oMap[newX][newY]){
// 此处有障碍物，不能继续前进
break;
}
currX=newX;
currY=newY;
}
res=max(res,currX*currX+currY*currY);
}
}
return res;
}
};
继续写一些 Hot100
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// 一个非常好想的思路就是前后缀
int n=nums.size();
vector<int> prefix(n),postfix(n);
prefix[0]=nums[0];
postfix[n-1]=nums[n-1];
for(int i=1;i<n;i++){
prefix[i]=nums[i]*prefix[i-1];
postfix[n-1-i]=nums[n-1-i]*postfix[n-i];
}
vector<int> res(n);
res[0]=postfix[1];
res[n-1]=prefix[n-2];
for(int i=1;i<n-1;i++){
res[i]=postfix[i+1]*prefix[i-1];
}
return res;
}
};
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 只能用常量额外空间
// 这种时候就得考虑一些数学性质了
// 两个相同的数异或为 0，因为其余元素均出现两次
// 所有数字异或后的结果就是只出现了一次的
int res=nums[0];
for(int i=1;i<nums.size();i++){
res^=nums[i];
}
return res;
}
};
--【壹】--：
膜拜OIer佬
--【贰】--：
- 优化了编码方式（那个unsigned int转换真的坑）
- set → unordered_set
class Solution {
public:
long long encode(int x, int y) {
return ((long long)x << 32) | (unsigned int)y;
}
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int ans = 0;
int x = 0, y = 0;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dir = 0;
unordered_set<long long> st;
for (const auto& ob : obstacles) {
st.insert(encode(ob[0], ob[1]));
}
for (int com : commands) {
if (com == -1) {
dir = (dir + 1) % 4;
} else if (com == -2) {
dir = (dir + 3) % 4;
} else {
for (int i = 0; i < com; i++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (st.count(encode(nx, ny))) break;
x = nx;
y = ny;
ans = max(ans, x * x + y * y);
}
}
}
return ans;
}
};
--【叁】--：
每日一题学习
--【肆】--：
模拟模拟
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
set<int> s;
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
int id_dir = 0;
int X = 0,Y = 0;
int res = 0;
for(const auto& it: obstacles) {
int val = it[0] * 6e4 + it[1];
s.insert(val);
}
auto jud_obs = [&](int x,int y) -> bool {
if(x > 3e4 || x < -3e4 || y > 3e4 || y < -3e4) {
return false;
}
int val = x * 6e4 + y;
if(s.find(val) != s.end()) {
return true;
}
return false;
};
for(const auto& it : commands) {
if(it == -2) {
id_dir = (id_dir - 1 + 4) % 4;
} else if(it == -1) {
id_dir = (id_dir + 1) % 4;
} else {
for(int i = 0; i < it; i++) {
int next_X = X + dx[id_dir];
int next_Y = Y + dy[id_dir];
if(jud_obs(next_X,next_Y)) {
break;
}
X = next_X;
Y = next_Y;
}
res = max(res,X * X + Y * Y);
}
}
return res;
}
};
874. 模拟行走机器人 - 力扣（LeetCode）
874. 模拟行走机器人 - 机器人在一个无限大小的 XY 网格平面上行走，从点(0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ： * -2 ：向左转90 度 * -1 ：向右转 90 度 * 1 <= x <= 9 ：向前移动x个单位长度 在网格上有一些格子被视为障碍物obstacles 。第 i个障碍物位于网格点 obstacles[i] = (xi, yi)...
思路
可以发现每一步最多只会走 9 步，因此模拟完全是 OK 滴 ദ്ദി(˵ •̀ ᴗ - ˵ ) ✧。用哈希表标记障碍物后逐步判断是否与障碍物相撞即可。
注意左转和右转时的坐标变换，左转和右转都会交换 X 和 Y 方向上的行进增量，区别在于左转后 X 方向增量取负、右转是 Y 方向增量取负。
如果这题每次走的步数可以很大，那就麻烦了，可能涉及到二分，在范围内查询点。
代码
238. 除了自身以外数组的乘积 - 力扣（LeetCode） 136. 只出现一次的数字 - 力扣（LeetCode）class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
// 模拟题
// 先把障碍物加入哈希表
unordered_map<int,unordered_map<int,bool>> oMap;
for(auto& ob:obstacles){
oMap[ob[0]][ob[1]]=true;
}
// 前进时可能被障碍物阻断，每步最多只能走九步其实挺好办，不然涉及二分查询点是否在范围中
int deltaX=0, deltaY=1;
int currX=0,currY=0;
int res=0;
for(int c:commands){
switch(c){
case -2:
// 左旋 90°
swap(deltaX,deltaY);
deltaX=-deltaX;
break;
case -1:
swap(deltaX,deltaY);
deltaY=-deltaY;
break;
default:
for(int i=0;i<c;i++){
int newX=currX+deltaX;
int newY=currY+deltaY;
if(oMap[newX][newY]){
// 此处有障碍物，不能继续前进
break;
}
currX=newX;
currY=newY;
}
res=max(res,currX*currX+currY*currY);
}
}
return res;
}
};
继续写一些 Hot100
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// 一个非常好想的思路就是前后缀
int n=nums.size();
vector<int> prefix(n),postfix(n);
prefix[0]=nums[0];
postfix[n-1]=nums[n-1];
for(int i=1;i<n;i++){
prefix[i]=nums[i]*prefix[i-1];
postfix[n-1-i]=nums[n-1-i]*postfix[n-i];
}
vector<int> res(n);
res[0]=postfix[1];
res[n-1]=prefix[n-2];
for(int i=1;i<n-1;i++){
res[i]=postfix[i+1]*prefix[i-1];
}
return res;
}
};
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 只能用常量额外空间
// 这种时候就得考虑一些数学性质了
// 两个相同的数异或为 0，因为其余元素均出现两次
// 所有数字异或后的结果就是只出现了一次的
int res=nums[0];
for(int i=1;i<nums.size();i++){
res^=nums[i];
}
return res;
}
};
--【壹】--：
膜拜OIer佬
--【贰】--：
- 优化了编码方式（那个unsigned int转换真的坑）
- set → unordered_set
class Solution {
public:
long long encode(int x, int y) {
return ((long long)x << 32) | (unsigned int)y;
}
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int ans = 0;
int x = 0, y = 0;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dir = 0;
unordered_set<long long> st;
for (const auto& ob : obstacles) {
st.insert(encode(ob[0], ob[1]));
}
for (int com : commands) {
if (com == -1) {
dir = (dir + 1) % 4;
} else if (com == -2) {
dir = (dir + 3) % 4;
} else {
for (int i = 0; i < com; i++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (st.count(encode(nx, ny))) break;
x = nx;
y = ny;
ans = max(ans, x * x + y * y);
}
}
}
return ans;
}
};
--【叁】--：
每日一题学习
--【肆】--：
模拟模拟
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
set<int> s;
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
int id_dir = 0;
int X = 0,Y = 0;
int res = 0;
for(const auto& it: obstacles) {
int val = it[0] * 6e4 + it[1];
s.insert(val);
}
auto jud_obs = [&](int x,int y) -> bool {
if(x > 3e4 || x < -3e4 || y > 3e4 || y < -3e4) {
return false;
}
int val = x * 6e4 + y;
if(s.find(val) != s.end()) {
return true;
}
return false;
};
for(const auto& it : commands) {
if(it == -2) {
id_dir = (id_dir - 1 + 4) % 4;
} else if(it == -1) {
id_dir = (id_dir + 1) % 4;
} else {
for(int i = 0; i < it; i++) {
int next_X = X + dx[id_dir];
int next_Y = Y + dy[id_dir];
if(jud_obs(next_X,next_Y)) {
break;
}
X = next_X;
Y = next_Y;
}
res = max(res,X * X + Y * Y);
}
}
return res;
}
};