C++算法

algorithm库函数

#include<algorithm>
using namespace std;

排序：sort(beigin,end) 范围：[begin , end)

//例1.
vector<int> vec;
//一顿操作后...
sort(vec.begin(),vec.end());
//例2.
int num[20];
sort(num,num+20);

设置排序的规则：sort(begin,end,comp)

• comp相当于函数的函数名
• bool comp(lhs,rhs)
  • lhs、rhs是待排序元素
  • 不发生交换：返回真
  • 发生交换：返回假

如果排序不是稳定的，但是题目要求定，可以加入int seq;用来记录录入的顺序，实现稳定排序

String

1. 关于字符数据的两种输入：

char buf[100];
//1
scanf("%s",buf);//只能读取一个单词（遇到空格停止）
//2
fgets(buf,100,stdin);//只能读取一整行（包括换行符）
//去掉末尾换行符：
string str = buf;
str.pop_back();

2. C风格的字符串：字符数组（以’\0’结尾）
   C++风格的字符串：string

#include<string>
using namespace std;

3. C风格==>C++风格： str = char_str
   C++风格==>C风格：char_str = str.c_str()
4. 输入输出都要先转化（都转成C风格的字符串）
   • 输入：scanf("%s",char_str);
   • 输出：printf("%s",str.c_str());

如果想用string[i] = ‘h’来插入元素，必须先初始化大小：string s1(10,’c’); 否则会报异常

初始化

string s1;           //默认初始化，s1是一个空串
string s2(s1);       //s2是s1的副本(string类的拷贝构造)
string s2 = s1;      //等价于s2(s1)，s2是s1的副本(string类的拷贝赋值)
string s3("value");  //s3是字面值"value"的副本，除了字面值最后的那个空字符外
string s3 = "value"; //等价于s3("value")，s3是字面值"value"的副本
string s4(n,'c');    //把s4初始化为由连续n个字符c组成的串 

常见操作

1. 判断相等：str == "hello"
2. 比较字典序：str>"abandon"
3. 访问字符串长度：str.size() 或 str.length()
4. 访问字符串的每个元素：

// 1.下标访问
// 2.迭代器访问
for(string::iterator it = str.begin();it!=str.end();++it) {
    printf("%c",*it);
}

5. 连接操作：+（只对c++风格有效）
6. 删除操作：
   • str.erase(4) 删除下标为4的元素
   • str.erase(str.size()-1)删除最后一个元素
7. 清空操作：str.clear()
8. 字符串匹配：find()方法
   • 找到返回：匹配内容起点的下标
   • 未找到返回：str::npos

string str = "how are you";
if(str.find("are")!=string::npos) {
    printf("找到了");
}

9. 字符串string截取：str.substr(起始下标，截取长度)

string str = "hello";
str.substr(1,2); // 得到el

10. 数字转成字符串：to_string(123);//“123” ==>返回string类型
    • 应用场景：如果想知道一个数字num的位数有几位，可以to_string(num).size()
11. 字符串转成数字：stoi("919"); //919
12. 字符串末尾加一个字符c：str.push_back(c);
13. 从字符串末尾弹出一个字符：str.pop_back();
14. 计算字符串某个字符数：count(str.begin(),str.end(),' ');

vector

数组的限制：

• 在定义的时候，就要指定大小（常量）
• 函数内部定义的数组不能太长（如果需要很长的，只能定义成全局变量）

解决：引入向量（动态数组）

• 顺序存储/线性表

#include<vector>
using namespace std;
vector<int> vec;

如果想用vec[i] = 5来插入元素，必须事先初始化大小：vector<int> vec(10); 否则会报异常

---

初始化

vector<int> vec1{1,2,3};
vector<int> vec2(100); 
// 给这100个地方都附上-1，即：{-1,-1,-1,.....,-1}
fill(vec2.begin(),vec2.end(),-1);

常见操作

1. 获取长度：vec.size() 或 vec.length()
2. 尾部扩容：vec.push_back(1)
3. 弹出最后一个元素：vec.pop_back()
4. 访问：
   • vec[i]
   • 迭代器访问：
     • vec.begin()：指向第一个元素
     • vec.end()：指向最后一个元素的后一个元素

for(vector<int>::it = vec.begin();it<vec.end();++it) {
    printf("%d",*it);
}

5. 修改：vec[i] = 3
6. 随机位置的插入：
   • 假设有数组：1,2,3,4。在2号元素后面插入元素5，插入后===>1,2,5,3,4

vector<int>::iterator it = vec.begin+2;//找到3号元素的迭代器
vec.insert(it,5);//在3号元素的前面插入5

7. 随机位置的删除：
   • 假设有数组：1,2,3,4。删除2号元素，删除后===>1,3,4

vector<int>::iterator it = vec.begin+1;//找到2号元素的迭代器
vec.erase(it);//删除2号元素

map

map的底层是二叉搜索树：构建O(nlogn)、查找O(logn)
map<string,int> myMap;

常见操作

1. 判空：myMap.empty()
2. 获取键值对的个数：myMap.size()
3. 插入一对键值对：

myMap["xiaolin"] = 3;
myMap.insert(pair<string,int>("03",3));
myMap.insert({"33", 3});

4. 删除一对键值对：myMap.erase("xiaolin");
5. 键值对的个数：myMap.size();
6. 迭代器：

map<string,int>::iterator beginIt = myMap.begin(); // 指向第一个元素
map<string,int>::iterator endIt = myMap.end();   //指向最后一个元素的后一个元素（尾后）

7. 遍历：

for(map<string,int>::iterator it = myMap.begin();it!=myMap.end();++it) {
    printf("key=%c,value=%d",it->first,it->second);
}

map<string,int> myMap;
// 法1
for(map<string,int>::iterator it = myMap.begin();it!=myMap.end();++it) {
    printf("key=%c,value=%d",it->first,it->second);
}
// 法2
for(const auto&[key,value] : myMap) {
    printf("key=%c,value=%d",key,value);
}

8. 某个键是否存在：

if(myMap.find("xiaolin") == myMap.end()) {
    printf("未找到");
}

set

#include<set>
using namespace std;
set<int> s;

常见操作

1. 插入：s.insert(333); 往集合中添加元素，它的参数也是只有一个，就是你想要添加的元素，无返回值。
2. 删除：s.erase(333); 用来删除指定的元素，参数只有一个，并且是你想要删除的元素，无返回值
3. 查找在集合中出现的元素个数：s.count(333); 因为集合的互异性，它的返回值要么是1要么是0，一般也可以用它来判断某个元素是否在该集合中。
4. 查找某元素是否在集合中：find()

if(s.find("33")!=s.end()) {
    printf("在集合中");
}else {
    printf("不在集合中");
}

5. 得出集合中的元素个数：s.size()
6. 判断该集合是否为空：s.empty()
7. 清空集合中的元素：a.clear()
8. 遍历：

//法一：
for(int i:s) {
    printf("%d",i);
}
//法二：
for(set<int>::iterator it = s.begin();it<s.end();++it) {
    printf("%d",*it);
}

stack

栈：先进后出（场景：“优先级差别”等待）

#include<stack>
using namespace std;
stack<int> myStack;

1. 大小：size()
2. 压栈：push()
3. 取栈顶元素：top()`
4. 弹栈：pop()
5. 判断栈是否为空：empty()

queue

#include<queue>
using namespace std;
queue<int> myQueue;

1. 入队：push
2. 出队：pop
3. 判断为空：empty
4. 队首元素：front