【剑指Offer】（字符串）左旋转字符串（翻转操作）

小鱼儿 2022-03-12 10:24 214阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_12d959b108cb42b1ab72cef4d36af5ec_tpId_13_tqId_11196_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

class Solution { 
    public:
        string LeftRotateString(string str, int n) { 
            if(str.size()<=1) return str;
            n=n%str.size();
            if(n<=0) return str;                
            
            //方法1：需要借助O(n)额外空间
            /*string ans=str; for(int i=0;i<(str.size()-n);i++) ans[i]=str[i+n]; for(int i=str.size()-n;i<str.size();i++) ans[i]=str[i-(str.size()-n)]; return ans;*/
            //方法2：借助翻转操作。空间复杂度较低
            //[1]先将字符串分成两部分，分别翻转这两部分
            reverse(str,0,n-1);
            reverse(str,n,str.size()-1);
            //[2]翻转整个字符串
            reverse(str,0,str.size()-1);
            return str;
                
        }
        void reverse(string& str,int begin,int end){ 
            //翻转
            while(begin<end){ 
                char temp=str[begin];
                str[begin]=str[end];
                str[end]=temp;
                begin++;end--;
            }
        }
    };

[https_www.nowcoder.com_practice_12d959b108cb42b1ab72cef4d36af5ec_tpId_13_tqId_11196_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking