• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【两万字精编~建议抱走】蓝桥杯算法竞赛系列第0章——蓝桥必考点及标准模板库STL(下)

互联网 diligentman 3小时前 3次浏览

欢迎回到:遇见蓝桥遇见你,不负代码不负卿!

目录

【补充】:常用头文件及库函数

1.#include

sscanf() 和 sprintf()

2.#include

3.#include

4.#include

(1).fabs(double x)

(2).pow(double r, double p)

(3).sqrt(double x)

5.#include

(1).strlen()

(2).strcmp()

(3).strcpy()

(4).strcat()

6.#include 

7.#include

8.#include

9.#include

一、string的常见用法详解

1.string的定义

2.string中内容的访问

(1).通过下标访问

(3).通过迭代器访问

3.string常用函数实例解析

(1).operator+=

(2).compare operator

(3).length() / size()

(4).insert()

(5).erase()

(6).clear()

(7).substr()

(8).string::npos

(9).find()

(10).replace()

二、queue的常见用法详解

1.queue的定义

2.queue容器内元素的访问

3.queue常用函数实例解析

(1).push()

(2).front(), back()

(3).pop()

(4).empty()

(5).size()

三、stack的常见用法详解

1.stack的定义

2.stack容器内元素的访问

3.stack常用函数实例解析

(1).push()

(2).top()

(3).pop()

(4).empty()

(5).size()

四、algorithm头文件下的常用函数

1.max()、min()和abs()

2.swap()

3.reverse()

4.next_permutation()

5.fill()

6.sort()

<1>.基本数据类型数组的排序

<2>.结构体数组的排序

<3>.容器的排序

7.lower_bound()和upper_bound()

五、蓝桥结语:遇见蓝桥遇见你,不负代码不负卿!


【前言】

这篇是上次文章的后续哦,铁汁们可以先回顾一下上篇的内容。

蓝桥杯算法竞赛系列第0章——蓝桥必考点及标准模板库STL(上)(万字博文,建议抱走)_安然无虞的博客-CSDN博客

上次有好几位铁汁建议我多换点图片,表示看腻了,也有不少热心小友私发给了我一些,但是由于格式大小的问题,能用的不多,不过在这里还是要特别感谢一下哈,抱拳啦。

【两万字精编~建议抱走】蓝桥杯算法竞赛系列第0章——蓝桥必考点及标准模板库STL(下)

【补充】:常用头文件及库函数

  • #include<stdio.h>
  • #include<stdlib.h>
  • #include<time.h>
  • #include<math.h>
  • #include<string.h>
  • #include<vector>
  • #include<string>
  • #include<queue>
  • #include<stack>
  • #include<algorithm>

1.#include<stdio.h>

  • scanf()
  • printf()
  • getchar()
  • putchar()
  • gets()
  • puts()
  • sscanf()
  • sprintf()

标准输入输出头文件,当然除了scanf() 和 printf() 很重要外,sscanf() 和 sprintf()也是非常重要的,对于这两个库函数,老师从未讲过,但是看题解时经常出现,它们是用来处理字符串的利器。待会再谈它们,先讲一下scanf() 的弊端,对于scanf() 函数,不能读入空格,遇到空格就结束了,所以处理起字符串就很不方便。所以这里还有两个库函数用来处理字符串:gets() 和 puts() , gets() 用来输入一行字符串,识别'n' 结束,遇到空格不会结束哦,puts() 用来输出一行字符串,并且紧跟一个换行,对于putchar()和getchar() 用得不多,有兴趣可自行了解哦。

sscanf() 和 sprintf()

sscanf() 与 sprintf() 是处理字符串问题的利器,我们很有必要学会它们(sscanf() 从单词上可理解为 string + scanf , sprintf 则可理解为 string + printf, 均在stdio.h 头文件下) 。先来回顾一下scanf() 和 printf(), 如果想要从屏幕上输入int 型变量n 并将int 型变量 n 输出到屏幕上,则可以写成下面这样:

scanf("%d", &n);
printf("%d", n);

事实上,上面的写法其实可以表示成下面的样子,其中screen 表示屏幕:

scanf(screen, "%d", &n);
printf(screen, "%d", n);

可以发现,scanf() 的输入其实是把screen 的内容以"%d" 的格式传输到n 中(即从左至右),而printf() 的输出则是把n 以“%d” 的格式传输到screen 上(即从右至左)

sscanf() 和 sprintf() 与上面的格式是相同的,只不过把screen 换成了字符数组(假设定义了一个char 数组 str[100]),如下所示:

