HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 04-29

2021-04-29 21:01:42 By 张义丰

【set】

1、排序

2、去重

s.size() 元素个数

s.insert(x) 插入

s.erase(x) 删除

s.find(x) 查找

s.count(x) 统计x的数量

/*************************************************************************
    > File Name: set.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 06:12:42 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> s;
    s.insert(8);
    s.insert(99);
    s.insert(5);
    s.insert(-2);
    s.insert(22);
    s.insert(5);
    s.insert(8);
    s.insert(5);
    cout << s.size() << endl;
    if (s.count(5) == 1){
        cout << "5 yes\n";
    } else {
        cout << "5 no\n";
    }
    s.erase(5);
    if (s.count(5) == 1){
        cout << "next 5 yes\n";
    } else {
        cout << "next 5 no\n";
    }
    for (auto it = s.begin(); it != s.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

auto自动推导类型

set<int>::iterator it

编译需要加 -std=c++11

反迭代器:rbegin(), rend()

自定义类型

/*************************************************************************
    > File Name: set.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 06:12:42 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x, y;
    bool operator< (const node&b) const{
        return this->x < b.x;
    }
};
int main(){
    set<node> s;
    s.insert((node){2, 3});
    s.insert((node){-1, 9});
    s.insert((node){5, 2});
    for (auto it = s.begin(); it != s.end(); it ++){
        cout << it->x << " " << it->y << endl;
    }
      return 0;
}

【map】

键值对,唯一键对应自身值

set的增强扩展版

pair

m.size()

m.insert(pair)

m.erase(key)

m.find(x) 查找

m.count(x)

重载了[ ],m[key] = 'A'

/*************************************************************************
    > File Name: map.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 06:41:20 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
#include <utility> //make_pair
using namespace std;
int main(){
    map<string, int> m;
    m.insert(make_pair("abc", 123));
    m.insert(make_pair("haha _()987", 12345678));
    m["tianchuanzhang"] = 987654321;
    cout << m.size() << endl;
    if (m.count("abc") == 1) {
        cout << "find abc, value is " << m["abc"] << endl;
    } else {
        cout << "not find abc" << endl;
    }
    m.erase("abc");
    if (m.count("abc") == 1) {
        cout << "next find abc, value is " << m["abc"] << endl;
    } else {
        cout << "next not find abc" << endl;
    }
    m["{hah}{456}"] = 90909090;
    m["qwerqrt"] =456754656;
    for (auto it = m.begin(); it != m.end(); ++it){
        cout << (*it).first << ' ' << (*it).second << endl;
    }
    return 0;
}

【multiset】【multimap】

multimap没有[ ]运算

里面的元素可重复

【unordered_set】

哈希版set(无序)

s.size()

s.insert(x)

s.erase(x)

s.find(x)

s.count(x)

/*************************************************************************
    > File Name: unordered_set.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 07:24:32 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    unordered_set<string> s;
    s.insert("abc");
    s.insert("haha");
    s.insert("12345");
    s.insert("()-=+.,/");
    s.insert("OPERA");
    cout << s.size() << endl;
    if (s.find("abc") != s.end()){
        cout << "abc yes" << endl;
    } else {
        cout << "abcc no" << endl;
    }
    s.erase("abc");
    if (s.count("abc") == 1){
        cout << "next abc yes" << endl;
    } else {
        cout << "nex abc no" << endl;
    }
    for (auto it = s.begin(); it != s.end(); ++it){
        cout << *it << endl;
    }
    return 0;
}

如果是自定义结构,那么要手动实现hash函数

【unordered_map】

unordered_multiset, unordered_multimap 也有的

OJ刷题


OJ-378 字符串括号匹配2

/*************************************************************************
    > File Name: 377.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 27 Apr 2021 09:25:05 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
stack<char> S;
int main(){
    string s;
    cin >> s;
    for (int i=0; s[i]!='@'; ++i){
        if (s[i] == '(' || s[i] == '[' || s[i] == '{'){
            S.push(s[i]);
        }else if (s[i] == ')'){
            if (S.empty() || S.top()!='('){
                cout << "NO\n";
                return 0;
            }else{
                S.pop();
            }
        }else if (s[i] == ']'){
            if (S.empty() || S.top() !='['){
                cout << "NO\n";
                return 0;
            } else {
                S.pop();
            }
        }else if (s[i] == '}'){
            if (S.empty() || S.top() != '{'){
                cout << "NO\n";
                return 0;
            }else{
                S.pop();
            }
        }
    }
    if (!S.empty()){
        cout << "NO\n";
    }else {
        cout << "YES\n";
    }
    return 0;
}

OJ-379 仓库日志

辅助栈(极大值栈

货物站可以省略

/*************************************************************************
    > File Name: 379.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 08:01:17 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    stack<int> S;
    int n, op, t;
    scanf("%d", &n);
    for (int i=0; i<n; ++i){
        scanf("%d", &op);
        switch (op){
            case 0:scanf("%d", &t);
            if (S.empty() || S.top()<t){
                S.push(t);
            }else{
                S.push(S.top());
            }
            break;
            case 1:if (!S.empty()){
                S.pop();
            }
            break;
            case 2:if (S.empty()){
                printf("0\n");
            }else {
                printf("%d\n", S.top());
            }
        }
    }
    return 0;
}

OJ-569 溶液模拟器

/*************************************************************************
    > File Name: 569.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 08:20:45 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
struct node{
    double v, c, salt;
};
int main(){
    stack<node> sta;
    double v0, c0, salt0;
    int n;
    cin >> v0 >> c0;
    salt0 = v0*c0/100;
    cin >> n;
    for (int i=0; i<n; ++i){
        char t;
        cin >> t;
        if (t == 'P'){
            double vt, ct, saltt;
            cin >> vt >> ct;
            saltt = vt*ct/100;
            v0 += vt;
            salt0 += saltt;
            sta.push((node){vt, ct, saltt});
        } else {
            if (!sta.empty()){
                v0 -= sta.top().v;
                salt0 -= sta.top().salt;
                sta.pop();
            }
        }
        printf("%d %.5lf\n", (int)v0, salt0/v0*100);
    }
    return 0;
}

OJ-384 敲七

/*************************************************************************
    > File Name: 384.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 29 Apr 2021 08:43:25 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
queue<int> Q;
int safe(int x){
    if (x%7 == 0) return 0;
    while (x){
        if (x%10 == 7){
            return 0;
        }
        x /= 10;
    }
    return 1;
}
int main(){
    int n, x, t;
    cin >> n >> x >> t;
    for (int i=x; i<=n; ++i){
        Q.push(i);
    }
    for (int i=1; i<x; ++i){
        Q.push(i);
    }
    while (Q.size() != 1){
        if (safe(t++)){
            Q.push(Q.front());
            Q.pop();
        }else{
            Q.pop();
        }
    }
    cout << Q.front() << endl;
    return 0;
}

作业 :OJ-385 海港

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。