重点在于对哈希表unordered_set <pair<int, int>>的应用,具体可以看这个博客
哈希表之unordered_set <pair<int, int>> 案例与分析
https://blog.csdn.net/weixin_45259896/article/details/121733861
unordered_set是个无序的set,为什么不能直接用set我个人认为不是时间问,而是set似乎不能和pair一起用,毕竟它也不知道该怎么排序了,也许重定义排序函数后可行,但是这个题里没有必要。
然后官方给的题解有问题,不能直接用unordered_set <pair<int, int>>,还得加个自定义的结构体pair_hash在后面,也就是unordered_set<pair<int, int>, pair_hash> ,因为这里要重新定义哈希(不然set的唯一性是怎么来的)。当然题解里return的是return h1 ^h2,我换成了|也没事,看起来主要是为了返回一个唯一值。
还有一个问题就是我自己的程序提交上去的时候先报内存不足,改成long后报超时,后来我试了试应该是commands>0时那块儿,我用了个while,但是他那个样例我无法本地测试,因为障碍是0,我给obstacles传个空集合编译器就会给我报错,不知道力扣下边的main到底是怎么写的,折腾半天后来换成for循环就好了,但是我用while它别的测试样例是能通过的,就不是很理解。
using namespace std;
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
int x, y;
int distance;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int di = 0;
x = y = 0;
distance = 0;
unordered_set<pair<int, int>, pair_hash> obstacleSet;
for (vector<int>obstacle : obstacles)
obstacleSet.insert(make_pair(obstacle[0], obstacle[1]));
for(int i=0;i<commands.size();i++){
if (commands[i] == -1) {
di = (di + 1 + 4) % 4;
}
if (commands[i] == -2) {
di = (di - 1 + 4) % 4;
}
else {
for (int k = 0; k < commands[i]; ++k) {
int nx = x + dx[di];
int ny = y + dy[di];
if (obstacleSet.find(make_pair(nx, ny)) == obstacleSet.end()) {
x = nx;
y = ny;
distance = max(distance, x*x + y*y);
}
}
}
}
return distance;
}
private:
struct pair_hash
{
template <class T1, class T2>
ssize_t operator () (pair<T1, T2> const &pair) const
{
size_t h1 = hash<T1>()(pair.first);
size_t h2 = hash<T2>()(pair.second);
return h1 | h2;
}
};
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)