大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
目录
3.binary_search：查找数组内某个元素是否出现。
入坑rc车的我又来写文啦ヾ(≧▽≦*)o
要“深入探讨”的可以加我qq28562939
想必经常搞C++的人大概都听说过STL库吧(正好最近在研究)，其中最知名我就是我们的——sort快速排序了！
不了解的兄弟也没关系，
我们继续往下看。
难度逐次递增。
首先，咱们搞清楚STL库是啥东西
STL,学名Standard Template Library，一般我们称他为标准模板库，是一系列软件的统称。
从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map一大堆，STL也是算
法和其他一些组件的集合。比如说<algorithm>中sort函数、<string>中string类都
是STL的内容。
STL库还有很多内容，比如：向量（vector）、栈（stack）、队列（queue）、优先队列
（priority_queue）、链表（list）、集合（set）、映射（map）等容器；min、max、swap
、sort、lower_bound、upper_bound 等算法，有的甚至都没人知道。ㄟ( ▔, ▔ )ㄏ
One.快速排序(Sort):
众所周知，c++有各种正常排序和奇葩的排序，比如说冒泡排序，时间复杂度为N(O^2)，就很离谱
是不是，随便排一个100000的元素的数组就超时。
所以，咱们以后不用冒泡，用sort快排（弃暗投明）,时间复杂度为N*LogN，对一百万个数排序也不会超过1秒。
1.Sort的基本用法:
sort是STL自带的系统函数，它的格式是：
void sort(要排序元素的起始地址，要排序元素的结束地址，比较函数)；
这里可以省略比较函数，他是默认从小到大排序的（升序排序）
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int a[]={3,5,2,6,9,3,5};
sort(a,a+7);//7是数组的元素个数，这里a为数组的开头，a+7就等于排序到数组的第七个元素
for(int i=0;i<6;i++)
cout<<a[i]<<" ";
}
输出:
2 3 3 5 5 62.Sort进阶用法（CMP）：
void sort(要排序元素的起始地址，要排序元素的结束地址，比较函数)；,没错又是他，这里我们发
现还有个比较函数没说，这个比较函数的作用就是可以自定义排序方式，比如降序排序。
定义：bool cmp(int x,int y)…..，如果返回True那么x就排在y前面。
#include<algorithm>
#include<iostream>
using namespace std;
bool cmp(int x,int y)
{
if(x>y)return true;//降序
return false;
}
int main()
{
int a[]={3,5,2,6,9,3,5};
sort(a,a+7,cmp);//7是数组的元素个数
for(int i=0;i<6;i++)
cout<<a[i]<<" ";
}
输出：
9 6 5 5 3 33.Sort对结构体(或者类)的排序：
同学们进行干饭比赛，参赛队员分别为“法外狂徒张三”，“干饭者老八”以及王五同学，谁吃的更多谁就排在更前面，如果吃的一样多那么谁吃的老八汉堡多谁就排在更前面：
#include<algorithm>
#include<iostream>
using namespace std;
struct ganfan
{
string name;
int zongshu;
int hanbao;
};
bool cmp(ganfan x,ganfan y)
{
if(x.zongshu>y.zongshu)return true;
else if(x.hanbao>y.hanbao&&x.zongshu==y.zongshu)//如果一样多那么比谁吃的汉堡多
return false;
}
int main()
{
ganfan a[3];
a[0].name="zhangsan";a[0].zongshu=200;a[0].hanbao=6;
a[1].name="laoba";a[1].zongshu=170;a[1].hanbao=13;
a[2].name="wangwu";a[2].zongshu=170;a[2].hanbao=10;
sort(a,a+3,cmp);
for(int i=0;i<3;i++)
cout<<a[i].name<<" ";
}
输出：
wangwu laoba zhangsan我们可以看到，张三的干饭总数是最多的，所以排在最前面，老八和王五的干饭总数一样多，但是老八吃的汉堡更多些，所以老八排在王五前面。
Two.Map
Map简介:
map是STL的一个关联容器，它提供一对一的hash。
- 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
- 第二个可能称为该关键字的值(value)；
定义：
map<类型,类型> m;举个栗子:
记录每个人的名字的对应的爱好,张三喜欢吃汉堡：
#include<map>
#include<iostream>
using namespace std;
int main()
{
map<string,string> m;
m["张三"]="吃汉堡";
cout<<"张三: "<<m["张三"];
}
输出：
张三: 吃汉堡
刷题时间!
题目：离散化基础
在使用离散化方法编程时，通常要知道每个数排序后的编号(rank值)，相同的数对应同一个编号。
输入格式
第1行：一个整数N。 1<=N<=100000。
第2行：有N个整数，每个数都是int范围的。注意：可能有相同整数。
输出格式
依次输出每个数的排名。
输入/输出例子1
输入：
5
8 2 6 9 2
输出：
3 1 2 4 1
题解:
这题用Sort和Map就可以很容易解决:
#include<bits/stdc++.h>
using namespace std;
int N,a[100001],b[100001];
map<int,int> m;
int main(){
cin>>N;
for(int i=0;i<N;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b,b+N);//将数组排序
int c=1;//排名
m[b[0]]=1;//因为数组经过排序，所以第1个元素肯定是第一
for(int i=1;i<N;i++)
{
if(b[i]!=b[i-1])//判断是否不与前一个数相等
{
c++;
m[b[i]]=c;
}
}
for(int i=0;i<N;i++)
if(m[a[i]]!=0)
cout<<m[a[i]]<<" ";//按照原来的下标输出
return 0;
}Three.stack(栈)
头文件:
#include<stack>stack好像还有个翻译叫“咸鱼”…嘿嘿。
栈的介绍：
栈就像一个盒子，可以放入或去除元素，但是个人类都知道，要把盒子底下的东西取出来，就必须先取出他上面的东西。
假如我们把1、2、3、4、5按顺序分别入栈：
——博主美丽的手绘
栈的定义：
stack<类型(可以不写)> st;
或者stack st;很easy是不？
栈的成员函数：
| .empty() | 判断栈是否为空，空则返回true |
| .pop() | 移除栈顶元素 |
| .push(啥啥啥) | 在栈顶增加元素 |
| .size() | 返回栈中元素数目 |
| .top() | 返回栈顶元素 |
.empty() 判断栈是否为空。
stack st;
if(st.empty())//如果是空那么执行下面代码
.......push(啥啥啥),在栈顶增加元素。
.top()，返回栈顶元素，记住是返回，要单独输出。
#include<stack>
#include<iostream>
using namespace std;
stack<int> st;
int main(){
st.push(5418);
cout<<st.top();//输出栈顶元素
return 0;
}输出5418。
.size(), 返回栈中元素数目。
#include<stack>
#include<iostream>
using namespace std;
stack<int> st;
int main(){
st.push(5418);
cout<<st.size();
return 0;
}输出1
.pop()，移除栈顶元素：
#include<stack>
#include<iostream>
using namespace std;
stack<int> st;
int main(){
st.push(1452);
st.push(5418);
st.pop();
cout<<st.top();
return 0;
}输出1452。
简单不？
Four.二分查找
头文件：
#include <algorithm>美妙的函数：
1.lower_bound函数
对于有序容器，有序容器，有序容器（重要的事情说三遍）快速二分查找出第一个大于等于
指定数的位置（下标），如果没有找到，返回最后一个数据后面的位置。
对于数组，通常的格式为：
查找的数组下标 = lower_bound(数组要查找的开始位置，数组要查找的结束位置后面，要找的数) – 数组开始位置(一般写数组名);
比如：
#include<algorithm>
#include<iostream>
using namespace std;
int main() {
int a[5] = { 1,2,3,3,8 };
//从 a 数组中找到第一个不小于 3 的元素
int index = lower_bound(a, a + 5, 3)-a;//查找的数组下标 = lower_bound(数组要查找的开始位置，数组要查找的结束位置后面，要找的数) – 数组开始位置;
if (index==5 ) cout << " not found! ";//index=5，也就是数组末尾的位置。
else cout << index;
return 0;
}输出2。
2.upper_bound函数
有一个类似lower_bound的函数upper_bound, 快速二分查找出第一个大于指定数的位置（下
标），如果没有找到，返回最后一个数据后面的位置。
举个栗子，啊……快没栗子了。(っ °Д °;)っ
#include<algorithm>
#include<iostream>
using namespace std;
int main() {
int a[5] = { 1,2,3,3,8 };
//从 a 数组中找到第一个大于 3 的元素
int index = upper_bound(a, a + 5, 3)-a;
if (index==5 ) cout << " not found! ";
else cout << index;
return 0;
}输出4.
3.binary_search：查找数组内某个元素是否出现。
void binary_search(数组首地址，结束地址，要查找的数)
返回值为bool类型，找到了返回true。
再来一题！
题目：数组线段和M
输入格式
第一行2个正整数N和M，N范围[1，1000000],M范围[1，10^9]。
第二行是N个正整数，每个数范围[1，1000]。
输出格式
一个整数。
输入/输出例子1
输入：
10 20
1 7 10 10 7 10 6 4 6 6
输出：
2
题解：
这题我是用前缀和的方法解的，因为数据较多，这样快一点,还能变成有序数列。
代码稍稍有点难，大家看着办吧：
#include<bits/stdc++.h>
using namespace std;
int N,M;
int a[1000001];
int main(){
cin>>N>>M;
cin>>a[0];
for(int i=1;i<N;i++)
{
cin>>a[i];
a[i]+=a[i-1];//求前缀和数组
}
int ans=0;
int mubiao=M;//目标
for(;int index = lower_bound(a, a + N, mubiao)-a;)
{
if(index==N)//找不到了说明没有了
{
break;
}
if(a[index]==M)
{
mubiao=a[index]+1;
}
else{
int fl=a[index]-M;
int ind=lower_bound(a, a + N, fl)-a;
if(a[ind]==fl)
ans++;
mubiao=a[index]+1;//目标加一，防止重复查找
}
}
cout<<ans;
return 0;
}思路是找一个比M大的数，如果能找到，那么求出这个数和M的差，再找这个差，如果能找到，那根据前缀和的定义这一串的和就等于M，然后把目标+1，防止重复查找。
Six.list(链表)
常用操作函数：
List.assign() 给list赋值
List.back() 返回最后一个元素
List.begin() 返回指向第一个元素的迭代器
List.clear() 删除所有元素
List.empty() 如果list是空的则返回true
List.end() 返回末尾的迭代器
List.erase() 删除一个元素
List.front() 返回第一个元素
List.get_allocator() 返回list的配置器
List.insert() 插入一个元素到list中
List.max_size() 返回list能容纳的最大元素数量
List.merge() 合并两个list
List.pop_back() 删除最后一个元素
List.pop_front() 删除第一个元素
List.push_back() 在list的末尾添加一个元素
List.push_front() 在list的头部添加一个元素
List.rbegin() 返回指向第一个元素的逆向迭代器
List.remove() 从list删除元素
List.remove_if() 按指定条件删除元素
List.rend() 指向list末尾的逆向迭代器
List.resize() 改变list的大小
List.reverse() 把list的元素倒转
List.size() 返回list中的元素个数
List.sort() 给list排序
List.splice() 合并两个list
List.swap() 交换两个list的内容
List.unique() 删除list中相邻重复的元素
list的定义
list<int> lst1; //创建一个空list
list<int> lst2(10); //创建一个含有10个元素的list
list<int> lst3(3,2); //创建含有3个元素2的list
list<int> lst4(lst2); //使用lst2初始化lst4
list<int> lst5(lst2.begin(),lst2.end()); //同lst4部分内容与栈那篇差不多，我们不讲。
ヽ(￣ω￣(￣ω￣〃)ゝ今天就到这，大家再见！。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/181574.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...