左旋转字符串 Posted on 2021-07-20 00:00:00 2021-07-20 00:00:00 by Author 摘要 给定一个字符串，你能原地使字符串左移或者右移k个位置吗？？？？？ # 左旋转字符串 > 写于2021/05/30 1. 题目描述 - 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。（不能申请额外的空间，只能在本串上操作） 2. 示例描述 - 示例一： - 输入：s = "abcdefg" ,k=2 - 输出："cdefgab" - 示例二： - 输入：s = "oldke" k =3 - 输出："keold" 3. 解题思路 - 对于本题来说，原地操作字符串，不能申请额外的空间，我的看法，就是可以把字符数组想象成一个首位相连的管道，每个字符在这个管道内所在的位置向后移动k个位置，就实现左旋字符串。 - 也许以上讲的太抽象了，举个具体的栗子：s = {'a','b','c','d','e','f',''g},我们可以想象`g`字符与`a`字符有通道是连着的。即为g后移一位就到a的位置(其实g后移一位就越界了)。之后g把a往后挤了一位到达`b`的位置，然后每一个字符都向后移动一位，到最后`f`字符移动到`g`位置，这样就实现了一次左旋操作，然后每个字符连续右移`k-1`位，就能实现字符串左旋转`k`位了。 - 那怎么实现这样的操作尼。其实我们可以这样想，让我们左旋k位，那我们可以对一个长度为n的字符串，先反转前`k`位字符，然后在反转后`n-k`位，最后再把整个字符串反转一遍，就能实现字符串左旋转`k`位了。那么为什么会想到这样做尼。 - 我们可以用数学推理，假设对于第`k+1`位的字符，左旋他应该出现在字符数组的首位。那我们就用上面的方法，计算这个字符每一步出现的位置，看这个字符最后的结果是否在字符串首部的位置，首先我们反转前k位字符，与`k+1`位的字符无关，我们到达第二步，反转后面的`n-k`位字符，那么就从第`k+1`位反转,那么反转后这个字符就到达字符数组的尾部。最后我们反转整个字符数组，那么最后一位的字符到达字符数组的头部，达到我们预期的结果。这只是其中一位字符位置变化的关系，我们用以上的方法可以推理出每一个字符变化的位置。都能达到我们左旋k位后的位置。以上就是这个算法的整体思路。具体代码如下文所示。 4. 代码实现 ```java public String reverseLeftWords(String s, int k) { String result = ""; char[] chars = s.toCharArray(); //先反转前k位 reverseWords(chars,0,k-1); //在反转后n-k位 reverseWords(chars,k,s.length()-1); //最后反转整个字符数组 reverseWords(chars,0,s.length()-1); //返回最终结果 for (int i = 0; i < chars.length; i++) { result+=chars[i]; } return result; } public void reverseWords(char[]chars, int start, int end){ //反转从下标为start到下标为end位置的字符 while(start<end){ char temp = chars[start]; chars[start]=chars[end]; chars[end] = temp; start++; end--; } } ```
{{ item.content }}
{{ child.content }}