哈希+set+map

哈希表

哈希表定义

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度
映射函数叫做散列函数
存放记录的数组叫做散列表

一般选用模N取余来获得要插入的位置

对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突

一般有拉链发和开放定址法来处理冲突

数组模拟链表

结点需要有数值域与指针域

因此：创建两个一维数组，分别作为链表的数值域与指针域

int e[N]; // e[i] 表示结点 i 的数值 
int ne[N]; // ne[i] 表示结点 i 的 next 指针（即结点 i 的下一个结点的地址）

e[N] 与 ne[N] 以同一个下标 i 关联在一起，共同组成一个结点

int head; // 头指针，值为虚拟头节点的next指针
int idx; // 其值为下一个插入的新结点的下标

idx 的含义:

链表中没有结点：idx = 0
插入第一个结点后：idx = 0 + 1 = 1
插入第二个结点后：idx = 1 + 1 = 2 ；
…
插入第 i 个结点后：idx = i

因此 idx 表示链表曾经一共插入了多少个结点

idx并不能表示此时链表中一共有多少个结点，因为即使有结点被删除，idx 始终递增
对于删除的结点，其数据仍然保存在数组中，只是不再有指针指向它，即无法被访问到

head这里是指针，不是节点：ne[head]=链表中第一个节点索引

代码

// 用数组模拟链表
const int N = 1000;
// e[N]:用来存储链表结点的值
// Ne[N]:用来存储链表的next指针指向
int e[N], ne[N], head, idx;

初始化

void init(){
    head = -1; //-1表示节点为空，因为数字索引从0开始
    idx = 0;
}

在头节点插入节点的情况

在这里插入图片描述

void insert_head(const int &val){// 头插法
    e[idx] = val;   // 当前插入位置值为val
    ne[idx] = head; // next值为head
    head = idx;     // head指针指向新的索引位置
    idx++;          // 更新下一个插入节点位置
}

在某一个节点后插入节点的情况

在这里插入图片描述

void insert_k_index(int k,const int& val){
    //在k位置后面插入新元素
    e[idx] = val;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

删除某一个节点后元素情况

在这里插入图片描述

void remove_k(int k){//删除k后元素
    ne[k] = ne[ne[k]];
}

遍历

head就是指向第一个元素的索引，e[head]就是第一个值

然后e[ne[head]]就是第二个值

设：m=ne[head] e[ne[m]]就是第三个值

void traverse(){
    int tmp = head;
    while(tmp!=-1){
        cout << e[tmp] << " ";
        tmp = ne[tmp];
    }
    cout << endl;
}

封装成类

class link_arr{
public:
    //构造函数
    link_arr(){
        head = -1;
        idx = 0;
    }
    //头插法，在虚拟头节点后面插值
    void insert_head(const int& v){
        e[idx] = v;
        ne[idx] = head;//新值指向头节点next索引head
        head = idx;
        idx++;
    }
    //在位置k后插入新元素
    void insert_k_index(int k,const int& v){
        //注意每次都在idx处加入新元素
        e[idx] = v;
        ne[idx] = ne[k];
        ne[k] = idx;//断链，ne[k]指向当前节点索引idx
        idx++;
    }
    //删除，删除k位置后的元素
    void remove_k_index(int k){
        ne[k] = ne[ne[k]];
        //不是真删除，只是断了访问索引
        //好处就是避免了大量元素的移动
    }
    //遍历
    void traverse(){
        int tmp = head;
        while(tmp!=-1){
            cout << e[tmp] << " ";
            tmp = ne[tmp];
        }
        cout << endl;
    }
private:
    int e[1000], ne[1000];
    int head, idx;
};

主函数测试

int main(){
    link_arr m;
    m.insert_head(100);
    m.insert_head(200);
    m.insert_head(300);
    m.traverse();
    m.insert_k_index(0, 99);
    m.insert_k_index(1, 88);
    m.insert_k_index(2, 77);
    m.traverse();
    m.remove_k_index(4);
    m.traverse();
    return 0;
}

运行结果

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

模拟散列表

题目描述
维护一个集合，支持如下几种操作：

I x，插入一个数 x；
Q x，询问数 x是否在集合中出现过；
现在要进行 N次操作，对于每个询问操作输出对应的结果。

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

说白了就是实现一种支持插入和查询操作的散列表

拉链法—处理哈希冲突的方法

在这里插入图片描述

//建立的哈希表
const int N = 10000;
int ha[N];//hash数组，存放值
int e[N], ne[N], idx = 0;//数组模拟链表
//散列表插入
void insert(const int& x){
    //用哈希函数找到存放位置k
    int k = (x%N + N) % N;
    //拉链
    e[idx] = x;
    ne[idx] = ha[k];
    ha[k] = idx++;
}
//散列表查询
bool query(const int& x){
    int k = (x % N + N) % N;
    for (int i = ha[k]; i != -1;i=ne[i]){
        if(e[i]==x)
            return true;
    }
    return false;
}

这里选用最简单的哈希函数：h=xmodN

由于c++负数取模依然是负数，所以用+N后再modN可以避免出现负数

除留余数法函数
int Hash(int x){
 return ((x % N) + N) % N;
}

主程序

#include<iostream>
#include<string.h>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    memset(ha, -1, sizeof(ha));//ha用-1填充
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op=='I'){
            insert(x);
        }
        else{//*op=='Q'
           if(query(x))
               puts("yes");
           else
               puts("N0");
        }
    }
    return 0;
}