sscanf(str, "%d", &n);
sprintf(str, "%d", n);

上面的sscanf() 写法的作用是把字符数组str 中的内容以"%d" 的格式写到n 中(还是从左至右)

示例如下:

#include<stdio.h>

int main()
{
	int n = 0;
	char str[100] = "123";
	sscanf(str, "%d", &n);

	printf("%dn", n);//输出123

	return 0;
}

而sprintf() 写法的作用是把n 以"%d" 的格式写到str 字符数组中(还是从右至左)

示例如下:

#include<stdio.h>

int main()
{
	int n = 233;
	char str[100];
	sprintf(str, "%d", n);
	printf("%sn", str);//输出233
	return 0;
}

上面只是一些简单的应用,事实上,可以像使用scanf() 和 printf() 那样进行复杂的格式的输入和输出。例如下面的代码使用sscanf() 将字符数组str 中的内容按"%d:%lf,%s"的格式写到int 型变量n、double 型变量db、char型数组str2中

#include<stdio.h>

int main()
{
	int n;
	double db;
	char str[100] = "2048:3.14,hello", str2[100];
	sscanf(str, "%d:%lf,%s", &n, &db, str2);
	printf("n = %d, db = %lf, str2 = %sn", n, db, str2);
	return 0;
}

类似的,下面的代码使用sprintf() 将int 型变量n 、double 型变量db、char 型数组str2 按"%d:%lf,%s" 的格式写到字符数组str 中

#include<stdio.h>

int main()
{
	int n = 12;
	double db = 3.1415;
	char str[100], str2[100] = "good";
	sprintf(str, "%d:%.2lf,%s", n, db, str2);
	printf("str = %sn", str);
	return 0;
}

2.#include<stdlib.h>

主要用于生成随机数以及动态内存开辟,常用的库函数有srand((unsigned int) time(NULL)),rand() 和动态内存开辟用的malloc(),用new会更简单一些

3.#include<time.h>

上面生成随机数的时候,常用time()函数用于生成时间戳,作为随机数种子

4.#include<math.h>

  • fabs()
  • sqrt()
  • pow()
  • floor()
  • ceil()
  • round()

用数学函数可以节省大量的时间,所以一定要记住,对于很常用的其实也就是fabs()、sqrt()和pow()

(1).fabs(double x)

该函数用于对double 型变量取绝对值。

(2).pow(double r, double p)

该函数用于返回 r ^ p ,要求r 和 p 都是double类型的

(3).sqrt(double x)

该函数用于返回double型变量的算数平方根

在这里就只简单介绍这三个最常用的。

5.#include<string.h>

  • strlen()
  • strcmp()
  • strcpy()
  • strcat()

(1).strlen()

strlen()函数可以得到字符数组中第一个之前的字符的个数

(2).strcmp()

strcmp()函数返回两个字符串大小的比较结果,比较原则是按字典序,所谓字典序就是字符串在字典中的顺序,因此如果有两个字符数组str 1 和 str 2, 且满足str 1[0…k – 1] == str 2[0…k – 1]、str1[k] < str2[k], 那么就说str 1的字典序小于str2。例如"a" 的字典序小于"b"、"aaaa" 的字典序小于"aab"

strcmp()函数的返回值:

  • 如果字符数组1 < 字符数组2,则返回一个负整数(不一定是-1,由编译器决定)
  • 如果字符数组1 == 字符数组2,则返回0
  • 如果字符数组1 > 字符数组2,则返回一个正整数(不一定是1,由编译器决定)

(3).strcpy()

strcpy()函数可以把一个字符串复制给另一个字符串,格式如下:

strcpy(字符数组1,字符数组2);

注意哦,是把字符数组2复制给字符数组1,这里的“复制” 包括了结束标志  

示例如下:

#include<stdio.h>
#include<string.h>

int main()
{
	char str1[50] = "Thank";
	char str2[50] = "you for your smile.";
	strcpy(str1, str2);
	puts(str1);//输出you for your smile.
	//printf("%sn", str1);
	return 0;

}

(4).strcat()

strcat()可以把一个字符串拼接到另一个字符串的后面

strcat(字符数组1, 字符数组2);

注意哦,是把字符数组2拼接到字符数组1的后面 

示例如下:

#include<stdio.h>
#include<string.h>

int main()
{
	char str1[50] = "Thank";
	char str2[50] = "you for your smile.";
	strcat(str1, str2);
	puts(str1);//输出 Thankyou for your smile.
	//printf("%sn", str1);
	return 0;
	return 0;
}

