資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告