memset(ha, -1, sizeof(ha));

memset函数定义在头文件string.h中，该函数用来填充缓冲区，（地址，填充值，填充字长）
void *memset(void *str, int c, size_t n)
str – 指向要填充的内存块。
c – 要被设置的值。该值以 int 形式传递，但是函数在填充内存块时是使用该值的无符号字符形式。
n – 要被设置为该值的字符数。

当然也可以不用数组模拟链表，用真链表

//数据结构
const int N = 100;
struct node{//定义链表节点
    int val;
    node *next;
    node(int val,node*next=NULL):val(val),next(next){}
};
node *h[N];//定义出N条链表

//初始化
void init(){
    for (int i = 0; i < N;i++){
        h[i] = new node(-1);
    }
}
// 散列表插入
void insert(const int &x)
{
    int k = (x % N + N) % N;
    // 拉链
    node *cur = new node(x,h[k]->next);
    //cur->next = h[k]->next;--可以一步到位
    h[k]->next = cur;
}
//散列表查询
bool query(const int& x){
    int k = (x % N + N) % N;
    //查询
    for (node *tmp = h[k]->next; tmp != NULL;tmp=tmp->next) {
        
        if(tmp->val==x)
            return true;
    }
    return false;
}

开放定址法—处理哈希表

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

使用线性探测法解决冲突的散列表，删除不能单纯地把要删除的元素设置为空。

在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。

所以删除是将删除的元素特殊标记为deleted。
当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。

#include <iostream>
#include <string.h>
using namespace std;
//这两个数对程序运行十分重要
const int N = 200003;//一般设置成质数，因为模质数会减少冲突
const int null = 0x3f3f3f3f;//null是将所有位置设置为“没存储”
int ha[N];
int find(int val){
    int k = (val % N + N) % N;
    while(ha[k]!=null && ha[k]!=val){
        k++;
        if(k==N)
            k = 0; //如果遍历到最后，从0开始，查找k之前的
    }
    //这个find返回的k包含两种情况
    //k==null,可插入位置
    //k==val,找到的位置
    return k;
}
int main(){
    int n;
    cin>>n;
    memset(ha, null, sizeof(ha));
    while(n--){
        string op;
        int x;
        cin>>op>>x;
        if(op=="I"){
            ha[find(x)] = x;
        }
        else{
            if(ha[find(x)]!=null)
                puts("yes");
            else
                puts("no");
        }
    }
    return 0;
}

