Lintcode8 Rotate String solution 題解

發(fā)布時間：2020-07-17 06:55:03 來源：網(wǎng)絡(luò) 閱讀：451 作者：coderer 欄目：軟件技術(shù)

【題目描述】

Given a string and an offset, rotate string by offset. (rotate from left to right)

給定一個字符串和一個偏移量，根據(jù)偏移量旋轉(zhuǎn)字符串(從左向右旋轉(zhuǎn))

【題目鏈接】

http://www.lintcode.com/en/problem/rotate-string/

【題目解析】

常見的翻轉(zhuǎn)法應(yīng)用題，仔細觀察規(guī)律可知翻轉(zhuǎn)的分割點在從數(shù)組末尾數(shù)起的offset位置。先翻轉(zhuǎn)前半部分，隨后翻轉(zhuǎn)后半部分，最后整體翻轉(zhuǎn)。

源碼分析：異常處理，A為空或者其長度為0；offset可能超出A的大小，應(yīng)模len后再用；三步翻轉(zhuǎn)法。Python 雖沒有提供字符串的翻轉(zhuǎn)，但用 slice 非常容易實現(xiàn)，非常 Pythonic!

復(fù)雜度分析：翻轉(zhuǎn)一次時間復(fù)雜度近似為 O(n)O(n)O(n), 原地交換，空間復(fù)雜度為 O(1)O(1)O(1). 總共翻轉(zhuǎn)3次，總的時間復(fù)雜度為 O(n)O(n)O(n), 空間復(fù)雜度為 O(1)O(1)O(1).

【答案鏈接】

http://www.jiuzhang.com/solution/rotate-string/

向AI問一下細節(jié)

猜你喜歡