1.1 字符串的旋转

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

package mainimport "fmt"func ReverseBytes(strBytes []byte) {	tmpLen := len(strBytes)	if tmpLen <= 1 {		return	}	tailIndex := tmpLen - 1	for headIndex := 0 ; headIndex < tailIndex; headIndex++{		tmpVal := strBytes[headIndex]		strBytes[headIndex] = strBytes[tailIndex]		strBytes[tailIndex] = tmpVal		tailIndex--	}	return}func StringReverse(str string, num int) (res string) {	strBytes := []byte(str)	tmpLen := len(str)	shiftLen := num % tmpLen	if shiftLen <= 0 {		res = str		return	}	leftPart := strBytes[0:shiftLen]	rightPart := strBytes[shiftLen:]	ReverseBytes(leftPart)	ReverseBytes(rightPart)	ReverseBytes(strBytes[0:])	res = string(strBytes)	return}func main() {	tmpStr := "abcdef"	fmt.Println(StringReverse(tmpStr, 3))}

单词翻转

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”。

func ReverseWord(str string) (res string) {	strBytes := []byte(str)	strLen := len(str)	curLeft := 0	curRight := 0	for i := 0; i < strLen; i++ {		if strBytes[i] != ' ' {			curRight = i		} else {			if curRight - curLeft >= 1 {				ReverseBytes(strBytes[curLeft:curRight+1])			}			curLeft = i + 1			curRight = i + 1		}	}	if curRight - curLeft >= 1 {		ReverseBytes(strBytes[curLeft:curRight+1])	}	ReverseBytes(strBytes[0:])	res = string(strBytes)	return}

1.2 字符串包含

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？

为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)

比如，如果是下面两个字符串：

String 1：ABCD

String 2：BAD

答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。

如果是下面两个字符串：

String 1：ABCD

String 2：BCE

答案是false，因为字符串String2里的E字母不在字符串String1里。

同时，如果string1：ABCD，string 2：AA，同样返回true。

func StringContain(a string, b string) (isContain bool) {	isContain = true	aCharMap := make(map[byte]int)	aBytes := []byte(a)	for _, ch := range aBytes {		aCharMap[ch] += 1	}	bBytes := []byte(b)	for _, ch := range bBytes {		_, ok := aCharMap[ch]		if ok == false {			isContain = false			break		}	}	return}

1.3 字符串的全排列

输入一个字符串，打印出该字符串中字符的所有排列。

例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串

abc、acb、bac、bca、cab 和 cba。

解法1，递归解法（Go的递归传递很奇怪）

package mainimport "fmt"func Swap(str []byte, i int, j int) {	tmpVal := str[i]	str[i] = str[j]	str[j] = tmpVal}var list []stringfunc Permutation(str []byte, tmpRes[]byte) {	strLen := len(str)	if strLen < 1 {		return	}	if strLen == 1 {		tmpFinalRes := string(append(tmpRes, str[0]))		list = append(list, tmpFinalRes)		return	}	for i := 0; i < strLen; i++ {		Swap(str, 0, i)		tmpRes = append(tmpRes, str[0])		Permutation(str[1:], tmpRes)		tmpRes = tmpRes[0:len(tmpRes) - 1]		Swap(str, i, 0)	}	return}func main() {	tmpStr := []byte("ABC")	var tmpRes []byte	Permutation(tmpStr, tmpRes)	fmt.Println(list)}

找到下一个，STL的next_permutation的思想

package mainimport "fmt"func Swap(str []byte, i int, j int) {	tmpVal := str[i]	str[i] = str[j]	str[j] = tmpVal}func Reverse(strBytes []byte) {	tmpLen := len(strBytes)	if tmpLen <= 1 {		return	}	tailIndex := tmpLen - 1	for headIndex := 0 ; headIndex < tailIndex; headIndex++{		tmpVal := strBytes[headIndex]		strBytes[headIndex] = strBytes[tailIndex]		strBytes[tailIndex] = tmpVal		tailIndex--	}	return}func NextPermutation(str[] byte) (isEnd bool){	isEnd = false	strLen := len(str)	var i int	for i = strLen - 2; i >= 0 && str[i] > str[i+1]; i-- {	}	if i < 0 {		isEnd = true		return	}	var k int	for k = strLen - 1; k > i && str[k] < str[i]; k-- {	}	Swap(str, i, k)	Reverse(str[i+1:])	return}func main() {	tmpStr := []byte("abc")	fmt.Println(string(tmpStr))	for {		isEnd := NextPermutation(tmpStr)		fmt.Println(string(tmpStr))		if isEnd {			break		}	}}

1.4 字典序的全排列

已知字符串里的字符是互不相同的，现在任意组合，比如ab，则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。

分析：非简单的全排列问题（跟全排列的形式不同,abc全排列的话，只有6个不同的输出）。 本题可用递归的思想，设置一个变量表示已输出的个数，然后当个数达到字符串长度时，就输出。

package mainimport "fmt"var allList []stringfunc AllPermutation(str []byte, tmpRes []byte, curDeepLen int, maxLen int) {	strLen := len(str)	if strLen <= 0 {		return	}	if curDeepLen == maxLen {		allList = append(allList, string(tmpRes))		return	}	for i := 0; i < strLen; i++ {		tmpRes = append(tmpRes, str[i])		AllPermutation(str, tmpRes, curDeepLen + 1, maxLen)		tmpRes = tmpRes[0:(len(tmpRes) - 1)]	}}func main() {	tmpStr := []byte("ab")	var tmpRes []byte	AllPermutation(tmpStr, tmpRes, 0, 2)	fmt.Println(allList)}

1.5 字符的所有组合

如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？当输入的字符串中含有相同的字符串时，相同的字符交换位置是不同的排列，但是同一个组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

package mainimport "fmt"var allListPair []stringfunc AllPair(str []byte, tmpRes []byte, length int) {	strLen := len(str)	if strLen < 1 {		return	}	if length == 1 {		for i := 0; i < strLen; i++ {			allListPair = append(allListPair, string(append(tmpRes, str[i])))		}		return	}	tmpWithFirst := append(tmpRes, str[0])	AllPair(str[1:], tmpWithFirst, length - 1)	AllPair(str[1:], tmpRes, length)}func main() {	tmpStr := []byte("abc")	var tmpRes []byte	tmpLen := len(tmpStr)	for i := 1; i <= tmpLen; i++ {		AllPair(tmpStr, tmpRes, i)	}	fmt.Println(allListPair)}