6.#include<vector> 

常用函数:

  • push_back()
  • pop_back()
  • size()
  • clear()

7.#include<queue>

常用函数

  • push()
  • pop()
  • front()
  • back()
  • empty()
  • size()

8.#include<stack>

常用函数:

  • push()
  • pop()
  • top()
  • empty()
  • size()

9.#include<algorithm>

常用函数:

  • max()
  • min()
  • swap()
  • fill()
  • sort()

【两万字精编~建议抱走】蓝桥杯算法竞赛系列第0章——蓝桥必考点及标准模板库STL(下)

下面在介绍一些常见的容器: 

一、string的常见用法详解

在C语言中,一般使用字符数组char str[ ] 来存放字符串,但是使用字符数组有时会显得操作麻烦,而且容易因经验不足产生错误,得不偿失。为了使编程者可以更方便的对字符串进行操作,C++在STL中加入了string类型,对字符串常用的需求功能进行了封装,使得操作起来更方便,且不易出错。

如果要使用string,需要添加string头文件,即#include<string>(注意string.h 和 string 是不一样的头文件)。除此之外,还需要在头文件下面加上一句:"using namespace std;", 这样就可以在代码中使用string了。下面来看string的一些常见用法。

1.string的定义

定义string的方式跟基本数据类型相同,只需要在string后面跟上变量名即可:

string str;

如果要初始化,可以直接给string类型的变量进行赋值:

string str = "abcd"

2.string中内容的访问

(1).通过下标访问

一般来说,可以直接像字符数组那样去访问string:

#include<stdio.h>
#include<string>
using namespace std;

int main()
{
	string str = "abcd";
	for (int i = 0; i < str.length(); i++)
	{
		printf("%c ", str[i]);//输出a b c d
	}
	return 0;
}

注意哦,如果要读入和输出整个字符串,则只能用cin 和  cout:

#include<iostream>//cin和cout在iostream头文件中,而不是stdio.h
#include<string>

using namespace std;
int main()
{
	string str;
	cin >> str;
	cout << str;

	return 0;
}

上面的代码对任意的字符串输入,都会输出同样的字符串。

那么,真的没有办法用printf来输出string吗?其实是有的,即用c_str()将string类型转换为字符数组进行输出,示例如下:

#include<stdio.h>
#include<string>

using namespace std;

int main()
{
	string str = "abcd";
	printf("%sn", str.c_str());//将string型str使用c_str()变成字符数组
	return 0;
}

(3).通过迭代器访问

一般仅通过(1)即可满足访问的要求,但是有些函数比如insert()与erase()则要求以迭代器为参数,因此还是需要学习一下string迭代器的用法。

由于string不像其他STL容器那样需要参数,因此可以直接入下定义:

string::iterator it;

这样就得到了迭代器it, 并且可以通过*it 来访问string里的每一位:

#include<stdio.h>
#include<string>

using namespace std;

int main()
{
	string str = "abcd";
	for (string::iterator it = str.begin(); it != str.end(); it++)
	{
		printf("%c ", *it);//输出a b c d
	}
	return 0;
}

最后指出,string和vector一样,支持直接对迭代器进行加减某个数字,如str.begin() + 3的写法是可行的

3.string常用函数实例解析

  • operator+=
  • compare operator
  • length() / size()
  • insert()
  • erase()
  • clear()
  • substr()
  • string::nops
  • find()
  • replace()

(1).operator+=

这是string的加法,可以将两个string直接拼接起来

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str1 = "abc", str2 = "xyz", str3;
	str3 = str1 + str2;//将str1和str2拼接,赋值给str3
	str1 = str1 + str2;//将str2直接拼接到str1上

	cout << str1 << endl;//输出abcxyz
	cout << str3 << endl;//输出abcxyz

	return 0;
}

(2).compare operator

两个string类型可以直接使用==、!=、<、<=、>、>=比较大小,比较规则是字典序。

示例如下:

#include<stdio.h>
#include<string>

using namespace std;

int main()
{
	string str1 = "aa", str2 = "aaa", str3 = "abc", str4 = "xyz";
	if (str1 < str2)//如果str1字典序小于str2,输出ok1
	{
		printf("ok1n");//输出ok1
	}

	if (str1 != str3)//如果str1和str3字典序不等,输出ok2
	{
		printf("ok2n");//输出ok2
	}

	if (str4 >= str3)//如果str4字典序大于等于str3,输出ok3
	{
		printf("ok3n");//输出ok3
	}
	return 0;
}

