数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找最小循环旋转次数以避免特定字符串集并获得给定数字字符串
在这篇文章中，我们将找到获得给定数字字符串（目标字符串）所需的最小循环旋转次数，同时避免给定的字符串集。目标字符串和字符串集中的字符串长度均为N。初始字符串将是一个包含全零且长度为N的字符串。
在这篇文章中讨论的方法中，我们将使用队列数据结构和集合数据结构。队列数据结构将保存我们当前所在的字符串，即我们目前已到达的数字字符串。集合数据结构将保存所有被阻止的字符串以及我们之前已经到达的所有字符串。这样做是为了避免重复，从而避免反复访问相同的字符串并陷入死循环。在每次迭代中，我们将进行所有可能的移动，并将生成的新的字符串添加到队列中。当我们第一次生成目标字符串时，我们将跳出循环并返回结果。
问题陈述
给定一个长度为N的数字字符串（目标字符串）和一个字符串列表（每个字符串长度也为N），我们需要找到将初始字符串转换为目标字符串所需的最小循环旋转次数。初始字符串将是一个长度为N，只包含零的字符串。
在一次循环旋转中，我们可以选择0到N-1之间的任何索引，并增加或减少初始字符串中该索引处的数字值。
注意 − 如果特定索引的值为0，并且我们对该索引执行减操作，则其值将转换为9。类似地，如果特定索引的值为9，并且我们对其执行加操作，则其值将转换为0。
示例
输入
Target = “22”, avoid = {“10”, “11”, “12”}
输出
6
解释
我们可以按照以下顺序获得目标字符串
“00” -> “01” -> “02” -> “03” -> “13” -> “23” -> “22”
输入
target = “55”, avoid = {“01”, “10”, “09”, “90”}
输出
-1
解释
从我们的初始字符串“00”开始，如果我们进行一次循环旋转，我们可以生成四个字符串：“01”、“10”、“09”、“90”。由于所有这些字符串都在avoid数组中，因此我们无法生成除“00”之外的任何字符串。
因此输出为-1。
输入
target = “111”, avoid = {“001”, “010”, “100”}
输出
5
解释
我们可以按照以下顺序：
“000” -> “900” -> “910” -> “911” -> “011” -> “111”
方法
在这种方法中，我们将使用队列数据结构和集合数据结构。队列数据结构将用于存储在进行K次循环旋转操作后可以生成的所有可能的字符串。集合数据结构将存储我们想要避免的所有字符串，并且还将存储我们之前已经访问过的所有字符串，这将有助于减少重复。我们将初始字符串插入队列中。在每次迭代中，我们将使用for循环弹出队列中所有当前元素。然后，对于每个字符串，我们找出通过对字符串进行单个循环旋转操作可以生成的所有可能的字符串。如果字符串已在集合中，则我们继续；否则，我们将它添加到队列中，并将它添加到集合中。我们循环直到获得目标字符串或队列为空。
算法
步骤1 − 创建一个集合数据结构。
步骤1.1 − 将avoid数组中的所有元素插入集合数据结构中。
步骤1.2 − 如果初始字符串或目标字符串在avoid数组中，则返回-1。
步骤2 − 创建一个队列数据结构并将初始字符串压入队列。
步骤2.1 − 也将字符串插入集合中。
步骤3 − 循环直到队列为空
步骤3.1 − 在每次迭代中，将队列的当前大小存储在一个数组中，并创建一个for循环来访问队列元素。
步骤3.2 − 在for循环的每次迭代中，获取队列中的前一个元素并将其从队列中弹出。
步骤3.3 − 如果当前字符串等于目标字符串，则返回结果。
步骤3.4 − 查找可以使用当前字符串生成的所有字符串。
步骤3.5 − 对于每个字符串，如果该字符串不在集合中，则将其压入队列并将该字符串插入集合中。
步骤3.6 − 完成for循环后，如果我们还没有找到目标字符串，则将结果变量加1。
步骤4 − 如果队列为空，则无法生成目标字符串，因此返回-1。
示例
#include <bits/stdc++.h>
using namespace std;
int minimum_count_of_circular_operations(string target, vector<string> &avoid, string initial){
set<string> to_avoid;
for(auto it:avoid){
if(it==initial || it==target)return -1;
to_avoid.insert(it);
}
int res = 0;
queue<string> curr_strings;
curr_strings.push(initial);
to_avoid.insert(initial);
while(!curr_strings.empty()){
int x = curr_strings.size();
for(int i=0;i<x;i++){
string temp = curr_strings.front();
curr_strings.pop();
if(temp==target)return res;
for(int j=0;j<temp.size();j++){
char increased = temp[j]+1 ,decreased=temp[j]-1, curr_ch=temp[j];
if(temp[j]=='9')increased='0';
if(temp[j]=='0')decreased='9';
temp[j] = increased;
if(!to_avoid.count(temp)){
to_avoid.insert(temp);
curr_strings.push(temp);
}
temp[j] = decreased;
if(!to_avoid.count(temp)){
to_avoid.insert(temp);
curr_strings.push(temp);
}
temp[j] = curr_ch;
}
}
res++;
}
return -1;
}
int main(){
string target = "111";
vector<string> avoid = {"001", "010", "100"};
string initial = "000"; cout<<minimum_count_of_circular_operations(target,avoid,initial)<<endl;
return 0;
}
输出
5
时间复杂度 – O(N^3)，其中N是字符串的长度。
空间复杂度 – O(N)
浏览量：37
