資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
