HZOJ Logo 张义丰的博客

博客

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

2021-04-27 21:00:42 By 张义丰

【cppreferece.com】

【STL六大组件】

容器

算法

适配器

迭代器

分配器

仿函数

【string】

str.size() 或 str.length() 长度

str.find("找什么",, 从哪儿开始找) 查找 没找到 string::npos (size_type)-1

str.insert(在哪儿, “插入什么” ) 插入

str.substr(从哪儿开始, 长度) 截取,注意第二个参数是长度!

str.replace(从哪儿开始, 长度, “替换成什么”) 替换

代码演示

/*************************************************************************
    > File Name: string.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 27 Apr 2021 06:26:56 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    str = "abcdef";
    str[0] = 'A';
    for (int i = 0; i < str.size(); ++i){
        cout << str[i];
    }
    cout << endl;
    cout << str.size() << " " << str.length() << endl;
    cout << str.find("cd") << " " << str.find("cd", 4) << endl;
    if (str.find("cd", 4) == string::npos) {
        cout << "not find" << endl;
    }
    str.insert(3, "123");
    cout << str << endl;
    string t = str.substr(2);
    cout << t << endl;
    t = t.substr(2, 2);
    cout << t << endl;
    t = t + t;
    str.replace(2, 2, t);
    cout << str << endl;
    sort(str.begin(), str.end());
    cout << str << endl;
    reverse(str.begin(), str.end());
    cout << str << endl;
    return 0;
}

迭代器 str.begin() str.end()

【vector】

v.size() 元素数量

v.push_back(x) 在最后加入x

v[a] 访问下标为a的元素

初始化

vector <int>  v(5, 1);//5个空间,值为1

v.capacity() 空间数量

扩容原则

/*************************************************************************
    > File Name: vector.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 27 Apr 2021 06:51:20 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector <vector<int>> V;
    vector<int> v;
    int temp = -1;
    for (int i = 0; i<1000000; i++) {
        if (temp != v.capacity()){
            cout << v.capacity() << endl;
            temp = v.capacity();
        }
        v.push_back(i);
    }
    /*
    vector <int> v(3, 5);
    v.push_back(6);
    v.push_back(7);
    for (int i=0; i< v.size(); ++i){
        cout << v[i] << " ";
    }
    cout << endl;
    */
    return 0;
}

【stack】

sta.size() 元素数量

sta.push(x) 插入x

sta.pop() 弹出栈顶元素

sta.top() 栈顶元素

sta.empty() 是否为空

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

#include <bits/stdc++.h>
using namespace std;
int main(){
    stack <int> sta;
    sta.push(5);
    sta.push(2);
    sta.push(8);
    sta.push(-3);
    sta.push(99);
    cout << sta.size() << " " << sta.top() << endl;
    while (!sta.empty()) {
        cout << sta.top() << endl;
        sta.pop();
    }
    cout << sta.size() << endl;
    return 0;
}

栈是由双端队列封装出来的,所以是容器适配器

【queue】

que.size() 元素数量

que.push(x) 入队

que.pop() 出队

que.front() 队首元素

que.empty() 是否为空

que.back() 队尾元素

/*************************************************************************
    > File Name: queue.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 27 Apr 2021 07:44:34 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    queue <int> que;
    que.push(5);
    que.push(8);
    que.push(1);
    que.push(99);
    que.push(0);
    cout << que.size() << " " << que.front() << " " << que.back() << endl;
    while (!que.empty()){
        cout << que.front() << " " << que.back() << endl;
        que.pop();
    }
    cout << que.size() << endl;
    return 0;
}

队列是由双端队列封装出来的,所以是(容器)适配器

【遍历栈、队列,不删元素】

栈:只能用另一个暂时存一下

队列:循环n次”将队首元素放入队尾“,n为队列中的元素个数

​ 注意:队列没有迭代器

【deque】

dq.size()

dq.push_front(x)

dq.pop_front()

dq.push_back(x)

dq.pop_back()

dq.front()

dq.back()

/*************************************************************************
    > File Name: deque.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Tue 27 Apr 2021 08:02:42 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main(){
    deque<int> que;
    que.push_back(5);
    que.push_back(7);
    que.push_front(99);
    que.push_front(-2);
    que.push_back(8);
    cout << que.size() << " " << que.front() << " " << que.back() << endl;
    int t = 0;
    while (!que.empty()) {
        cout << que.front() << " " << que.back() << endl;
        if (t % 2 == 0){
            que.pop_front();
        } else {
            que.pop_back();
        }
        t++;
    }
    cout << que.size() << endl;
    return 0;
}

可以通过下标直接访问元素

双端队列本质上是指针数组,顺序容器

【priority_queue】

用数组模拟的堆,默认大根堆

pq.size()

pq.push(x)

pq.pop()

pq.top()

pq.empty()

自定义结构的排序方法

1、默认排序方法 => 重载小于号 (逻辑有点混乱)

bool operator < (const node &b) const {
  return this->x > b.x;
}

2、指定排序方法

struct cmp{
  bool operator() (const node &a, const node &b) {
     return a.x > b.x;
  }
}
priority_queue<node, vector<node>, cmp> que;

注意:

1、排序容器,指定比较方法

2、必须重载小于号

评论

暂无评论

发表评论

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