题目形容
1. 给定一个字符串，要求把字符串后面的若干个字符挪动到字符串的尾部，如把字符串“abcdef”后面的2个字符’a’和’b’挪动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数实现此性能，要求对长度为n的字符串操作的工夫复杂度为 O(n)，空间复杂度为 O(1)。剖析与解法
计划一：暴力位移（工夫复杂度不符合要求）
思路
逻辑思路：
1. 把须要挪动的字符一个一个的挪动到字符串的尾部
代码实现思路：
1. 实现一个函数，能够实现挪动一个字符到字符串尾部的性能
2. 循环m次调用上述函数，实现挪动m个字符到字符串尾部代码实现(GO语言)
package main
func LeftShiftOne(chars []byte,n int) {
c:=chars[0] // 获取第一个字符
for i:=1;i<n;i++{
chars[i-1]=chars[i]
}
chars[n-1]=c
}
func LeftRotateString(s string,m int) string {
chars:=[]byte(s)
n:=len(chars)
for m>0{
LeftShiftOne(chars,n)
m--
}
return string(chars)
}
func main() {
res:=LeftRotateString("abcdef",2)
println(res)
}工夫复杂度和空间复杂度剖析
针对长度为n的字符串来说，假如须要挪动m个字符到字符串的尾部，那么总共须要 mn 次操作，同时设立一个变量保留第一个字符，如此，工夫复杂度为O(m*n)，空间复杂度为O(1)，空间复杂度合乎题目要求，但工夫复杂度不合乎，所以，咱们得须要寻找其余更好的方法来升高工夫复杂度。反转法(利用一点点数学知识)
思路
逻辑思路
1. 将一个字符串分成A和B两局部，而后定义一个字符串的反串操作，A^T，示意把A的所有字符反转(如，A=”abc“,那么A^T="cba"),在数学上有个对于矩阵运算的公式：(A*B)^T=B^T*A^T，套用一下能够得出一个论断:(A^T*B^T)^T=B*A,这样就解决了字符串反转的问题
代码实现思路：以反转abcdef为例
1. 实现一个反转字符串的函数
2. 将原字符串分为两个局部，即A:abc,B:def，注在本题中就是分为0-m和m-n的两个子串
2. 将A反转，A->A^T,即：abc->cba，将B反转,B->B^T，即：def-fed
3. 反转A^T*B^T,即反转cbafed，失去defabc,即为最初后果代码实现(GO语言)
package main
func ReverseString(chars []byte,from,to int) {
for from<to{
temp:=chars[from]
chars[from]=chars[to]
chars[to]=temp
from++
to--
}
}
func LeftRotateString(s string,m int) string {
chars:=[]byte(s)
n:=len(chars)
m%=n // 如果挪动的大于n位，那么和挪动%n位是一样的
ReverseString(chars,0,m-1) // 反转A，失去A^T m是挪动位数，m-1是下标
ReverseString(chars,m,n-1) // 反转B，失去B^T
// 此时 chars为 A^T*B^T
ReverseString(chars,0,n-1) // 反转A^T*B^T，失去B*A
return string(chars)
}
func main() {
res:=LeftRotateString("abcdef",2)
println(res)
}相干高频变种题
一样的结题思路，不再一个个的解释了，能够本人尝试解决，如果有问题，欢送在公众号”韩哥有话说“上给我留言，我会及时回复的1. 链表反转
给出一个链表和一个数k，比方，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。2. 尾部字符串挪动到头部
编写程序，在原字符串中把字符串尾部的m个字符挪动到字符串的头部，要求：长度为n的字符串操作工夫复杂度为O(n)，空间复杂度为O(1)。3. 单词反转(谷歌真题)
输出一个英文句子，翻转句子中单词的程序，但单词内字符的程序不变，句子中单词以空格符隔开。为简略起见，标点符号和一般字母一样解决。例如，输出“I am a student.”，则输入“student. a am I”。更多内容欢送关注我的集体公众号“韩哥有话说”，100G人工智能学习材料，大量后端学习材料等你来拿。
发表回复