Reverse String 反轉(zhuǎn)字符串

問題描述：

編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 s 的形式給出。

不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。

$$\begin{gathered} 1<=s.length<=10^5 \\ s[i]isaprintableasciicharacter. \end{gathered}$$

分析

呃，反轉(zhuǎn)字符串，還能說啥呢，看代碼吧。

入門級(jí)方法，就是新開一個(gè)數(shù)組，從右向左依次填入原數(shù)組的從左向右的元素，時(shí)間復(fù)雜度 $O(N)$,空間復(fù)雜度 $O(N)$.

進(jìn)階的方法，就是雙指針swap，空間可以降低到$O(1)$.

代碼

雙指針

public void reverseString(char[] s) {int n = s.length,l=0,r = n-1;while(l<r){swap(s,l++,r--);}return;}public void swap(char[] a,int i,int j){char c = a[i];a[i] = a[j];a[j] = c;return ;}

時(shí)間復(fù)雜度$O(N)$

空間復(fù)雜度$O(1)$

Tag

Two Pointers

String