剑指offer——左旋转字符串

AI那点小事

发布于 2020-04-18 00:46:27

2780

发布于 2020-04-18 00:46:27

文章被收录于专栏：AI那点小事

概述

题目描述汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路

初始化len为字符串长度，首先对整个字符串反转，然后再对前len-n个字符翻转，最后对最后n个字符串翻转即可。循环右移的方法与之类似。相关博客请移步： 2010年计算机联考真题——一维数组循环左移

C++ AC代码

#include <iostream>
#include <string>
using namespace std;

class Solution {
    public:
        void Reverse(char* str,int start,int end,int len){
            if(start >= end || end > len){
                return;
            }
            int mid = (start+end)/2;
            for(int i = 0 ; i <= mid-start ; i++){
                char tmp = str[i+start];
                str[i+start] = str[end-i];
                str[end-i] = tmp;
            } 
        }

        string LeftRotateString(string str, int n) {
            int len = str.length();
            char* ch = (char*) str.c_str();
            this->Reverse(ch,0,len-1,len);
            this->Reverse(ch,0,len-n-1,len);
            this->Reverse(ch,len-n,len-1,len);
            string s = "";
            for(int i= 0 ; i < len ; i++){
                s.push_back(ch[i]);
            }
            return s;
        }
};