字串反轉算是基礎的考題，不論在學校或是工作，拿來作為考題或面試題都會是必經的一道題。
首先，你會拿到一個題目，題目內容是將看到的字串反轉，通常會拿到一個固定的字串去反轉，但在這裡，我建立一個方法亂數產生字串，並且有一個必須傳入的參數——length，每次 Random 時都可以自由配置字串的長度。
/// <summary>
/// 取得亂數產生的字串
/// </summary>
/// <param name="length"></param>
/// <returns></returns>
public static string RandomString(int length)
{
string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
Random random = new Random(Guid.NewGuid().GetHashCode());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++)
sb.Append(str[random.Next(0, str.Length)]);
return sb.ToString();
}
題目準備好後，下一步就來解題，目前我只有想到四種反轉方法，如果你有其他的方法，不論好與壞，請不要吝嗇留言告訴我～
暴力破解法
比較直覺的做法，從尾到頭遍歷所有字符，並將每次遍歷的字符加到新的變數裡
/// <summary>
/// 暴力破解 O(n)
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase1(string s)
{
string res = string.Empty;
for (int i = s.Length - 1; i >= 0; i--)
res += s[i];
return res;
}
LINQ
直接使用 LINQ 的 Reverse 方法，寫起來簡易明瞭又快速
/// <summary>
/// LINQ Reverse method
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase2(string s)
{
return string.Join("", s.Reverse());
}
頭尾位置對調
運用厲害一點的演算法來解——頭尾文字的位置對調，暴力破解迭代了所有字符，而這個方法只需要迭代一半的字符，等於時間複雜度減少了一半，整體效能優於暴力破解。
/// <summary>
/// 頭尾對調位置 O(n/2)
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase3(string s)
{
char[] c = s.ToCharArray();
int i = 0;
int j = s.Length - 1;
// you can also use a for loop to iterate
while (i < j)
{
// swap
char temp = c[i];
c[i] = c[j];
c[j] = temp;
i++;
j--;
}
return new string(c);
}
C# Array 原生反轉方法
最後，一定要知道的 Array.Reverse() C# 原生方法，反轉前先將字串轉換成 Array，反轉完後再 new 成一個新的字串
/// <summary>
/// C# Array 原生反轉方法
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase4(string s)
{
char[] c = s.ToCharArray();
Array.Reverse(c);
return new string(c);
}
寫一個測試 Action 執行時間的方法
/// <summary>
/// 測試 Action 執行時間
/// </summary>
/// <param name="action"></param>
/// <param name="methodName"></param>
static void TestTime(Action action, string methodName)
{
Stopwatch sw = new Stopwatch();
sw.Start();
action();
sw.Stop();
Console.WriteLine($"Duration: {sw.ElapsedMilliseconds:N0}ms, TestName:{methodName}");
}
Main 方法
static void Main(string[] args)
{
// six nines
var str = GetRandomString(100000);
TestTime(() => ReverseCase1(str), "暴力破解");
TestTime(() => ReverseCase2(str), "LINQ 反轉方法");
TestTime(() => ReverseCase3(str), "頭尾對調位置");
TestTime(() => ReverseCase4(str), "C# Array 原生反轉方法");
}
執行結果
因為暴力破解遍歷的所有字符，沒有意外的話它會是執行時間最久的方法
第一次執行結果，可以看到暴力破解法的時間複雜度相對高，僅次於後的是 LINQ 方法，而後兩種方法無法比較。
如果加大長度同時去跑這四種方法，會因為暴力破解法的執行時間過長而等待，為了再更清楚的看到後兩種方法執行狀況，將前兩種方法註解，只運行後兩種方法，並且加大參數長度為 9999999
比較就明顯出來了，雖然頭尾對調是優化過的演算法，甚至比 LINQ 的執行效率更高，但還是輸給 C# Array 的原生方法。
或許 Array 底層的最佳化是基於頭尾對調的邏輯去執行的…？
Thanks for reading the article 🌷 🌻 🌼
If you like it, please don't hesitate to click heart button ❤️
or follow my GitHub ⭐ I'd appreciate it.
Top comments (0)