(3).length() / size()

length()返回string的长度,即存放的字符数。时间复杂度为O(1)。size()与length()基本相同

示例如下:

string str = "abcdef";
printf("%d %dn", str.length(), str.size());//输出6 6

(4).insert()

string的insert()函数有很多种写法,这里给出几种常用的写法。时间复杂度为O(N)

1.insert(pos, string), 在pos号位置插入一个字符串string

示例如下:

string str = "abcxyz", str2 = "opq";
str.insert(3, str2);//往str[3]处插入opq,将括号里的str2直接写成"opq"也是可以的
cout<<str<<endl;//输出abcopqxyz

2.insert(it, it2, it3), it 为原字符串的欲插入位置,it2 和 it3 为待插字符串的首尾迭代器,用来表示串[it2, it3)将被插在it 的位置上

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "abcxyz", str2 = "opq";//str为原字符串,str2为待插字符串
	//在str的3号位(即c和x之间)插入str2
	str.insert(str.begin() + 3, str2.begin(), str2.end());
	cout << str << endl;//输出abcopqxyz
	return 0;
}

(5).erase()

erase()有两种用法:删除单个元素、删除一个区间内的所有元素。时间复杂度均为O(N)

1.删除单个元素:str.erase(it) 用于删除单个元素,it为需要删除的元素的迭代器

示例如下:

#include<iostream>
#include<stdio.h>

using namespace std;
int main()
{
	string str = "abcdefg";
	str.erase(str.begin() + 4);//删除4号位(即e)
	cout << str << endl;//输出abcdfg
	return 0;
}

2.删除一个区间内的所有元素:有两种方法:

  • str.erase(first, last), 其中first为需要删除的区间的起始迭代器,而last为需要删除的区间的末尾迭代器的下一个地址,即为删除[first, last)

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "abcdefg";
	//删除在[str.begin() + 2, str.end() - 1)内的元素,即cdef
	str.erase(str.begin() + 2, str.end() - 1);
	cout << str << endl;//输出abg
	return 0;
}
  • str.erase(pos, length), 其中pos为需要开始删除的起始位置,length为删除的字符个数。

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "abcdefg";
	str.erase(3, 2);//删除de
	cout << str << endl;//输出abcfg
	return 0;
}

(6).clear()

clear()可以清空string中的数据,时间复杂度一般为O(1)

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "abcd";
	str.clear();//清空字符串
	cout << str.length() << endl;//输出0
	return 0;
}

(7).substr()

substr(pos, len) 返回从pos号位开始、长度为len的子串,时间复杂度为O(len)

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "Thank you for your smile.";
	cout << str.substr(0, 5) << endl;//输出Thank
	cout << str.substr(14, 4) << endl;//输出your
	cout << str.substr(19, 5) << endl;//输出smile
	return 0;
}

(8).string::npos

string::npos是一个常数,其本身的值为-1 ,但由于是unsigned int 类型,因此实际上也可以认为是unsigned int 类型的最大值,可认为是4,294,967,295。string::npos 用以作为 find 函数失配时的返回值。

(9).find()

str.find(str) 当str2 是str 的子串时,返回其在str 中第一次出现的位置,如果str2 不是str 的子串,那么返回string::npos

str.find(str2, pos), 从str 的pos 号位开始匹配str2,返回值与上相同。时间复杂度为O(M*N),M和N 分别是str2 和str的长度

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "Thank you for your smile";
	string str2 = "you";
	string str3 = "me";
	if (str.find(str2) != string::npos)
	{
		cout << str.find(str2) << endl;//输出6
	}
	if (str.find(str2, 7) != string::npos)
	{
		cout << str.find(str2, 7) << endl;//输出14
	}
	if (str.find(str3) != string::npos)
	{
		cout << str.find(str3) << endl;
	}
	else
	{
		cout << "I know there is no position for me." << endl;
	}
	return 0;
}

(10).replace()

str.replace(pos,len,str2) 把str 从pos 号位开始、长度为len 的子串替换为上str2

str.replace(it1,it2,str2) 把str 的迭代器[it1, it2)范围的子串替换为str2

示例如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str = "Maybe you will turn around.";
	string str2 = "will not";
	string str3 = "surely";
	cout << str.replace(10, 4, str2) << endl;
	cout << str.replace(str.begin(), str.begin() + 5, str3) << endl;
	return 0;
}

