資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中使所有字串相等所需的最小移動次數
問題陳述
給定 n 個字串，它們彼此之間是排列關係。我們需要透過一個操作使所有字串都相同，該操作將任何字串的第一個字元移動到該字串的末尾。
示例
如果 arr[] = {“abcd”, “cdab”}，則需要 2 次移動。
- 讓我們取第一個字串“abcd”。將字元‘a’移動到字串的末尾。此操作後，字串變為“bcda”
- 現在將字元‘b’移動到字串的末尾。此操作後，字串變為“cdab”。這反過來使兩個字串相等
演算法
- 取第一個字串。讓我們將其稱為‘str1’。
透過如下方式將 str1 與 str1 連線起來建立一個臨時字串：
temp = str1 + str1
- 計算使所有其他字串與當前目標字串相同所需的旋轉次數
- 對所有字串重複上述步驟，並返回所有計數的最小值。
示例
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minMoves(string str[], int n) {
int minCnt = INT_MAX;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
string temp = str[j] + str[j];
int index = temp.find(str[i]);
if (index != string::npos) {
cnt += index;
}
}
minCnt = min(cnt, minCnt);
}
return minCnt;
}
int main() {
string str[] = {"abcd", "cdab", "bacd", "cdba"};
cout << "Minimum moves: " << minMoves(str, SIZE(str)) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Minimum moves: 2
更新於: 2019-11-22
351 次瀏覽
廣告