输入方式

9 I 1 I 2 I 3 I 4 I 5 I 6 I 7 Q 8 Q 3

N和null的选取决定了程序的运行正确与否

字符串前缀哈希

$\text{已知字符串}str\text{为：}S_nS_{n-1}...S_2S_1\ ,\text{定义好数字}P,Q$

$\text{则}str\text{的映射方式为：}$

$\ \ \ \ \ \ \ \ \ \left( S_n*P^{n-1}+S_{n-1}*P^{n-2}+...+S_2*P^1+S_1*P^0 \right) modQ$

$ex:\ \ h\left( ABCD \right) =1*p^3+2*p^2+3*p^1+4*p^0\left( ABCD\text{分别定义}1234 \right)$

任意字符不可以映射成0

比如 a映射成0,那么aa,aaaa,aaaaa全是0，无法区分

通过巧妙设置P (131 或 13331),Q (2^64)的值，一般可以理解为不产生冲突

前缀哈希

$str\text{为：}S_nS_{n-1}...S_2S_1\,\,\text{，则前缀哈希定义为：}$

$H\left[ 0 \right] =0$

$H\left[ 1 \right] =S_n$

$H\left[ 2 \right] =S_nS_{n-1}$

$.....$

$H\left[ n-1 \right] =S_nS_{n-1}...S_2$

重要公式：

已知[0,…,l-1]的哈希值H[l-1],[0,…,r]的哈希值H[r],求：[l,…,r]的哈希值

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

将哈希数组声明为unsigned long long，这样当字符串相加后的值大于Q时就相当于自动取模了

也就是溢出相当于取模

H[i]=H[i-1]*p+str(i)-----也就是相邻的哈希值是：前一个哈希值+多出的字母

AcWing 841. 【字符串哈希】

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

Yes
No
Yes

关键：

//定义
const int N = 1000, P = 131;
typedef unsigned long long UUL;
UUL ha[N],power[N];
//求区间函数，计算[l,r]区间内的哈希值
UUL getHash(int l,int r){
    return ha[r] - ha[l - 1] * power[r-l+1];
}
//初始化前缀哈希
 //初始化
    ha[0] = 0;
    power[0] = 1;//P的0次幂为1
    for (int i = 1; i <= str.size();i++){//从1开始到str长度结束
        ha[i] = ha[i - 1]*P+ str[i - 1];//注意str从0开始,str[i-1]
        power[i] = power[i - 1] * P;
    }

完整程序：

#include<iostream>
#include<string>
using namespace std;
const int N = 1000, P = 131;
typedef unsigned long long UUL;
UUL ha[N],power[N];
//计算[l,r]区间内的哈希值
UUL getHash(int l,int r){
    return ha[r] - ha[l - 1] * power[r-l+1];
}
int main(){
    int n,m;//字符串长度n,计算m次区间
    cin >> n >> m;
    string str;
    cin >> str;//输入字符串
    //初始化
    ha[0] = 0;
    power[0] = 1;//P的0次幂为1
    for (int i = 1; i <= n;i++){
        ha[i] = ha[i - 1]*P+ str[i - 1];//注意str从0开始,str[i-1]
        power[i] = power[i - 1] * P;
    }
    //检验
    while(m--){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(getHash(l1,r1)==getHash(l2,r2)){
            puts("yes");
        }
        else{
            puts("no");
        }
    }
    return 0;
}

集合set与映射map

集合set用来存储不重复的值，底层实现是：平衡二叉搜索树

T: set 中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set 中元素默认按照小于来比较
Alloc：set 中元素空间的管理方式，使用 STL 提供的空间配置器管理

set会去重,而且按照升序排列

