哈希集合基本操作

1
2
3
4
5
6
7
8
9
10
11
12
unordered_map<int,int>h1;
unordered_set<int>h2;

// 	在容器中查找以 key 键的键值对的个数。
h1.count(键值)
h2.count(键值)

// 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
// 所以对find 进行判断 要根据迭代器进行判断
h1.find(键值) == h1.end() // 没找到
h1.find(键值) != h1.end() // 找到

遍历map

1
2
3
4
5
6
7
8
9
10
11
map<int,int>hash;
// 遍历值
for(auto & v : hash){
    ...
}

// 遍历键值对
for(auto it = hash.begin() ; it != hash.end() ; it++){
    cout << it->first << ' ' << it->second << endl;
    ...
}

切片

以vector为例子

1
2
3
4
5
6

vector<int>q;

// 返回前k个的话
return vector<int>(q.begin(),q.begin() + k);

c++ 自定义排序

自定义排序 在算法题中运用的非常多 尤其是贪心之类的题目

  1. cmp
    自定义cmp函数 传入 sort中 相对来说比较麻烦 但比较清晰吧 记不起lambda的时候 可以用这个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct Data{
    int a;
    int b;
};

// 升序 
bool cmp1(int a, int b){
    return a < b;
}

// 降序
bool cmp2(int a, int b){
    return a > b;
}

// 结构体排序
bool cmps1(Data &d1,Data &d2){
    // 按照 a 升序
    return d1.a < d2.a;
}

bool cmps2(Data &d1,Data &d2){
    // 按照 b 降序
    return d1.b > d2.b;
}

int main(){
    int *q = new int[5]{3,7,2,9,1};
    sort(q,q + 5,cmp2);

    for(int i = 0 ; i < 5 ; i++){
        printf("%d ",q[i]);
    }


    struct Data *qd = new struct Data[4]{{4,7},{3,1},{8,6},{2,5}};

    sort(qd,qd + 4, cmps2);

    for(int i = 0 ; i < 4 ; i++){
        printf("%d %d\n",qd[i].a,qd[i].b);
    }
    
}

  1. lambda 就是在sort里面直接定义函数 把过程简化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 升序 
sort(q,q + 5,[&](int a,int b) -> bool{
        return a < b;
});

// 结构体排序
// 按a升序
sort(qd,qd + 4, [&](Data &d1,Data &d2)->bool{
    return d1.a < d2.a;
});
// 按b降序
sort(qd,qd + 4,[&](Data &d1,Data &d2)->bool{
    return d1.b > d2.b;
});

// vector 排序 以二维为例子
// 贪心题 如合并区间中 常用
sort(q.begin(),q.end(),[&](vector<int> &a,vector<int> &b)->bool{
    return a[0] < b[0];
});