摘要：本文将对两道LeetCode原题进行介绍，分别是煎饼排序和不含AAA或者BBB的字符串。在陈述完基本的思路后，本文给出基于golang语言实现的代码，实现都是通过了所有测试用例且运行时间超过100%的优质解法，最后给出相应的复杂度分析。
关键词：算法，LeetCode，Golang，排序，双指针

煎饼排序

原题描述

LeetCode 969 煎饼排序：对于一个数组nums，每一次可以选择一个数k（1 << k << len(nums)），将nums[:k]范围内的数字进行翻转，现在需要基于这种翻转操作完成数组的排序，给出能将数组排好序的k值的一个序列。注意，任何长度小于10 * len(nums)的可行序列都是正确的。

思路简述

可以这样去想，对于任何一个位置k的数来说，我们都可以通过两次翻转操作将其移动到数组的尾部，分别是翻转nums[: k]和翻转整个nums，第一次翻转将这个数翻到了头部，第二次则是将其翻转到了尾部。因此，我们可以每一次都针对最大数进行以上的翻转，然后下一次考虑更小的一个序列。这样就能够完成整个数组的排序，且翻转次数不会超过2 * （n - 1）次。

代码实现

func pancakeSort(arr []int) []int {n := len(arr)res := make([]int, 0, 2 * n)for i := n - 1; i > 0; i-- {// 先找当前序列[0: i]的最大数的位置maxi := 0for j := 0; j <= i; j++ {if arr[j] > arr[maxi] {maxi = j}}if maxi == i {  // 最大数在当前序列的尾部，不需要翻转continue}if maxi != 0 {  // 最大数在头部，只需要进行第二次翻转res = append(res, maxi + 1)}res = append(res, i + 1)// 以下为整理翻转后的数组newArr := make([]int, n)k := 0for j := i; j > maxi; j-- {newArr[k] = arr[j]k++}for j := 0; j < maxi; j++ {newArr[k] = arr[j]k++}arr = newArr}return res
}

LeetCode运行截图如下：

复杂度分析

• 时间复杂度：$O(n^2)$，其中n为数组的长度
• 空间复杂度：$O(n)$

不含AAA或者BBB的字符串

原题描述

LeetCode 984 不含AAA或者BBB的字符串给定两个数字a和b，要求构造一个长度为a+b的字符串，且该字符串中恰好包含a个’a’字符和b个’b’字符，且不能出现连续的"aaa"或者"bbb"的子串。

思路简述

想要达到不出现陆续三个同样的字符，需要用一个字符或者两个字符将彼此之间隔断。考虑来说，假设"aa"或者"a"段的个数为n，“bb"或者"b"段的个数为m，只要m与n的差的绝对值小于1，那么一定可以构造出一个合法的字符串。因此，可以去计算"aa"段的最大个数，以及在这个最大个数下"a"的个数，以及"bb"和"b"的个数，如果在数量要求上不满足以上的等式，则可以将少的一边的"bb"段分解为两个"b”，直到达到上述要求。

代码实现

func strWithout3a3b(a int, b int) string {na, ma := a / 2, a % 2   // na和ma分别表示"aa"和"a"两种段的个数nb, mb := b / 2, b % 2// 接下来调整，目标是将|na+ma-nb-mb|<=1// for na + ma - nb - mb > 1 && nb > 0 {// 	nb--// 	mb += 2// }// for nb + mb - na - ma > 1 && na > 0 {// 	na--// 	ma += 2// }if na + ma - nb - mb > 1 {gap := na + ma - nb - mb - 1nb -= gapmb += 2 * gap}if nb + mb - na - ma > 1 {gap := nb + mb - na - ma - 1na -= gapma += 2 * gap}if na + ma - nb - mb <= 1 || na + ma - nb - mb >= -1 {return buildStr(na, ma, nb, mb)}return ""
}func buildStr(na, ma, nb, mb int) string {var ch1 byte = 'a'var ch2 byte = 'b'if na + ma < nb + mb {ch1, ch2 = ch2, ch1na, ma, nb, mb = nb, mb, na, ma}strs := make([]byte, na * 2 + nb * 2 + ma + mb)i := 0j := 0k := 0for i < na * 2 + ma || j < nb * 2 + mb {if i < na * 2 {strs[k] = ch1k++strs[k] = ch1k++i += 2} else if i < na * 2 + ma {strs[k] = ch1i++k++}if j < nb * 2 {strs[k] = ch2k++strs[k] = ch2k++j += 2} else if j < nb * 2 + mb {strs[k] = ch2j++k++}}return string(strs)
}

LeetCode运行截图如下：

复杂度分析

• 时间复杂度：$O(a+b)$
• 空间复杂度：$O(a+b)$