剑指58-II：左旋转字符串

传送门

nowcoder
leetcode

题目描述

对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出。
例如：字符序列 S=”abcXYZdef”, 要求输出循环左移 3 位后的结果，即”XYZdefabc”。

C++ 代码 - nowcoder

/*
    暴力方法：str + str 拼接起来，从 n 开始遍历 len
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.size();
        if (len == 0) return str;  // str 为空
        if (n >= len) n = n % len; // n 比 str 更大的情况
        
        string temp = str + str;
        string res;
        res.resize(len);
        int index = 0;
        for (int i = n; i < n + len; i++) {
            res[index ++] = temp[i];
        }
        return res;
    }
};

/*
    三次翻转
    
    "...X...Y" -> "...Y...X"
    reverse("...X") -> "X......Y"
    reverse("...Y") -> "X...Y..."
    reverse("...X...Y") -> "...Y...X"
*/
class Solution {
public:
    string LeftRotateString(string str, int n) {
        int m = str.size();
        if (m == 0) return "";
        n = n % m; // 取余，每次长度为 m 的旋转相当于没有变化

        reverse(str, 0, n - 1);
        reverse(str, n, m - 1);
        reverse(str, 0, m - 1);
        return str;
    }

    void reverse(string& str, int i, int j) {
        while (i < j) {
            char tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
            i++, j--;
        }
    }
};

C++ 代码 - leetcode

/*
    暴力方法：str + str 拼接起来，从 n 开始遍历 len
*/
class Solution {
public:
    string dynamicPassword(string s, int n) {
        return s.substr(n) + s.substr(0, n);
    }
};

/*
    三次翻转
    
    "...X...Y" -> "...Y...X"
    reverse("...X") -> "X......Y"
    reverse("...Y") -> "X...Y..."
    reverse("...X...Y") -> "...Y...X"
*/
class Solution {
public:
    string dynamicPassword(string s, int n) {
        int length = s.size();
        if (length <= n) return s;

        reverse(s, 0, n - 1);
        reverse(s, n, length - 1);
        reverse(s, 0, length - 1);
        return s;
    }

    void reverse(string &s, int i, int j) {
        while (i < j) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i ++, j --;
        }
    }
};