今天依舊是一道簡(jiǎn)單難度的題目, 騰訊校招精選的 50 題簡(jiǎn)單難度部分即將完結(jié), 繼續(xù)加油吧
題目
編寫(xiě)一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)。輸入字符串以字符數(shù)組 char[] 的形式給出。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問(wèn)題。
你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。
示例 1：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
示例 2：
輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
思路
這道題在此前是返回字符數(shù)組, 但現(xiàn)在換成了原地修改, 無(wú)返回值. 這使得高級(jí)函數(shù)的使用都被限制住了, 如果可以返回字符數(shù)組, 那么在 Python 中可以直接用return s[::-1] 這條語(yǔ)句即可實(shí)現(xiàn)反轉(zhuǎn), 在 Java 等高級(jí)語(yǔ)言中也有 reverse() 這樣的函數(shù).
現(xiàn)在題目修改之后, 思路被限定了, 你需要使用兩個(gè)指針來(lái)進(jìn)行數(shù)據(jù)交換. 遍歷半個(gè)數(shù)組, 依次交換兩個(gè)數(shù)即可.
遺憾的是, LeetCode 在這道題的解答排名上尚未舍棄之前允許返回值的解答, 我無(wú)法判斷這種解法是否最優(yōu), 如有更優(yōu)解法, 歡迎留言告知.
如下圖所示, 排名靠前的解答并不符合現(xiàn)在的題目
實(shí)現(xiàn)
盡管我已經(jīng)盡量?jī)?yōu)化語(yǔ)句, 如在 Python 中使用這樣 s[i], s[j] = s[j], s[i] 的數(shù)據(jù)交換方式而不是借由中間變量交換以節(jié)省時(shí)間, 但仍然消耗了 196 ms的時(shí)間, 而實(shí)際上算法的時(shí)間復(fù)雜度僅有O(n/2)
C語(yǔ)言
void reverseString(char* s, int sSize) {
int temp;
for(int i=0; i<sSize/2; i++){
temp = s[i];
s[i] = s[sSize-i-1];
s[sSize-i-1] = temp;
}
}
Python
class Solution:
def reverseString(self, s):
"""
:type s: List[str]
:rtype: void Do not return anything, modify s in-place instead.
"""
j = len(s)-1
for i in range(int(len(s)/2)):
s[i], s[j] = s[j], s[i]
j -= 1
i += 1
