你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

剑指 Offer 58 - II. 左旋转字符串

2021-11-9 0:59:21

左旋转字符串(Easy)

题目描述

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

举个栗子

  • 示例 1:
    • 输入: s = “abcdefg”, k = 2。
    • 输出: “cdefgab”。
  • 示例 2:
    • 输入: s = “lrloseumgh”, k = 6。
    • 输出: “umghlrlose”。

解题思路

  • 为了让本题更有意义,提升一下本题难度:不能申请额外空间,只能在本串上操作。
  • 不能使用额外空间的话,模拟在本串操作要实现左旋转字符串的功能还是有点困难的。
  • 使用整体反转+局部反转就可以实现左旋转的目的。
  • 具体步骤为:
    • 反转区间为前 k 的子串
    • 反转区间为 k 到末尾的子串
    • 反转整个字符串
    • 最后就可以得到左旋 k 的目的,而不用定义新的字符串,完全在本串上操作。

代码来了

public String reverseLeftWords(String s, int n) {
	char[] str = s.toCharArray();
	int k = n % str.length;

	reverse(str, 0, k - 1);
	reverse(str, k, str.length - 1);
	reverse(str, 0, str.length - 1);

	return new String(str);
}

public void reverse(char[] str,int left, int right){
	int count = (right - left) / 2;
	for(int i = 0;i <= count;i++){
		char temp = str[left + i];
		str[left + i] = str[right - i];
		str[right - i] = temp;
	}
}