乐趣区

关于mysql:高频算法面试题旋转字符串完整的代码实现

jiezi

题目形容 

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 人工智能学习材料，大量后端学习材料等你来拿。

退出移动版