字典序排序
字典序排序
在这次的文章中将会介绍关于字典序排序的一些内容(包括一道复盘题)，但是在讲述字典序题目前，我们先要知道什么是字典序，字典序是指按照ascii码值来进行排序的序列来形成一个有序的集合。
有个经典的例子，比如说这样一道题，有1，2，3这三个数，你要把它们所组成的三位数按照从小到大的顺序依次排列，想都不用想就知道可以排列成123，132，213，231，312，321这6种情况，但是放在程序中要怎么写呢，这就是我们要解决的问题，这道题可以用回溯算法，数组和宽度优先搜索来解决，对于每一个数字进行判断是否满足一定的要求，满足的话就放入一个新的序列，这就是字典序排序
两个最简单的函数
给我们指定5个数字，例如1 8 9 0 4，要找出这五个树中组成的某个数的上一个字典序对应的数是什么，通俗的说，就是告诉你18940后，你要立刻回答给我18904，这道题可以用一个字典序排序的函数来解决prev_permutation()这个函数就可以立刻对18940这个数进行排序，代码如下
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[5] = {1,8,9,4,0};
prev_permutation(a,a+5);
for(int i = 0;i < 5;i++){
printf("%d",a[i]);
}
return 0;
}同理，还有一个函数next_permutation()函数可以告诉你18940的下一个字典序对应的数是什么,代码如下
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[5] = {1,8,9,4,0};
next_permutation(a,a+5);
for(int i = 0;i < 5;i++){
printf("%d",a[i]);
}
return 0;
}组合数排序
但是，在面对一些题目时，这个函数也帮不到你，比如这道
给定两个整数 n和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]在面对此题时，我们只能采取别的方法
定义
首先，我们要定义一个n和k,同时我们要创建两个数组，一个用来记录每一种情况，一个用来把每一个情况存储起来
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N = 100010;
typedef long long ll;
int n,k;
//记录当前情况
vector<int> ans;
//存储每一种情况
vector<vector<int>> cnt;
void dfs(int n,int k,int u){
//算法分析
check();
}
int main(){
cin>>n>>k;
//1指的是第一位数是1
dfs(n,k,1);
//输出语法
cout<<?;
return 0;
}算法分析
现在，我们开始分析算法
我们通过例题可以知道，我们要找到的数是单调递增的，像12 23 34 14 这种，每个数从左到右的位数是单调递增的，所以我们要判断我们的数是否满足可以组成k位数
//判断是否可以组成k位数
if(ans.size() + (n - u + 1) < k)
return;
//进入循环则说明不可以找到组成k位数的了现在我们来分析怎样可以组成k位数
我们要先组12这个数，我们要看1有没有出现过
//没有出现过
ans.push_back(u);
//进入下一个循环
dfs(n,k,u+1);
//恢复现场
ans.pop_back();如果我们无法判定2是否出现过，我们可以把不出现也放上去
//不选择当前的数直接下一个循环
dfs(n,k,u+1);这样，选数的环节就已经搞定了
现在，我们要把选好的数的数组存起来
//保存所有的结果
if(ans.size() == k){
cnt.push_back(ans);
return;
}得出结果
输出
int main(){
cin>>n>>k;
//1指的是第一位数是1
dfs(n,k,1);
//输出语法
int n = cnt.size(),m = cnt[0].size();
for(int i = 0; i < n;i++){
for(int j = 0; j < m;j++){
cout<<cnt[i][j];
}
puts("");
}
return 0;
}现在，我们再来介绍第二种题型
全排列类排序
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]虽然题目是说可以任意顺序返回，但是我们可以写一个按照字典序返回的，同时还可以不需要STL中的vector容器(跑的实在是太快啦)
第二个是我用STL写的，跑的巨慢，虽然思路贼简单(只要给我足够的内存，我一定可以跑出来)
我们来介绍一下dfs，利用宽度搜索算法的思路来写这道题(后面会给出这道题的核心代码的STL形式)
其实，思路和第一个一样，都是看一下这个数有没有被搜索过了，没有的话就放上去
我们先把初始量定义好
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;
int a[N],b[N];
bool st[N];
int n;
void dfs(int u)
{
//算法设计
;
}
int main()
{
cin>>n;
for(int i = 0;i < n;i++){
cin>>b[i];
}
dfs(0);
return 0;
}算法设计
首先，我们要判断现在是否满足u == n，是的话我们就可以输出一种情况了
if(u == n){
for(int i = 0;i < n;i++) {
printf("%d ",a[i]);
}
puts("");
return;
}现在，我们要把满足的数一个一个输进去，但是在输进去前，我们要对数组进行排序
int main()
{
cin>>n;
for(int i = 0;i < n;i++){
cin>>b[i];
}
sort(b,b+n);
dfs(0);
return 0;
}排序后，我们进入dfs，开始循环
for(int i = 0;i < n;i++){
//如果这个数没有被用过
if(!st[i]){
//说明被用过
st[i] = true;
//加入数组
a[u] = b[i];
//进入下一个循环
dfs(u+1);
//恢复现场
st[i] = false;
}
}现在我们就把这道题解出来了
最后放出核心代码中的stl解法,使用的是回溯算法
void dfs(vector<vector<int>>& ans,vector<int>& nums,int u,int len){
//如果满足
if(u == len){
ans.push_back(nums);
return;
}
//插入数字
for(int i = u;i < len;i++){
//交换
swap(nums[i],nums[u]);
//进入下一个循环
dfs(ans,nums,u+1,len);
//恢复现场
swap(nums[i],nums[u]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
//定义二维vector数组
vector<vector<int>> ans;
//计算nums数组的长度
int len = nums.size();
//宽搜(回溯算法)
dfs(ans,nums,0,len);
//返回二维数组
return ans;
}
