设计理念网站,wordpress思维导图,自己也可以免费轻松创建一个网站,全国工商登记网目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣 描述#xff1a;
机器人在一个无限大小的 XY 网格平面上行走#xff0c;从点 (0, 0) 处开始出发…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣 描述
机器人在一个无限大小的 XY 网格平面上行走从点 (0, 0) 处开始出发面向北方。该机器人可以接收以下三种类型的命令 commands
-2 向左转 90 度-1 向右转 90 度1 x 9 向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] (xi, yi) 。
机器人无法走到障碍物上它将会停留在障碍物的前一个网格方块上但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点坐标为整数的最大欧式距离的平方。即如果距离为 5 则返回 25 注意
北表示 Y 方向。东表示 X 方向。南表示 -Y 方向。西表示 -X 方向。 示例 1
输入commands [4,-1,3], obstacles []
输出25
解释
机器人开始位于 (0, 0)
1. 向北移动 4 个单位到达 (0, 4)
2. 右转
3. 向东移动 3 个单位到达 (3, 4)
距离原点最远的是 (3, 4) 距离为 32 42 25
示例 2
输入commands [4,-1,4,-2,4], obstacles [[2,4]]
输出65
解释机器人开始位于 (0, 0)
1. 向北移动 4 个单位到达 (0, 4)
2. 右转
3. 向东移动 1 个单位然后被位于 (2, 4) 的障碍物阻挡机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位到达 (1, 8)
距离原点最远的是 (1, 8) 距离为 12 82 65 提示
1 commands.length 104commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].0 obstacles.length 104-3 * 104 xi, yi 3 * 104答案保证小于 231 解题思路
* 874. 模拟行走机器人
* -2:左转90
* -1:右转90
* 1x9移动长度
* 解题思路
* 首先我们看范围1 commands.length 10^40 obstacles.length 10^4。
* 则肯定不能是n*m的复杂度否则时间会超过。
* 但是commands的遍历肯定是要的所以我们就想办法解决obstacles把其变为一个O(1)或者O(lgn)复杂度的查询。
* obstacles按照x轴和y轴分为两个mapkey为x或者y坐标value为这个坐标轴上所有的点然后进行排序。
* 遍历commands的时候方向自然不用说如果遇到了前进或者后退则判断当前轴距离原点最近的点长度如果大于command则移动command否则移动最近长度。 代码
class Solution874
{
public:/*** 找出比tartget找到有序集合中比目标值相等或者大的* 或者* 找到有序集合中比目标值相等或者小的*/int findIndex(vectorint *list, int target, bool isBigger){int left 0;int right list-size() - 1;int middle;int abs isBigger ? right 1 : left - 1;while (left right){middle (left right) / 2;if (isBigger){if ((*list)[middle] target){right middle - 1;abs middle;}else{left middle 1;}}else{if ((*list)[middle] target){abs middle;left middle 1;}else{right middle - 1;}}}return abs;}/*** forward 方向加或者减* value 前进值* from 起始值*/void takeStep(mapint, vectorint xMap, mapint, vectorint yMap, int x, int y, int forward, int step){vectorint *list;int from 0;int *updateValue;bool isAdd forward 1;if (forward 0 || forward 2){from y;if (yMap.find(x) yMap.end()){y y (forward 0 ? step : step * -1);return;}updateValue y;list (yMap[x]);}else if (forward 1 || forward 3){from x;if (xMap.find(y) xMap.end()){x x (forward 1 ? step : step * -1);return;}updateValue x;list (xMap[y]);}int index findIndex(list, from, isAdd);if (index -1 || index list-size()){*updateValue from (isAdd ? step : step * -1);return;}// int expect from (isAdd ? step : step * -1);//int canMove abs((*list)[index] - from) - 1;if (step canMove){*updateValue from (isAdd ? canMove : canMove * -1);}else{*updateValue from (isAdd ? step : step * -1);}}int correctForward(int forward){if (forward 0){return 3;}if (forward 3){return 0;}return forward;}int robotSim(vectorint commands, vectorvectorint obstacles){mapint, vectorint xMap;mapint, vectorint yMap;for (vectorint v : obstacles){int x v[0];int y v[1];if (xMap.find(y) xMap.end()){xMap[y] vectorint();}xMap[y].push_back(x);if (yMap.find(x) yMap.end()){yMap[x] vectorint();}yMap[x].push_back(y);}int max 0;// 排序for (auto at xMap.begin(); at ! xMap.end(); at){std::vectorint value at-second;sort(value.begin(), value.end());}for (auto at yMap.begin(); at ! yMap.end(); at){std::vectorint value at-second;sort(value.begin(), value.end());}int forward 0;int x 0;int y 0;for (int i 0; i commands.size(); i){int command commands[i];if (command -2){forward correctForward(forward - 1);}else if (command -1){forward correctForward(forward 1);}else{takeStep(xMap, yMap, x, y, forward, command);}cout command: command ,forward: forward ,x: x ,y: y ,value: (x * x y * y) endl;max std::max(max, x * x y * y);}return max;}
};