multiset区别于set就是，它可以存储重复元素，但是元素也是按照升序排列

    int arr[] = {1, 2, 3, 1, 2, 5, 3, 2, 6, 79, 8, 3};
    set<int> ss(arr, arr + sizeof(arr) / sizeof(int));
    cout << ss.size() << endl;//7
    for(auto m:ss)
        cout << m << " ";
    //1 2 3 5 6 8 79

swap()函数—交换头指针

    int arr1[] = {9,8,5,8,9,3};
    int arr2[] = {19,18,15,18,19,13};
    set<int> s1(arr1, arr1 + sizeof(arr1) / sizeof(int));
    set<int> s2(arr2, arr2 + sizeof(arr2) / sizeof(int));
    s1.swap(s2);//两个集合交换
    for(auto val:s1)
        cout << val << " ";
//13 15 18 19

s.clear()是清空所有函数;find(),count(),erase(),insert()

int arr1[] = {9,8,5,8,9,3};
    set<int> s1(arr1, arr1 + sizeof(arr1) / sizeof(int));
    auto pos = s1.find(9);//*pos=9
    s1.erase(pos);//删除传入迭代器
    s1.count(8);//bool，返回true或者false

映射map存储关键码key和对应值value,一般用平衡二叉搜索树实现，按key大小排列

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

key: 键值对中 key 的类型

T：键值对中 value 的类型

Compare: 比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器,一般来说空间配置器是vector或list

注意：在使用 map 时，需要包含头文件。

map 中的 key 是唯一的，并且不能修改,支持[]操作符，operator[]中实际进行插入查找

插入

采用创建pair的形式插入pair<string, string>(,)
采用make_pair的形式进行插入make_pair(,)
采用大括号的形式进行插入{}

map<int, string> mp;
    mp.insert(pair<int, string>(100, "good"));
    mp.insert(make_pair(200, "news"));
    mp.insert({300, "home"});
    mp[400] = "English";
    for(auto [k,v]:mp){
        cout << k << "," << v << endl;
    }

//另一种遍历
for(auto m:mp){//auto是：map<int,string>
        cout << m.first << "," << m.second << endl;
    }

同set一样，map的key不允许修改

但是map的value可以修改

map的find和count只针对key

map<int, string> mp;
    mp.insert(pair<int, string>(100, "good"));
    mp.insert(make_pair(200, "news"));
    mp.insert({300, "home"});
    mp[400] = "English";
    /*两种查找方式*/
    auto val = mp.find(300);
    cout << val->second << endl;
    cout << mp[300] << endl;
    /*只判断是否存在*/
    cout << mp.count(100) << endl;
    //修改value,加上{}
    for(auto &val:mp){
        val.second.insert(0,"{");
        val.second += "}";
    }
    //迭代器遍历
    for (auto val = mp.begin(); val != mp.end();val++){
        cout << val->first<<" "<<val->second <<endl;
    }

map可以用于统计频次

mp[key]++是最简单的方式

 string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球",\
                     "足球","排球","羽毛球","篮球","足球" };
    map<string, int> mp;
    for(auto val:arr){
        mp[val]++;
    }
    for(auto val:mp){
        cout << val.first << " " << val.second << endl;
    }

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

借助find()函数，插入过就频次加一

string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球",\
                     "足球","排球","羽毛球","篮球","足球" };
    map<string, int> mp;
    for (auto str : arr)
    {
        auto it = mp.find(str);
        if (it == mp.end()) {
                mp.insert({str, 1});
        }
        else{
            it->second++;
        }
    }

借助insert的返回值

返回值是：pair对，第一个元素是map的迭代器，第二个元素是bool类型变量

 string arr[] = { "篮球","足球","排球","羽毛球","足球","乒乓球",\
                     "足球","排球","羽毛球","篮球","足球" };
    map<string, int> mp;
    for(auto val:arr){
        auto it=mp.insert(make_pair(val,1));
        if(it.second==false){
            //注意it是.迭代器后用->
            it.first->second++;
        }
    }

map和set可以定义升序

set<T,greater> ;

