龍華建站公司b站視頻推廣網(wǎng)站2023年
文章目錄
- Reverse String 反轉(zhuǎn)字符串
- 問題描述:
- 分析
- 代碼
- Tag
Reverse String 反轉(zhuǎn)字符串
問題描述:
編寫一個(gè)函數(shù),其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 s 的形式給出。
不要給另外的數(shù)組分配額外的空間,你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。
1 < = s . l e n g t h < = 1 0 5 s [ i ] i s a p r i n t a b l e a s c i i c h a r a c t e r . 1 <= s.length <= 10^5\\ s[i] is a printable ascii character. 1<=s.length<=105s[i]isaprintableasciicharacter.
分析
呃,反轉(zhuǎn)字符串,還能說啥呢,看代碼吧。
入門級(jí)方法,就是新開一個(gè)數(shù)組,從右向左依次填入原數(shù)組的從左向右的元素,時(shí)間復(fù)雜度 O ( N ) O(N) O(N),空間復(fù)雜度 O ( N ) O(N) O(N).
進(jìn)階的方法,就是雙指針swap,空間可以降低到 O ( 1 ) O(1) 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 ) O(N) O(N)
空間復(fù)雜度 O ( 1 ) O(1) O(1)
Tag
Two Pointers
String