首页 > 试题广场 >

左旋转字符串

[编程题]左旋转字符串
  • 热度指数:445428 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列  S ,请你把其循环左移 K 位后的序列输出。例如,字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果,即 “XYZdefabc”

数据范围:输入的字符串长度满足
进阶:空间复杂度 ,时间复杂度
示例1

输入

"abcXYZdef",3

输出

"XYZdefabc"
示例2

输入

"aab",10

输出

"aba"
# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if not s or len(s) == 0:
            return ''
        n =  n % len(s) 
        s = list(s)
        self.swap(0, n-1, s)
        self.swap(n, len(s)-1, s)
        self.swap(0, len(s)-1, s)
        return ''.join(s)
        
    def swap(self, i, j, s):
        while i < j:
            s[i],s[j]  = s[j], s[i]
            i += 1
            j -= 1
        

发表于 2019-08-14 09:46:20 回复(0)
更多回答
原理:YX = (XTY T)T
class Solution {
public:
    string LeftRotateString(string str, int n) 
    {
    	int len = str.size();
        if(len == 0) return str;
        n %= len;
        for(int i = 0, j = n - 1; i < j; ++i, --j) swap(str[i], str[j]);
        for(int i = n, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
        for(int i = 0, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
        return str;
    }
};

发表于 2016-08-05 12:49:52 回复(25)
public class Solution {
    public String LeftRotateString(String str,int n) {
        char[] chars = str.toCharArray();        
        if(chars.length < n) return ""; 
        reverse(chars, 0, n-1);
        reverse(chars, n, chars.length-1);
        reverse(chars, 0, chars.length-1);
        StringBuilder sb = new StringBuilder(chars.length);
        for(char c:chars){
            sb.append(c);
        }
        return sb.toString();
    }
    
    public void reverse(char[] chars,int low,int high){
        char temp;
        while(low<high){
            temp = chars[low];
            chars[low] = chars[high];
            chars[high] = temp;
            low++;
            high--;
        }
    }
}


发表于 2015-04-13 01:03:48 回复(7)
/**
 * 题目描述
 * 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,
 * 就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,
 * 请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,
 * 要求输出循环左移3位后的结果,即“XYZdefabc”。
 * 是不是很简单?OK,搞定它!
 *
 * @author shijiacheng
 */
public class LeftRotateStringSolution {
    public String LeftRotateString(String str, int n) {
        char[] chars = str.toCharArray();
        if (chars.length < n) {
            return "";
        }
        reverse(chars, 0, n - 1);
        reverse(chars, n, chars.length - 1);
        reverse(chars, 0, chars.length - 1);

        return new String(chars);
    }

    public void reverse(char[] chars, int start, int end) {
        while (start < end) {
            char temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            start++;
            end--;
        }
    }
}
发表于 2018-03-15 22:26:59 回复(5)
public class Solution {
    public String LeftRotateString(String str,int n) {
        //保证旋转的位数大于字符串的长度,否则返回空字符串
        if(n>str.length())
			return "";
        //把原字符串截取成俩字符串,然后拼接
        String s1 = str.substring(0, n);
		String s2 = str.substring(n,str.length());
		return s2 + s1;
    }
}

编辑于 2016-07-31 20:51:51 回复(5)
貌似没怎么看到java,贴上自己的代码
public class Solution {
public String LeftRotateString(String str,int n) {
int length = str.length();
if(length<=0){
return "";
}
StringBuffer sb = new StringBuffer(str.substring(0, n));
StringBuffer sb1 = new StringBuffer(str.substring(n, str.length()));
sb1.append(sb);
//System.out.println(sb1);
return sb1.toString();
        
    }
}

做的时候用str作判断一直不给我过,看了讨论区都有length才能通过,,,,坑
发表于 2015-08-16 14:51:19 回复(10)
class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len=str.length();
        if(len<=0||n<=0)
            return str;       //假设输入str为abcXYZdef,n=3    
        Reverse(str,0,n-1);   //反转前n个字符,得到cbaXYZdef
        Reverse(str,n,len-1); //反转第n个字符后面所有的字符cbafedZYX
        Reverse(str,0,len-1); //反转整个字符串XYZdefabc
        return str;
    }
   void Reverse(string &str,int begin,int end)
    {
        int temp;
        while(begin<end)
         {
            temp=str[begin];
            str[begin]=str[end];
            str[end]=temp;
            
            begin++,end--;
         }
    }
};