map<key,value,greater>;

 int arr[] = { 1,6,7,8,2,4,2,6 };
    //map按key降序,set降序排列
    multiset<int,greater<int>> s;//key可以重复
    map<int, int,greater<int>> mp;
    for(auto val:arr){
        s.insert(val);
        mp[val]++;
    }
    //输出集合set
    for(auto val:s){
        cout <<val<<" ";//8 7 6 6 4 2 2 1 
    }
    cout << endl;
    //输出映射map
    for(auto val:mp){
        cout <<"("<<val.first << " " << val.second <<")"<< " ";
    }//(8 1) (7 1) (6 2) (4 1) (2 2) (1 1)

leecode题

692. 前K个高频单词

首先需要用map<string,int> mp来统计频次，key已经按照字典升序了

接下来可以用map<string,int> tmp，将频次优先

相同频次tmp只会记录一次，本题都需要，所以用multimap
要求频次依次降低，所以multimap需要加上greater<>来降序

 vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res;
        //用map统计单词频次
        map<string,int> mp;
        for(auto val:words) mp[val]++;
        //用multimap对频次排序，降序
        multimap<int,string,greater<int>> mmp;
        //把map元素放入mmp中
        for(auto &val:mp){
            mmp.insert({val.second,val.first});
        }
        //把mmp前个装入res
        auto it=mmp.begin();
        while(k--){
            res.push_back(it->second);
            it++;
        }
        return res;
    }

1. 两数之和

方法：用map记录值和下标，map[key:值]=下标

对于当前访问的元素nums[i],去map找“target-nums[i]"
假设j<i
for i 0~n-1
   对j从[0,i-1]中：搜索是否存在target-nums[i]的值
//枚举i，去它前面搜索值

vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> mp;//mp[值]=下标
        for(int i=0;i<nums.size();i++){
            //如果map存在了target-nums[i],说明找到了
            if(mp.find(target-nums[i])!=mp.end()){
                 return {i,mp[target-nums[i]]};
            }
            mp[nums[i]]=i;
        }
        return {};
    }

49. 字母异位词分组

问题关键是分组，如果让不同序列的单词划分一组

选用排序好的序列作为key,相同字母不同排序会有着相同的key

所以只要将值设为vector<string>,然后把mp[key]的元素存入即可

 vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        //把每一个单词排序
        //把排序好的单词作为key,将相同的放入string中
        unordered_map<string,vector<string>> mp;
        for(auto val:strs){//遍历字符串
            //因为放入值是未排序的，所以赋值进行排序
            string copy=val;
            sort(copy.begin(),copy.end());
            //把copy作为关键字，分组
            mp[copy].push_back(val);
        }
        //把结果放入res返回
        for(auto val:mp){
            res.push_back(val.second);
        }
        return res;
    }

如何输出mp的second

       for(auto aa:mp){
            cout<<aa.first<<":";
            for(auto bb:aa.second){
                cout<<bb<<" "; 
            }
            cout<<endl;
        }

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

187. 重复的DNA序列

题目规定了长度为10，所以以10个为一组计算出所有前缀哈希值

用set存储，只要值重复出现就放入结果

如果3个一样的，结果会存放两次，所以需要删除值

最后要注意边界：

长度小于10，return
res少于两个，没必要去重

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size() <= 10)
            return res;
        //初始化字符串哈希
        pw[0] = 1;
        ha[0] = 0;
        for (int i = 1; i <= s.size(); i++) {
            ha[i] = ha[i - 1] * P + s[i - 1];
            pw[i] = pw[i - 1] * P;
        }
        unordered_set<UUL> set;
        //10个一组，依次计算哈希值
        for (int i = 0; i < s.size() - 9; i++) {
            int j = i + 9; // j-i+1=10;
            if (set.find(getValue(i + 1, j + 1)) != set.end()) {
                res.push_back(s.substr(i, 10));
            }
            set.insert(getValue(i + 1, j + 1));
        }
        //去重
        sort(res.begin(), res.end());
        if (res.size() >= 2) {
            for (auto it = res.begin() + 1; it != res.end();) {
                if (*it == *(it - 1)) {
                    it = res.erase(it);
                } else {
                    it++;
                }
            }
        }
        return res;
    }