二、queue的常见用法详解

queue翻译为队列,在STL中主要则是实现一个先进先出的容器,当需要实现广度优先搜索时,可以不用自己手动实现一个队列,而是用queue代替,以提高程序的准确性。

1.queue的定义

要使用queue, 需要先添加头文件#include<queue>, 并在头文件下面加上"using namespace std;" ,然后就可以使用了。

其定义的写法和其他STL容器相同,typename 可以是任意基本数据类型和容器:

queue<typename> name;

2.queue容器内元素的访问

由于队列(queue)本身就是一种先进先出的限制性数据结构,因此在STL中只能通过front() 来访问队首元素,或是通过back() 来访问队尾元素。

示例如下:

#include<stdio.h>
#include<queue>

using namespace std;

int main()
{
	queue<int> q;
	for (int i = 1; i <= 5; i++)
	{
		q.push(i);//push(i)用以将i压入队列,因此依次入队1 2 3 4 5 
	}
	printf("%d %dn", q.front(), q.back());//输出结果为1 5
	return 0;
}

3.queue常用函数实例解析

  • push()
  • front()
  • back()
  • pop()
  • empty()
  • size()

(1).push()

push(x) 将x 进行入队,时间复杂度为O(1)

(2).front(), back()

front(), back()可以分别获得队首元素和队尾元素,时间复杂度为O(1)

注意哦,使用front() 和 pop() 函数之前,必须用empty() 判断队列是否为空,否则可能会因为队列空导致错误

(3).pop()

pop()令队首元素出队,时间复杂度为O(1)

示例如下:

#include<stdio.h>
#include<queue>

using namespace std;

int main()
{
	queue<int> q;
	for (int i = 1; i <= 5; i++)
	{
		q.push(i);
	}
	for (int i = 0; i < 3; i++)
	{
		q.pop();//出队列元素3次,依次出队1 2 3
	}
	printf("%dn", q.front());//输出4
	return 0;
}

(4).empty()

empty()检测queue是否为空,返回true则为空,返回false则非空,时间复杂度为O(1)

示例如下:

#include<stdio.h>
#include<queue>

using namespace std;

int main()
{
	queue<int> q;
	if (q.empty() == true)//一开始队列里没有元素,所以是空
	{
		printf("Emptyn");
	}
	else
	{
		printf("Not Emptyn");
	}
	q.push(1);
	if (q.empty() == true)
	{
		printf("Emptyn");
	}
	else
	{
		printf("Not Emptyn");
	}
	return 0;
}

(5).size()

size()返回queue内元素的个数,时间复杂度为O(1)

示例如下:

#include<stdio.h>
#include<queue>

using namespace std;

int main()
{
	queue<int> q;
	for (int i = 1; i <= 5; i++)
	{
		q.push(i);
	}
	printf("%dn", q.size());//输出5
	return 0;
}

【延伸】:STL容器中还有两种容器跟队列有关,分别是双端队列(deque) 和优先队列(priority_queue) ,前者是首尾皆可插入和删除的队列,后者是使用堆实现的默许将当前队列最大元素置于队首的容器,这里暂时先不介绍,后期如果需要再进行补充。

三、stack的常见用法详解

stack 翻译为栈,是STL中实现的一个先进后出的容器,stack 用来模拟实现一些递归,防止程序对栈内存的限制而导致程序运行出错。

1.stack的定义

要使用stack,应先添加头文件#include<stack>, 并在头文件下面加上" using namespace std;",然后就可以使用了。

其定义的写法和其他STL容器相同,typename可以是任意基本数据类型或容器:

stack<typename> name;

2.stack容器内元素的访问

由于栈(stack) 本身就是一种先进后出的数据结构,在STL的stack 中只能通过top() 来访问栈顶元素

示例如下:

#include<stdio.h>
#include<stack>

using namespace std;

int main()
{
	stack<int> st;
	for (int i = 1; i <= 5; i++)
	{
		st.push(i);//依次入栈1 2 3 4 5
	}
	printf("%dn", st.top());//输出5
	return 0;
}

3.stack常用函数实例解析

  • push()
  • top()
  • pop()
  • empty()
  • size()

(1).push()

push(x) 将x 入栈,时间复杂度为O(1),

(2).top()

top()获得栈顶元素,时间复杂度为O(1)

(3).pop()

pop()用以弹出栈顶元素,时间复杂度为O(1)

示例如下:

#include<stdio.h>
#include<stack>

using namespace std;

