数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告