给定一个N个数字的数组,这些数组具有前N个数字的排列。在单个操作中,任何前缀都可以颠倒。任务是找到此类操作的最小数量,以使数组中的数字按升序排序。
如果array为{1,2,4,3},则至少需要3个步骤才能对数组进行升序排序-
反转整个数组{3,4,2,1}
颠倒前两个元素{4,3,2,1}
反转整个数组{1,2,3,4}
将给定数字编码为字符串。对数组进行排序,并将其编码为字符串目标。
然后从初始排列开始进行BFS。每次检查由反向当前排列前缀引起的所有排列。
如果未访问,则将其放入已完成反转计数的队列中。
当编码字符串的排列与目标字符串相同时,返回到达此处所需的反转次数
也就是说,完成了字符串的所有排列,并返回了其中的最小值作为答案。
#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