int main()
{
	stack<int> st;
	for (int i = 1; i <= 5; i++)
	{
		st.push(i);
	}
	for (int i = 0; i < 3; i++)
	{
		st.pop();
	}
	printf("%dn", st.top());//输出2
	return 0;
}

(4).empty()

empty()可以检测stack 内是否为空,返回true 为空,返回false 为非空,时间复杂度为O(1)

(5).size()

size()返回stack 内元素的个数,时间复杂度为O(1)

四、algorithm头文件下的常用函数

使用algorithm 头文件,需要在头文件下面加上一行"using namespace std;",才能正常使用

  • max()、min()、abs()
  • swap()
  • reverse()
  • next_permutation()
  • fill()
  • sort()
  • lower_bound() 和 upper_bound()

1.max()、min()和abs()

max(x,y)和min(x,y) 分别返回x, y中的最大值和最小值,且参数必须是两个,可以是浮点数,如果想返回三个数x,y,z的最大值,可以使用max(x, max(y, z)) 的写法;abs(x) 返回x的绝对值。注意:此时的x 必须是整数,浮点数的绝对值请用math 头文件下的fabs

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int x = -1;
	int y = -2;
	printf("%d %dn", max(x, y), min(x, y));//输出-1 -2
	printf("%d %dn", abs(x), abs(y));//输出1 2
	return 0;
}

2.swap()

swap(x, y) 用来交换x 和 y 的值

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int x = 10;
	int y = 20;
	swap(x, y);
	printf("%d %dn", x, y);//输出20 10
	return 0;
}

3.reverse()

reverse(it, it2) 可以将数组指针在[it, it2) 之间的元素或容器的迭代器在[it, it2) 范围内的元素进行反转

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int arr[10] = { 10,11,12,13,14,15 };
	reverse(arr, arr + 4);//将arr[0]~arr[3]反转
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);//输出13,12,11,10,14,15
	}

	return 0;
}

如果要是对容器中的元素(例如string 字符串)进行反转,结果也是一样

示例如下:

#include<stdio.h>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	string str = "abcdefghi";
	reverse(str.begin() + 2, str.begin() + 6);//对str[0]~str[5]反转
	for (int i = 0; i < str.length(); i++)
	{
		printf("%c", str[i]);//输出abfedcghi
	}
	return 0;
}

4.next_permutation()

next_permutation() 给出一个序列在全排列中得下一个序列

例如,当n == 3 时的全排列为:

123

132

213

231

312

321

这样231的下一个序列就是312

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int a[10] = { 1,2,3 };
	//a[0]~a[2]之间的序列需要求解next_permutation
	do
	{
		printf("%d%d%dn", a[0], a[1], a[2]);
	} while (next_permutation(a, a + 3));
	return 0;
}

在上述的代码中,使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false, 这样会方便退出循环。而使用do…while语句而不使用while语句是因为序列1 2 3本身也需要输出,如果使用while会直接跳到下一个序列再输出,这样的话结果会少一个123

5.fill()

fill()可以把数组或容器中的某一段区间赋为某个相同的值。和memset 不同,这里的赋值可以是数组类型对应范围中的任意值

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int a[5] = { 1,2,3,4,5 };
	fill(a, a + 5, 133);//将a[0]~a[4]均赋值为133
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);//输出133 133 133 133 133
	}
	return 0;
}

6.sort()

顾名思义,sort()就是用来排序的函数,它根据具体情形使用不同的排序方法,效率较高。一般来说,不推荐使用C语言中的qsort函数,原因是qsort 用起来比较繁琐,涉及很多指针的操作。

sort函数的使用必须加上头文件"#include<algorithm>" 和 "using namespace std;",其使用的方式如下:

sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填));

可以看到,sort的参数有三个,其中前两个是必填的,而比较函数则可以根据需要填写,如果不写比较函数,则默认对前面给出的区间进行递增排序。

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int a[6] = { 9,4,2,5,6,-1 };
	//将a[0]~a[3]进行从小到大排序
	sort(a, a + 4);
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", a[i]);//输出2 4 5 9 6 -1
	}
	putchar('n');
	//将a[0]~a[5]进行从小到大排序
	sort(a, a + 6);
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", a[i]);//输出-1 2 4 5 6 9
	}
	return 0;
}

【敲黑板】:特别需要注意理解的是尾元素地址的下一个地址!

对double数组进行排序:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	double a[] = { 1.4,-2.1,9 };
	sort(a, a + 3);
	for (int i = 0; i < 3; i++)
	{
		printf("%.1lf ", a[i]);
	}
	return 0;
}