private:
    //定义好字符串哈希
    static const int N = 100001, P = 131;//用static才能通过编译
    typedef unsigned long long UUL;
    UUL ha[N], pw[N];
    //定义区间函数
    UUL getValue(int l, int r) { return ha[r] - ha[l - 1] * pw[r - l + 1]; }
};

874. 模拟行走机器人

首先抛开障碍物，给出步数和朝向，如何确定下标？

因为这里是旋转，所以四个方向需要顺时针或者逆时针

比如：↑→↓← （每次左转）或者↑←↓→（每次右转）

定义两个数组和一个数
//假设↑→↓←
int dir;
int dx[]={0,1,0,-1}
int dy[]={1,0,-1,0}
//然后
x+=dx[dir]
y+=dy[dir]
//dir=0向上走，dir=1向右走，dir=2向下走
如果需要掉头只需要取模即可

比如：←向下旋转成↓ 也就是：3变成2 所以：(dir-1)mod 4,(dir+4-1)mod 4,避免出现负数

#include <vector>
#include <iostream>
#include <string>
#include<map>
using namespace std;
class Solution {
public:
    pair<int,int> robotSim(vector<int>& commands) {
        //定义方向数组
        //↑→↓←
        int dx[] = {0,1,0,-1};
        int dy[] = {1,0,-1,0};
        int dir = 0;//初始向上走
        int x = 0, y = 0;//起始位置（0，0）
        //输出方向与距离
        map<int, string> mp;
        mp[0] = "向上走";
        mp[1] = "向右走";
        mp[2] = "向下走";
        mp[3] = "向左走";
        //开始走路
        for (int i = 0; i < commands.size();i++){
            if(commands[i]==-1)//右转 1->2,2->3,3->0
                dir = (dir + 1) % 4;
            else if(commands[i]==-2)//左转 2->1,0->3
                dir = (dir - 1 + 4) % 4;
            else{//开始走了
                cout << mp[dir] << commands[i] << endl;
                int nx = x + dx[dir]*commands[i];
                int ny = y + dy[dir]*commands[i];
                x = nx;
                y = ny;
            }
        }
        return make_pair(x, y);
    }
};
int main(){
    //-2 ：向左转 90 度
    //-1 ：向右转 90 度
    vector<int> commands({9,-2,8,-2,10,-2,7});
    auto m=Solution().robotSim(commands);
    cout << m.first << "," << m.second << endl;
    return 0;
}

接下来考虑障碍物，用set存障碍物,然后每次一步一步走，只要在障碍物就跳出

完整代码

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
          int res=0;//返回结果
          //↑→↓←
          int dx[]={0,1,0,-1};
          int dy[]={1,0,-1,0};
          int dir=0;
          int x=0,y=0;//起点
          //存障碍物
          set< pair<int,int> > s;
          for(auto val:obstacles)
                s.insert({val[0],val[1]});
          //执行指令
          for(auto op:commands){
               if(op==-1)  dir=(dir+1)%4;
               else if(op==-2)
                    dir=(dir-1+4)%4;
                else{
                    for(int i=0;i<op;i++){
                        int nx=x+dx[dir];
                        int ny=y+dy[dir];
                        if(s.find({nx,ny})!=s.end()){
                            break;
                        }
                       x=nx;
                        y=ny;
                        res=max(res,x*x+y*y);
                    }
                }
          }
          return res;
    }

//有时候，set存pair对不可以，所以用string,"key,value"一样可以达到目的

string calHash(int x,int y){//"x,y"
        return to_string(x)+","+to_string(y);
    }

s.insert(calHash(val[0],val[1]));

s.find(calHash(nx,ny))!=s.end()