发表于 2017-07-25 11:13:37 回复(2)
//C++
/*解法一:在原字符串上修改
“abcdef”循环左移9位(3位)
前3位逆序,后3位逆序,整体再逆序。
“cbafed”-> “defabc”
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.size();
        if(len <= 0)
        	return "";
        n = n%len;
        if(n==0)
            return str;
        reverseStr(str,0,n-1);
        reverseStr(str,n,len-1);
        reverseStr(str,0,len-1);
        return str;
    }
    void reverseStr(string &str, int left, int right)
    {
        for(int i=left,r=right;i<=left+(right-left)/2;++i){
            swap(str[i],str[r--]);
        }
    }
};
/*解法二:
借助n个大小的额外空间
*/class Solution {
public:
    string LeftRotateString(string str, intn) {
        string ret;
        intlen = str.size();
        if(len <= 0)
            return"";
        n = n%len;
        ret = str+str.substr(0,n);
        ret = ret.substr(n,str.size());
        returnret;
    }
};

编辑于 2016-05-07 23:05:26 回复(0)
BA = (A.reverse() B.reverse()).reverse(), 模拟这三个字符串翻转操作即可
# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        res, length = list(s), len(s)
        if n > length : return ""
        for i in range(int(n/2)):
            res[i], res[n-1-i] = res[n-1-i], res[i]
        for i in range(n, int((n+length)/2)):
            res[i], res[length-1-i+n] = res[length-1-i+n], res[i]
        for i in range(int(length/2)):
            res[i], res[length-1-i] = res[length-1-i], res[i]
        return "".join(res)

发表于 2019-05-19 16:28:47 回复(0)
public class Solution {
    /**
     * 思路:
     * 1.先翻转前半部分
     * 2.再翻转后半部分
     * 3.再对字符串整个进行翻转
     *
     * 考点:不使用库对字符串进行灵活的翻转
     */
    public String LeftRotateString(String str,int n) {
        if (str == null || str.length() == 0 || n <= 0) {
            return str;
        }
        if (n >= str.length()) {
            n = n % str.length();
        }
        char[] ch = str.toCharArray();
        reverseString(ch, 0, n - 1);
        reverseString(ch, n, str.length() - 1);
        reverseString(ch, 0, str.length() - 1);
        return new String(ch);
    }
    
    /**
     * 对字符数组 ch 的 start 到 end 范围内的字符进行翻转
     */
    public void reverseString(char[] ch, int start, int end) {
        while (start < end) {
            char temp = ch[start];
            ch[start] = ch[end];
            ch[end] = temp;
            start++;
            end--;
        }
    }
    
}

编辑于 2020-02-12 11:05:21 回复(5)
class Solution {
public:
    string LeftRotateString(string str, int n) {
           string l,r;
           for(int i=0;i<n;i++) r+=str[i];
           for(int i=n;i<str.size();i++) l+=str[i];
           return l+r;
    }
};

发表于 2017-07-12 11:12:50 回复(1)
    public static String LeftRotateString(String str,int n) {
        if (str == null || str.length() == 0) {
            return str;
        }

        n = n % str.length();
        return str.substring(n, str.length()) + str.substring(0, n);
    }

编辑于 2017-05-15 19:16:06 回复(1)
class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.length();
        if(len == 0) return "";
        n = n % len;
        str += str;
        return str.substr(n, len);
    }
};

发表于 2015-05-02 18:42:22 回复(128)

剑指Offer-左旋转字符串

package String;

/**
 * 左旋转字符串
 * 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。
 * 对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。
 * 例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
 */
public class Solution31 {
    public static void main(String[] args) {
        Solution31 solution31 = new Solution31();
        String str = "abcXYZdef";
        System.out.println(solution31.LeftRotateString(str, 3));
    }