对char型数组进行排序(默认是字典序)

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	char c[] = { 'T', 'W','A', 'K' };
	sort(c, c + 4);
	for (int i = 0; i < 4; i++)
	{
		printf("%c", c[i]);//输出AKTW
	}
	return 0;
}

我们需要知道的是,如果对序列进行排序,那么序列中的元素一定要有可比性,因此需要制定排序规则来建立这种可比性。特别是像结构体,本身并没有大小关系,需要认为制定比较的规则。sort 的第三个可选参数就是cmp函数,用来实现这个规则。

  • 如何实现比较函数cmp

下面介绍对基本数据类型、结构体类型、STL容器进行自定义规则排序时cmp的写法。

<1>.基本数据类型数组的排序

若比较函数不填,则默认按照从小到大的顺序排序。

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int a[] = { 3,1,4,2 };
	sort(a, a + 4);
	for (int i = 0; i < 4; i++)
	{
		printf("%d ", a[i]);//输出1 2 3 4
	}
	return 0;
}

如果想要从大到小来排序,则要使用比较函数cmp 来“告诉”sort 何时要交换元素(让元素的大小比较关系反过来)

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

bool cmp(int a, int b)
{
	return a > b;//可以理解为当a>b时把a放在b前面
}

int main()
{
	int a[] = { 3,1,4,2 };
	sort(a, a + 4, cmp);
	for (int i = 0; i < 4; i++)
	{
		printf("%d ", a[i]);//输出4 3 2 1
	}

	return 0;
}

这样就可以让数值较大的元素放在前面,也就达到了从大到小排序的要求。

同样的,对double型数组从大到小排序的代码如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

bool cmp(double a, double b)
{
	return a > b;//同样是a>b
}

int main()
{
	double a[] = { 1.4,-2.1,9 };
	sort(a, a + 3, cmp);
	for (int i = 0; i < 3; i++)
	{
		printf("%.1lf ", a[i]);//输出9.0 1.4 -2.1
	}
	return 0;
}

对char型数组从大到小排序如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

bool cmp(char a, char b)
{
	return a > b;//可以理解为当a>b时把a放在b之前
}

int main()
{
	char c[] = { 'T','W','A','K' };
	sort(c, c + 4, cmp);
	for (int i = 0; i < 4; i++)
	{
		printf("%c", c[i]);//输出WTKA
	}
	return 0;
}

【记忆方法】:

如果要把数据从小到大排列,那么就用'<', 因为"a<b" 就是左小右大;如果要把数据从大到小排列,那么就用'>', 因为"a>b" 就是左大右小。而当不确定或者忘记的时候,不妨两种都试一下,就会知道该用哪种了。

<2>.结构体数组的排序

现在定义了如下结构体:

struct node{
    int x, y;
}ssd[10];

如果想将ssd数组按照 x 从大到小排序(即进行一级排序),那么可以这样写cmp函数:

bool cmp(node a, node b){
    return a.x > b.x;
}

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

struct node
{
	int x;
	int y;
}ssd[10];

bool cmp(node a, node b)
{
	return a.x > b.x;//按x值从大到小对结构体数组进行排序
}

int main()
{
	ssd[0].x = 2;
	ssd[0].y = 2;
	ssd[1].x = 1;
	ssd[1].y = 3;
	ssd[2].x = 3;
	ssd[2].y = 1;
	sort(ssd, ssd + 3, cmp);
	for (int i = 0; i < 3; i++)
	{
		printf("%d %dn", ssd[i].x, ssd[i].y);
	}
	return 0;
}

而如果想先按x 从大到小排序,但当x相等的情况下,按照y的大小从小到大来排序(即进行二级排序),那么cmp的写法是:

bool cmp(node a, node b)
{
    if(a.x != b.x)
    {
        return a.x > b.x;
    }
    else
    {
        return a.y < b.y;
    }
}

这里的cmp函数首先判断结构体内的x 元素是否相等,如果不相等则直接按照x 的大小来排序,否则,按照y 的大小来排序。

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

struct node
{
	int x;
	int y;
}ssd[10];

