“find()”如何在“std::set<std::pair<int,int>>”中工作？

Question

我正在解决LeetCode问题“路径交叉”，其中我使用

set<pair<int,int>>

，试图找出点

x,y

是否已经在路径中。但我没有得到想要的结果。

bool isPathCrossing(string s) {
    set <pair <int, int>> st;
    int x = 0, y = 0;
    st.insert(make_pair(x,y));
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'N') y++;
        else if(s[i] == 'W') x++;
        else if(s[i] == 'S') y--;
        else x--;
        pair <int, int> pr = make_pair(x, y);
        if(st.find(pr) != st.end()) return false;
        st.insert(pr);
    } 
    return true;
}

find()

方法仅适用于

pair

的第一个元素，还是同时适用于两个元素？

Answer 1

为了回答您的问题，当

find()

比较 2 个

pair

对象时，会同时查看

first

和

second

值，而不仅仅是

first

值。

也就是说，你没有得到想要的结果的原因很简单，因为你没有遵循 LeetCode 给你的指示：

• 您的

  return

  值倒退了。

  如果循环在

  true

  中找到现有点，则需要返回

  set

  ，否则，如果整个

  false

  被消耗而没有找到匹配项，则返回

  string

  。

• 您的

  x

  坐标的移动是向后的。

  西向左移动，东向右移动，因此您需要在 x 上

  减少

  'W'

  ，在 x 上

  增加

  'E'

  。

这是更正后的代码：

bool isPathCrossing(string s) {
    set <pair <int, int>> st;
    int x = 0, y = 0;
    st.insert(make_pair(x,y));
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'N') y++;
        else if(s[i] == 'W') x--;
        else if(s[i] == 'S') y--;
        else x++;
        pair <int, int> pr = make_pair(x, y);
        if(st.find(pr) != st.end()) return true;
        st.insert(pr);
    } 
    return false;
}  

在线演示