lintcode :旋转字符串

题目:

给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转)

样例

对于字符串 "abcdefg".

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

在数组上原地旋转,使用O(1)的额外空间

解题:

这个题目和这一题很像,前部分逆序,后部分逆序,整体逆序,这里注意的是offeset会大于字符串长度的情况,所以要对offeset处理:offeset = offeset%len

Java程序:

public class Solution {
/**
* @param str: an array of char
* @param offset: an integer
* @return: nothing
*/
public void rotateString(char[] str, int offset) {
// write your code here
int left = 0;
int right = str.length-1; if(str!=null && str.length!=0){
offset = offset%(right+1);
rotateStr(str,0,right - offset);
rotateStr(str,right - offset+1,right);
rotateStr(str,0,right); }
}
public void rotateStr(char[]str,int left,int right){
char tmp;
while(left<right){
tmp = str[left];
str[left] = str[right];
str[right] = tmp;
left++;
right--;
}
}
}

总耗时: 831 ms

Python程序:

class Solution:
# @param s: a list of char
# @param offset: an integer
# @return: nothing
def rotateString(self, s, offset):
# write you code here
if s!=None and len(s)!=0:
left = 0
right = len(s) - 1
offset = offset%(right+1)
self.rotateStr(s,0,right - offset)
self.rotateStr(s,right - offset + 1,right)
self.rotateStr(s,0,right) def rotateStr(self,s,left,right):
while left<right:
tmp = s[left]
s[left] = s[right]
s[right] = tmp
left += 1
right -= 1

总耗时: 233 ms

上一篇:SQL Server :DBLINK创建及使用


下一篇:QT5-控件-QTimeEdit和QTime