排列数(输出0~9的全排列)-蓝桥杯算法提高

问题描述
  0、1、2三个数字的全排列有六种,按照字母序排列如下:
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个(第1个为0123456789)。
输入格式
  一行,包含一个整数n
输出格式
  一行,包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
  0 < n <= 10!
分析:啊我才发现有一个超好用的库函数……完全不用自己实现全排列。。竟然自己还那么笨的用下面的深度优先搜索的办法……next_permutation函数。。在algorithm里面,代码如下:

下面是那个笨方法。。。
假设有10个位置,需要在10个位置上依次放置0~9这十个数字。
1.先走到第一个位置,此时放置一个当前可以放置的数字当中最小的那个数字。
2.在走到第二个位置,放置一个当前可以放置的数字当中最小的那个数字。

3.到第10个位置时候,所有的数字已经放置完毕,属于第一个全排列。
4.收回第10个位置上的数字,此时还是只可以放置9,那么再到第9个位置面前,收回位置上的数字。
5.在第9个位置处,我们此时可以放置的数字有9,那么第10个位置放8.属于第二个全排列。
6.收回第10、9、8位置的数字,此时可以在第8个位置放置8.

用一个数组标记当前的数字是否已经被使用过了。
int book[10]; //一开始的时候没有被使用,初始化值为0.使用过了之后标记为1.
int a[10]; // 表示这10个需要放置数字的位置。
深度优先搜索:

 

 

 

【C++ 与 STL】双端队列:deque

头文件 #include <deque>

常用方法:
a.push_front(0);//在头部加入数据0
a.push_back(11);//在尾部加入数据11
a.pop_front();//在头部删除数据
a.pop_back();//在尾部删除数据
a.resize(num);//重新指定队列的长度
a.size() //返回容器中实际数据个数
a.max_size() //返回容器中最大数据的数量

测试代码:

输入输出:
1 2 3 4 5 6 7 8 9 10
在头部加入数据0:
0 1 2 3 4 5 6 7 8 9 10
在尾部加入数据11:
0 1 2 3 4 5 6 7 8 9 10 11
在头部删除数据:
1 2 3 4 5 6 7 8 9 10 11
在尾部删除数据:
1 2 3 4 5 6 7 8 9 10
a.size() = 10
1 2 3 4 5 6 7 8 9 10 0
a.empty() = 0
a.max_size() = 4611686018427387903

【C++ 与 STL】栈:stack

栈的常用操作函数:
top()
push()
pop()
size()
empty()

【C++ 与 STL】映射:map

map提供了“[]”运算符,使得map可以像数组一样使用
所以map也称为关联数组
map就是从键(key)到值(value)的映射。
例如可以用一个map<string, int> month_name 来表示月份名字到月份编号的映射
然后用month_name[“July”] = 7 这样的方式来赋值

map的基本操作函数
begin() 返回指向map头部的迭代器
clear() 删除所有元素
count(elem) 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数


例题:反片语
输入一些单词,找出所有满足如下条件的单词:该单词不能通过字母重排,得到输入文本中的另外一个单词。
在判断是否满足条件时,字母不分大小写,但在输入时应保留输入中的大小写,按字典序进行排列(所有大写字母在小写字母的前面)
样例输入:
ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb eye Rides dealer NotE derail LaCeS drIed
noel dire Disk mace Rob dries
样例输出:
Disk
NotE
derail
drIed
eye
ladder
soon