算法编程题-煎饼排序 不含AAA或者BBB的字符串

煎饼排序

原题描述

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 := 0
		for 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 := 0
		for 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 - 1
		nb -= gap
		mb += 2 * gap
	}
	if nb + mb - na - ma > 1 {
		gap := nb + mb - na - ma - 1
		na -= gap
		ma += 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, ch1
		na, ma, nb, mb = nb, mb, na, ma
	}
	strs := make([]byte, na * 2 + nb * 2 + ma + mb)
	i := 0
	j := 0
	k := 0
	for i < na * 2 + ma || j < nb * 2 + mb {
		if i < na * 2 {
			strs[k] = ch1
			k++
			strs[k] = ch1
			k++
			i += 2
		} else if i < na * 2 + ma {
			strs[k] = ch1
			i++
			k++
		}

		if j < nb * 2 {
			strs[k] = ch2
			k++
			strs[k] = ch2
			k++
			j += 2
		} else if j < nb * 2 + mb {
			strs[k] = ch2
			j++
			k++
		}
	}
	return string(strs)
}

LeetCode运行截图如下：

复杂度分析

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