共计 1911 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
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 人工智能学习材料，大量后端学习材料等你来拿。
正文完