剑指 Offer 58 - II. 左旋转字符串(3种方法)

简介: 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

题目:
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1:

输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2:

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制:

1 <= k < s.length <= 10000

来源:力扣(LeetCode)

一:开辟新空间

class Solution {
public:
    string reverseLeftWords(string s, int n) {
   string ans = "";
        for(int i = n; i < s.size(); i++){
            ans += s[i];
        }
        for(int i = 0; i < n; i++){
            ans += s[i];
        }
        return ans;
    }
};
ans += s[i];

利用c++中字符串的特性
也就是说,先把后面的字符串输出,再输出前面的字符串也就是相当于左转了字符串
二:多次旋转(3次旋转法,原地修改)

class Solution {
public:
    //无论是左移还是右移都可以使用多次反转实现
    void reverseStr(string& s, int l, int r){
        while(l < r){
            char temp = s[r];
            s[r--] = s[l];
            s[l++] = temp;
        }
    }
    string reverseLeftWords(string s, int n) {
        //原地修改,空间复杂度O(1);
        reverseStr(s, 0, s.size() - 1);//先进行第一次(全体翻转)
      
        reverseStr(s, 0, s.size() - n - 1);//第二次 将第一个到倒数第n个反转
  
        reverseStr(s, s.size() - n, s.size() - 1); //第三次 将倒数第n个到最后一个反转
      
        return s;
    }
};

原地修改,不需要开辟额外的空间,其实也就是以时间换取空间

三:利用c++特性,原地修改

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int len =s.size();

        s.resize(len+n);

        for(int i=0;i<n;i++){
            s[len++] =s[i];
        }

        s.erase(0,n);
        return s;
    }
};

利用了c++中string容器的resize函数,重新定义大小
利用for循环再新开辟出的位置进行赋值操作。
s.erase(0,n);再删除前n个位置。

目录
相关文章
|
6月前
|
Java C++ Python
剑指 Offer 05:替换空格
剑指 Offer 05:替换空格
41 0
|
2月前
|
C语言 C++
剑指 Offer(第 2 版)刷题 | 05. 替换空格
本文是作者在刷《剑指 Offer(第 2 版)》时对 "替换空格" 问题的解法分享,包括正确处理字符串中空格替换为"%20"的解法以及未刷题小白可能会犯的错误,同时记录了在解决过程中遇到的运行时错误。
剑指 Offer(第 2 版)刷题 | 05. 替换空格
|
6月前
剑指 Offer 10- II:青蛙跳台阶问题
剑指 Offer 10- II:青蛙跳台阶问题
47 1
|
6月前
剑指 Offer 10- I:斐波那契数列
剑指 Offer 10- I:斐波那契数列
33 1
|
6月前
|
Java C++ Python
剑指 Offer 58 - II:左旋转字符串
剑指 Offer 58 - II:左旋转字符串
62 0
|
6月前
剑指 Offer 49:丑数
剑指 Offer 49:丑数
35 0
|
6月前
剑指 Offer 07:重建二叉树
剑指 Offer 07:重建二叉树
32 0