bool cmp(node a, node b)
{
	if (a.x != b.x)
	{
		return a.x > b.x;//x 不等时按x 从大到小排序
	}
	else
	{
		return a.y < b.y;//x 相等时按y 从小到大排序
	}
}
int main()
{
	ssd[0].x = 2;
	ssd[0].y = 2;
	ssd[1].x = 1;
	ssd[1].y = 3;
	ssd[2].x = 3;
	ssd[2].y = 1;
	sort(ssd, ssd + 3, cmp);//排序

	for (int i = 0; i < 3; i++)
	{
		printf("%d %dn", ssd[i].x, ssd[i].y);
	}
	return 0;
}

<3>.容器的排序

在STL标准容器中,只有vector、string、deque是可以使用sort的。这是因为像set、map这种容器是用红黑树实现的(了解即可),元素本身有序,故不允许使用sort排序

vector示例如下:

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(int a, int b)//因为vector中的元素为int型,因此仍然是int的比较
{
	return a > b;
}


int main()
{
	vector<int> vi;
	vi.push_back(3);
	vi.push_back(1);
	vi.push_back(2);
	sort(vi.begin(), vi.end(), cmp);
	for (vector<int>::iterator it = vi.begin(); it != vi.end(); it++)
	{
		printf("%d ", *it);//输出3 2 1
	}
	return 0;
}

再来看string 的排序,示例如下:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	string str[3] = { "bbbb", "cc", "aaa" };
	sort(str, str + 3);//将string数组按字典树从小到大输出
	for (int i = 0; i < 3; i++)
	{
		cout << str[i] << endl;
	}

	return 0;
}

如果上面这个例子中,需要按照字符串长度从小到大排序,那么可以这样写:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

bool cmp(string str1, string str2)
{
	return str1.length() < str2.length();//按照string 的长度从小到大排序
}

int main()
{
	string str[3] = { "bbbb", "cc", "aaa" };
	sort(str, str + 3, cmp);
	for (int i = 0; i < 3; i++)
	{
		cout << str[i] << endl;
	}

	return 0;
}

7.lower_bound()和upper_bound()

lower_bound() 和 upper_bound() 需要用在一个有序数组或容器中

lower_bound(first, last, val) 用来寻找在数组或容器的[first, last) 范围内第一个值大于等于val元素的位置,如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器。

upper_bound(first, last, val) 用来寻找在数组或容器的[first, last) 范围内第一个值大于val 的元素的位置,如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器。

显然,如果数组或容器中没有需要寻找的元素,则lower_bound() 和 upper_bound() 均返回可以插入该元素的位置的指针或迭代器(即假设存在该元素时,该元素应当在的位置)。

示例如下: 

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int a[10] = { 1,2,2,3,3,3,5,5,5,5 };
	//寻找-1
	int* lowerPos = lower_bound(a, a + 10, -1);
	int* upperPos = upper_bound(a, a + 10, -1);
	printf("%d %dn", lowerPos - a, upperPos - a);//输出0 0

	//寻找1
	lowerPos = lower_bound(a, a + 10, 1);
	upperPos = upper_bound(a, a + 10, 1);
	printf("%d %dn", lowerPos - a, upperPos - a);//输出0 1

	//寻找3
	lowerPos = lower_bound(a, a + 10, 3);
	upperPos = upper_bound(a, a + 10, 3);
	printf("%d %dn", lowerPos - a, upperPos - a);//输出3 6

	//寻找4
	lowerPos = lower_bound(a, a + 10, 4);
	upperPos = upper_bound(a, a + 10, 4);
	printf("%d %dn", lowerPos - a, upperPos - a);//输出6 6

	//寻找6
	lowerPos = lower_bound(a, a + 10, 6);
	upperPos = upper_bound(a, a + 10, 6);
	printf("%d %dn", lowerPos - a, upperPos - a);//输出10 10
	return 0;
}

显然,如果只想获得欲查元素的下标,就可以不使用临时指针,而直接令返回值减去数组首地址即可。

【敲黑板】:这里补充一条知识点,指针 – 指针  = 两指针之间的元素个数

示例如下:

#include<stdio.h>
#include<algorithm>

using namespace std;

int main()
{
	int a[10] = { 1,2,2,3,3,3,5,5,5,5 };
	//寻找3
	printf("%d %dn", lower_bound(a, a + 10, 3) - a, upper_bound(a, a + 10, 3) - a);//输出3 6
	return 0;
}

五、蓝桥结语:遇见蓝桥遇见你,不负代码不负卿!

希望能给大家带来帮助,码字不易,如果可以动动小手来个三连那就更好啦,hh,咱们下次再见。

·【两万字精编~建议抱走】蓝桥杯算法竞赛系列第0章——蓝桥必考点及标准模板库STL(下)


喜欢 (0)