数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 对前 N 个数字的排列进行最小前缀反转排序
描述
给定一个包含 N 个数字的数组，这些数字是前 N 个数字的排列。在一次操作中，可以反转任何前缀。任务是找到使数组中的数字按升序排序所需的此类操作的最小数量。
示例
如果数组是 {1, 2, 4, 3}，则需要至少 3 步才能将数组按升序排序：
- 反转整个数组 {3, 4, 2, 1}
- 反转前两个元素 {4, 3, 2, 1}
- 反转整个数组 {1, 2, 3, 4}
算法
- 将给定的数字编码成字符串。对数组进行排序，并将其编码成字符串 destination。
- 然后从初始排列开始进行广度优先搜索 (BFS)。每次检查由反转当前排列的前缀引起的所有排列。
- 如果它没有被访问过，则将其放入队列中，并记录已执行的反转次数。
- 当编码字符串的排列与 destination 字符串相同时，返回到达这里的所需反转次数。
- 也就是说，所有字符串的排列都已完成，并将这些排列中的最小值作为答案返回。
示例
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
string start = "";
string destination = "", t, r;
for (int i = 0; i < n; i++) {
start += to_string(a[i]);
}
sort(a, a + n);
for (int i = 0; i < n; i++) { destination += to_string(a[i]);
}
queue<pair<string, int> > qu;
pair<string, int> p;
qu.push(make_pair(start, 0));
if (start == destination) {
return 0;
}
while (!qu.empty()) {
p = qu.front();
t = p.first;
qu.pop();
for (int j = 2; j <= n; j++) {
r = t;
reverse(r.begin(), r.begin() + j);
if (r == destination) {
return p.second + 1;
}
qu.push(make_pair(r, p.second + 1));
}
}
}
int main() {
int a[] = { 1, 2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl;
return 0;
}输出
编译并执行上述程序时，将生成以下输出：
Minimum reversal: 3
更新于: 2019年11月22日
211 次查看
广告