資料結構
網路
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
