使用 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 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告