萌新刷題（六）旋轉字元串

題目

給定一個字元串和一個偏移量，根據偏移量旋轉字元串(從左向右旋轉)

樣例

對於字元串 "abcdefg".

offset=0 => "abcdefg"offset=1 => "gabcdef"offset=2 => "fgabcde"offset=3 => "efgabcd"

在數組上原地旋轉，使用O(1)的額外空間

思路

常見的翻轉法應用題，仔細觀察規律可知翻轉的分割點在從數組末尾數起的offset位置。先翻轉前半部分，隨後翻轉後半部分，最後整體翻轉。

代碼

C++

class Solution {public: /** * @param str: a string * @param offset: an integer * @return: nothing */ void rotateString(string &str, int offset){ // wirte your code here if (strlen(str.c_str()) != 0){ offset = offset % strlen(str.c_str()); str.insert(0, str, strlen(str.c_str())-offset, offset); str.erase(str.end()-offset, str.end()); } }};

class Solution: # @param s: a list of char # @param offset: an integer # @return: nothing def rotateString(self, s, offset): # write you code here if len(s) > 0: offset = offset % len(s) temp = (s + s)[len(s) - offset : 2 * len(s) - offset] for i in xrange(len(temp)): s[i] = temp[i]

public class Solution { /* * param A: A string * param offset: Rotate string with offset. * return: Rotated string. */ public char[] rotateString(char[] A, int offset) { if (A == null || A.length == 0) { return A; } int len = A.length; offset %= len; reverse(A, 0, len - offset - 1); reverse(A, len - offset, len - 1); reverse(A, 0, len - 1); return A; } private void reverse(char[] str, int start, int end) { while (start < end) { char temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } }};

真正的素顏美女，就是養眼！看完你一定會喜歡
推薦閱讀：