    public String LeftRotateString(String str, int n) {
        if (str == null || str.length() == 0) return "";
        StringBuilder sb1 = new StringBuilder(str.substring(0, n));
        StringBuilder sb2 = new StringBuilder(str.substring(n, str.length()));
        sb2.append(sb1);
        return sb2.toString();
    }
}
发表于 2018-04-17 12:44:35 回复(4)
 char *LeftRotateString(char *str, int n) {

 	char *tmp;

 	tmp = (char *)malloc((n + 1)*sizeof(char));
 	if (!tmp)
 	{
 		/* code */
 		printf("allocate memory failed!.\n");
 		exit(1);
 	}

 	memcpy(tmp, str, n);
 	*(tmp + n) = '\0';

 	memcpy(str, str + n, strlen(str) - n);
 	*(str + strlen(str) - n) = '\0';

 	strcat(str, tmp);
 	free(tmp);

 	return str;
}

发表于 2015-09-05 10:20:46 回复(0)
class Solution:
    def LeftRotateString(self, s, n):
        return s[n:len(s)]+s[0:n]
python一句话搞定

编辑于 2015-10-12 20:45:15 回复(5)
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        res = []
        tmp = []
        c = ['']*len(s)
        i = 0
        if n >=len(s):return s
        for j in s:
            c[i]=j
            i+=1   
        for _ in range(n):
            a = c.pop(0)
            tmp.append(a)
        for k in c:
            res.append(k)
        for f in tmp:
            res.append(f)
        return ''.join(res)
print(Solution().LeftRotateString('abcXYZdef', 4))

发表于 2019-08-30 20:49:36 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString1(self, s, n):
        if not s:
            return ""
        if n<0:
            return
        k = n%len(s)
        return s[k:]+s[:k]
    def LeftRotateString(self, s, n):
        if not s:
            return ""
        if n<0:
            return
        k = n%len(s)
        #c = (s[:k][::-1]+s[k::][::-1])
        #return c[::-1]
        return (s[:k][::-1]+s[k::][::-1])[::-1]

发表于 2019-03-28 19:00:14 回复(0)
public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str.equals("")) return "";
        n %= str.length(); // 处理循环移
        str = str + str; // 复制str,则原str左移n就相当于str的第一个字符右移n
        return str.substring(n,n + str.length() / 2);
    }
}


发表于 2019-02-19 16:59:28 回复(0)
/*1、这一题使用队列就可以解决,没从头部移出一个放到一个变量中
    然后再将变量中的值再次放入到队列中。
    队列满足先进先出
  2、使用StringBuffer进行字符串操作
*/
import java.util.*;
public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str.length()==0 || str.equals("")){
            return "";
        }
        Queue<String> queue = new LinkedList<String>();
        char[] s = str.toCharArray();
        for(int i=0;i<s.length;i++){
            queue.add(s[i]+"");
        }
        //开始移位
        for(int j=0;j<n;j++){
            String tmp = queue.remove();
            queue.add(tmp);
        }
        //将字符数组再次变成字符串
        StringBuffer sb = new StringBuffer();
        for(int k=0;k<s.length;k++){
            sb.append(queue.remove());
        }
        return sb.toString();
    }
}

发表于 2017-09-04 15:11:00 回复(1)
//和翻转单词顺序是一样的原理,分为两段各做一次翻转再做一次总的翻转。主要注意输入为空串的情况和越界的问题,一定要注意这些细节
class Solution {
public:
    void Reverse(string&str,int start,int end)
    {
        if(start>=end)
            return;
        while(start<end)
        {
            char c = str[start];
            str[start]=str[end];
            str[end] = c;
            start++;
            end--;
        }
    }
    string LeftRotateString(string str, int n) {
        int length = str.size();
        if(length<=0)
            return str;
        if(length>0&& n>0&&n<length)
        {
            int pFirstStart = 0;
            int pFirstEnd = 0+n-1;
            int pSecondStart = 0+n;
            int pSecondEnd = 0+length-1;
            
            Reverse(str,pFirstStart,pFirstEnd);
            Reverse(str,pSecondStart,pSecondEnd);
            Reverse(str,pFirstStart,pSecondEnd);
        }
    return str;
    }
    
};

发表于 2016-03-25 01:21:05 回复(1)