目錄鏈接：
力扣編程題-解法匯總_分享+記錄-CSDN博客
GitHub同步刷題項目：
https://github.com/September26/java-algorithms
原題鏈接：力扣
描述：
機(jī)器人在一個無限大小的 XY 網(wǎng)格平面上行走，從點(diǎn)?(0, 0)?處開始出發(fā)，面向北方。該機(jī)器人可以接收以下三種類型的命令?commands?：
-
-2?：向左轉(zhuǎn)?90?度 -
-1?：向右轉(zhuǎn)?90?度 -
1 <= x <= 9?：向前移動?x?個單位長度
在網(wǎng)格上有一些格子被視為障礙物?obstacles?。第?i?個障礙物位于網(wǎng)格點(diǎn) ?obstacles[i] = (xi, yi)?。
機(jī)器人無法走到障礙物上，它將會停留在障礙物的前一個網(wǎng)格方塊上，但仍然可以繼續(xù)嘗試進(jìn)行該路線的其余部分。
返回從原點(diǎn)到機(jī)器人所有經(jīng)過的路徑點(diǎn)（坐標(biāo)為整數(shù)）的最大歐式距離的平方。（即，如果距離為?5?，則返回?25?）
注意：
- 北表示?
+Y?方向。 - 東表示?
+X?方向。 - 南表示?
-Y?方向。 - 西表示?
-X?方向。
示例 1：
輸入：commands = [4,-1,3], obstacles = [] 輸出：25 解釋： 機(jī)器人開始位于 (0, 0)： 1. 向北移動 4 個單位，到達(dá) (0, 4) 2. 右轉(zhuǎn) 3. 向東移動 3 個單位，到達(dá) (3, 4) 距離原點(diǎn)最遠(yuǎn)的是 (3, 4) ，距離為 32 + 42 = 25
示例?2：
輸入：commands = [4,-1,4,-2,4], obstacles = [[2,4]] 輸出：65 解釋：機(jī)器人開始位于 (0, 0)： 1. 向北移動 4 個單位，到達(dá) (0, 4) 2. 右轉(zhuǎn) 3. 向東移動 1 個單位，然后被位于 (2, 4) 的障礙物阻擋，機(jī)器人停在 (1, 4) 4. 左轉(zhuǎn) 5. 向北走 4 個單位，到達(dá) (1, 8) 距離原點(diǎn)最遠(yuǎn)的是 (1, 8) ，距離為 12 + 82 = 65
提示：
1 <= commands.length <= 104-
commands[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. 模擬行走機(jī)器人
* -2:左轉(zhuǎn)90
* -1:右轉(zhuǎn)90
* 1<=x<=9，移動長度
* 解題思路：
* 首先我們看范圍，1 <= commands.length <= 10^4，0 <= obstacles.length <= 10^4。
* 則肯定不能是n*m的復(fù)雜度，否則時間會超過。
* 但是commands的遍歷肯定是要的，所以我們就想辦法解決obstacles，把其變?yōu)橐粋€O(1)或者O(lgn)復(fù)雜度的查詢。
* obstacles按照x軸和y軸分為兩個map，key為x或者y坐標(biāo)，value為這個坐標(biāo)軸上所有的點(diǎn)，然后進(jìn)行排序。文章來源：http://www.zghlxwxcb.cn/news/detail-666804.html
* 遍歷commands的時候，方向自然不用說，如果遇到了前進(jìn)或者后退，則判斷當(dāng)前軸距離原點(diǎn)最近的點(diǎn)長度，如果大于command則移動command，否則移動最近長度。文章來源地址http://www.zghlxwxcb.cn/news/detail-666804.html
代碼：
class Solution874
{
public:
/**
* 找出比tartget找到有序集合中，比目標(biāo)值相等或者大的
* 或者
* 找到有序集合中，比目標(biāo)值相等或者小的
*/
int findIndex(vector<int> *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 前進(jìn)值
* from 起始值
*/
void takeStep(map<int, vector<int>> &xMap, map<int, vector<int>> &yMap, int &x, int &y, int forward, int step)
{
vector<int> *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(vector<int> &commands, vector<vector<int>> &obstacles)
{
map<int, vector<int>> xMap;
map<int, vector<int>> yMap;
for (vector<int> v : obstacles)
{
int x = v[0];
int y = v[1];
if (xMap.find(y) == xMap.end())
{
xMap[y] = vector<int>();
}
xMap[y].push_back(x);
if (yMap.find(x) == yMap.end())
{
yMap[x] = vector<int>();
}
yMap[x].push_back(y);
}
int max = 0;
// 排序
for (auto at = xMap.begin(); at != xMap.end(); at++)
{
std::vector<int> &value = at->second;
sort(value.begin(), value.end());
}
for (auto at = yMap.begin(); at != yMap.end(); at++)
{
std::vector<int> &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;
}
};到了這里，關(guān)于?LeetCode解法匯總874. 模擬行走機(jī)器人的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
