定义字符串的左旋转操作,把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab,请实现字符串左旋转函数。

定义字符串的左旋转操作,把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab,请实现字符串左旋转函数。

要求时间复杂度O(n),空间复杂度O(1).

解法1是将前k个字符串反转,后面的字符串同样反转,再对整个字符串进行一次翻转。

解法2如下

public class Rotate {

    public static String rotate(String s, int leftSize) {
        char[] chars = s.toCharArray();
        int L = 0;
        int R = s.length() - 1;
        int lpart = leftSize;
        int rpart = s.length() - leftSize;
        int same = Math.min(lpart, rpart);
        int diff = lpart - rpart;
        exchange(chars, L, R, same);
        while (diff != 0) {
            if (diff > 0) {
                L = L + same;
                lpart = diff;
            } else {
                R = R - same;
                rpart = -diff;
            }
            same = Math.min(lpart, rpart);
            diff = lpart - rpart;
            exchange(chars, L, R, same);
        }
        return String.valueOf(chars);
    }

    private static void exchange(char[] chars, int L, int R, int size) {
        int i = R - size + 1;
        char tmp = 0;
        while (size-- != 0) {
            tmp = chars[L];
            chars[L] = chars[i];
            chars[i] = tmp;
            L++;
            i++;
        }
    }


    public static void main(String[] args) {
//        String s = "abcdef";
//        String rotate = rotate(s, 4);
        String s = "abcdefgh";
        String rotate = rotate(s, 2);
    }
}

上一篇:虚拟机安装Windows11正式版


下一篇:ldd用法