剑指offer——面试题42-1：左旋转字符串

力扣，https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/description/

Python

class Solution:
    def dynamicPassword(self, password: str, target: int) -> str:
        new_password = password + password
        n = len(password)
        start = target
        end = target + n
        return new_password[start: end]

Java

class Solution {
    public String dynamicPassword(String password, int target) {
        if (target == 0) {
            return password;
        }
        int size = password.length();
        String str = password + password;

        return str.substring(target, target + password.length());
    }
}

20180906整理
##Solution1:
自己最开始想出来的垃圾算法！！！

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int i = 0;
        for(i = 0; i < n; i++) {
            LeftMoveOne(str);
        }
        return str;
    }
    
    void LeftMoveOne(string &str){
        char temp = str[0];
        for(int i = 1; i < str.size(); i++)
            str[i-1] = str[i];
        str[str.size() - 1] = temp;
        return;
    }
};

##Solution2:
20180906重做。此算法稍好一点

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if (str.size() <= 1 || n == 0) return str;
        int mod = n % str.size();
        if (!mod) return str;
        return str.substr(mod) + str.substr(0, mod);
    }
};

再稍微改进一点点。。

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);
    }
};

##Solution3:
比较巧妙的一种算法，主要考察三次翻转。
原理：$YX=(X^T{Y}^T{)}^T$
PS:这种描述原理的方式还真是简单粗暴，清晰易懂~~~

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if (str.size() <= 1 || n == 0) return str;
        int mod = n % str.size();
        if (!mod) return str;
        reverse(str.begin(), str.begin() + mod);
        reverse(str.begin() + mod, str.end());
        reverse(str.begin(), str.end());
        return str;
    }
};