数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究避免特定字符串集的情况下，获得给定数字字符串所需的最小循环旋转次数
在这个问题中，我们将找到从包含 N 个 0 的字符串获得目标字符串所需的旋转次数。此外，在进行旋转时，我们将跳过数组中给定的字符串。
我们可以使用 BFS 算法来找到获得目标字符串所需的最小旋转次数。
问题陈述
我们给定一个包含 N 个数字字符的目标字符串。此外，我们还给定了一个 strs[] 数组，其中包含 M 个大小为 N 的包含数字字符的字符串。我们需要通过多次执行给定的操作，最初从包含 N 个 0 的字符串获得目标字符串。在一次操作中，我们可以旋转字符串的任何字符，但我们需要确保在任何旋转中，我们都不应该得到 strs[] 包含的字符串。我们需要找到从初始字符串获得目标字符串所需的最小旋转次数。
注意 - 我们可以将 9 旋转为 0，将 0 旋转为 9。
示例
输入
N = 4; target = "7531"; strs = {"1543", "7434", "7300", "7321", "2427"};
输出
12
解释
我们需要从字符串 0000 开始。之后，我们可以进行以下旋转，并在旋转字符串时跳过数组中包含的字符串。
0000 → 9000 → 8000 → 7000 → 7900 → 7800 → 7700 → 7600 → 7500 → 7510 → 7520 → 7530 → 7531
这里，我们跳过了字符串 7300。另一个解决方案如下所示。
0000 → 9000 → 8000 → 7000 → 7100 → 7200 → 7210 → 7310 → 7410 → 7510 → 7520 → 7530 → 7531
输入
N = 4; target = "7531"; strs = {"7513", "7434", "7300", "7321", "2427"};
输出
-1
解释
目标字符串存在于数组中，我们需要跳过数组中包含的所有字符串。因此，无论如何都不可能获得目标字符串。
方法
在这种方法中，我们将向前和向后旋转给定字符串的每个字符。之后，我们将更新后的字符串插入队列。在下一次迭代中，我们将从前一次迭代中获取所有字符串，更新它们，并将它们插入队列。
在更新字符串时，我们将确保跳过 strs[] 数组的字符串。当我们获得目标字符串时，我们将返回所需的总旋转次数。
算法
步骤 1 - 使用 N 个 0 初始化 target_str。我们将更新 target_str 字符串以获得目标字符串。
步骤 2 - 此外，定义 'skip' 集合来存储我们需要跳过的字符串。因此，将 strs[] 的所有字符串插入集合中。
步骤 3 - 如果 skip 集合包含 target_str 或目标字符串，则返回 -1。
步骤 4 - 定义字符串队列并将 target_str 字符串插入队列。此外，定义 'rotations' 来存储旋转次数。
步骤 5 - 遍历队列。
步骤 5.1 - 增加旋转次数并获取队列的长度。
步骤 5.2 - 使用 for 循环遍历队列的所有元素。
步骤 5.2.1 - 从队列中获取前一个元素，并将其存储在 'str' 字符串变量中。
步骤 5.2.2 - 遍历 'str' 字符串的每个字符。
步骤 5.2.3 - 将 str[p] 存储到字符 'c' 中，并将 str[p] 增加 1。如果 str[p] 大于 '9'，则将其更新为 '0'。
步骤 5.2.4 - 如果当前字符串是目标字符串，则返回旋转次数。
步骤 5.2.5 - 如果 str 不存在于 'skip' 集合中，则将其推入队列。此外，将 str 插入 skip 集合，因为我们已经访问过它了。因此，我们下次需要跳过它。
步骤 5.2.6 - 使用 c − 1 初始化 str[p]。如果 str[p] 小于 '0'，则将其更新为 '9'。
步骤 5.2.7 - 如果更新后的 str 等于目标，则返回旋转次数。否则，如果 str 不在集合中，则将其插入队列。
步骤 5.2.8 - 将 str 插入 'skip' 集合。
步骤 5.2.9 - 使用 c（原始字符）更新 str[p]。
步骤 6 - 当无法获得目标字符串时，返回 -1。
示例
#include <bits/stdc++.h>
using namespace std;
int minRotations(string target, vector<string> &strs, int N) {
string target_str = "";
// Create a string containing N '0'
for (int p = 0; p < N; p++) {
target_str += '0';
}
unordered_set<string> skip;
// Insert given string in the set
for (int p = 0; p < strs.size(); p++)
skip.insert(strs[p]);
// Base case
if (skip.find(target_str) != skip.end())
return -1;
if (skip.find(target) != skip.end())
return -1;
queue<string> que;
que.push(target_str);
// To store a number of rotations
int rotations = 0;
// BFS algorithm
while (!que.empty()) {
rotations++;
int len = que.size();
for (int q = 0; q < len; q++) {
string str = que.front();
que.pop();
// Traverse the string
for (int p = 0; p < N; p++) {
char c = str[p];
// INcrement the character
str[p]++;
// Rotate the character
if (str[p] > '9')
str[p] = '0';
// If we got the targeted string
if (str == target)
return rotations;
// When we don't need to skip the string
if (skip.find(str) == skip.end())
que.push(str);
// Add in the set to skip as we already visited
skip.insert(str);
// Do the same thing after decreasing the current character by 1
str[p] = c - 1;
if (str[p] < '0')
str[p] = '9';
if (str == target)
return rotations;
if (skip.find(str) == skip.end())
que.push(str);
skip.insert(str);
str[p] = c;
}
}
}
return -1;
}
int main() {
int N = 4;
string target = "7531";
vector<string> strs = {"1543", "7434", "7300", "7321", "2427"};
cout << "The minimum rotations required to get the target string is - " << minRotations(target, strs, N) << endl;
return 0;
}
输出
The minimum rotations required to get the target string is - 12
时间复杂度 - O(N*N*N)
空间复杂度 - O(N)
结论
我们使用集合来跟踪已访问的字符串，并使用队列来存储更新后的字符串。在每次旋转中，我们更新从前一次迭代获得的字符串。每当我们第一次找到目标字符串时，我们都会返回旋转次数，因为 BFS 算法始终提供最小路径值。
89 次浏览
