如何解決 C#/Java 中的以下問題和時間復雜度？
有一個圓形的列印機輪，字母 A 到 Z 依次排列。它環繞使 A 和 Z 相鄰。列印機有一個最初指向“A”的指標。從任何字符移動到任何相鄰字符需要 1 秒。它可以向任一方向移動。給定一串字母，列印該字串所需的最短時間是多少？
示例：s = "BZA" 花費的時間是 3 秒，因為我們從 A 開始到 B 的時間是 1 秒。然后從 B 到 Z 是 2 秒 (B-> A -> Z) 。然后 Z -> A 又是 1 sec ，所以總共是 4 秒。
我試圖通過將 A 指向 1 并將 Z 指向 26 之類的數字分配給字典中的每個字符，但我無法進一步進行，因為使用此邏輯時間從 B -> Z 行進，這是不正確的 25 秒。
uj5u.com熱心網友回復：
您可以撰寫一個方法來確定兩個字符之間的最小距離：
static int Distance(char start, char end)
{
if (start < end)
return Math.Min(end - start, 26 - end start);
else
return Math.Min(start - end, 26 - start end);
}
然后計算字串的總距離：
static int TotalDistance(string s)
{
int total = 0;
for (int i = 0; i < s.Length - 1; i)
total = Distance(s[i], s[i 1]);
return total;
}
所以：
Console.WriteLine(TotalDistance("BZA")); // Prints 3
uj5u.com熱心網友回復：
字典方法是一個好的開始：您需要讓所有字母都有一個關聯的數字，例如。從 1 開始，A 開始，26 開始，Z。現在你可以做一個簡單的減法來找出直接路線（忽略超過 1 或 26）。
如果您有直接距離，則間接距離將正好相反。您無需為復雜的數學而煩惱，只需從總距離中減去直接距離即可。
示例代碼：
int maxNumber = 26;
int firstNumber = myDictionary['A'];
int secondNumber = myDictionary['Q'];
int direct = Math.abs(secondNumber - firstNumber);
if (direct <= (int)(maxNumber/2))
return direct;
return maxIdx - direct;
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313541.html
下一篇：從3小時時段延長至N天