字串反轉算是基礎的考題,不論在學校或是工作,拿來作為考題或面試題都會是必經的一道題。
首先,你會拿到一個題目,題目內容是將看到的字串反轉,通常會拿到一個固定的字串去反轉,但在這裡,我建立一個方法亂數產生字串,並且有一個必須傳入的參數——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 ⭐
or buy me a coffee ⬇️ I'd appreciate it.
Top comments (0)