题目描述

3304. 找出第 K 个字符 I

提示

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k。

现在 Bob 会要求 Alice 执行以下操作 无限次 :

将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。
例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行足够多的操作后， word 中 至少 存在 k 个字符，此时返回 word 中第 k 个字符的值。

示例 1:

输入：k = 5

输出：”b”

解释：

最初，word = “a”。需要进行三次操作:

生成的字符串是 “b”，word 变为 “ab”。
生成的字符串是 “bc”，word 变为 “abbc”。
生成的字符串是 “bccd”，word 变为 “abbcbccd”。

示例 2:

输入：k = 10

输出：”c”

提示：

1 <= k <= 500

3307. 找出第 K 个字符 II

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = “a”。

给定一个正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。

现在 Bob 将要求 Alice 按顺序执行 所有 操作：

如果 operations[i] == 0，将 word 的一份 副本追加 到它自身。
如果 operations[i] == 1，将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 “c” 进行操作生成 “cd”，对 “zb” 进行操作生成 “zbac”。
在执行所有操作后，返回 word 中第 k 个字符的值。

注意，在第二种类型的操作中，字符 ‘z’ 可以变成 ‘a’。

示例 1:

输入：k = 5, operations = [0,0,0]

输出：”a”

解释：

最初，word == “a”。Alice 按以下方式执行三次操作：

将 “a” 附加到 “a”，word 变为 “aa”。
将 “aa” 附加到 “aa”，word 变为 “aaaa”。
将 “aaaa” 附加到 “aaaa”，word 变为 “aaaaaaaa”。

示例 2:

输入：k = 10, operations = [0,1,0,1]

输出：”b”

解释：

最初，word == “a”。Alice 按以下方式执行四次操作：

将 “a” 附加到 “a”，word 变为 “aa”。
将 “bb” 附加到 “aa”，word 变为 “aabb”。
将 “aabb” 附加到 “aabb”，word 变为 “aabbaabb”。
将 “bbccbbcc” 附加到 “aabbaabb”，word 变为 “aabbaabbbbccbbcc”。

提示：

  • 1 <= k <= 1014
  • 1 <= operations.length <= 100
  • operations[i] 可以是 0 或 1。
  • 输入保证在执行所有操作后，word 至少有 k 个字符。

解题思路

这两道差不多，不知道为什么会把 3304 设置为简单题，可能是可以用暴力法直接模拟出来吧。如果从递归角度考虑，其实可以优先解决 3307。

由题目可以知道，每次操作后，字符串长度都会变为原来的两倍。因此，我们可以通过记录每次操作后字符串的长度来快速定位第 k 个字符。题目中已经保证在执行所有操作后，字符串至少有 k 个字符，所以我们可以直接计算出所有操作后的字符串长度，如果 operations 长度为 n，那么最终字符串的长度为 。

递归解法

那么现在考虑如何在 长的字符串中，找到第 k 个字符，可以使用递归来解决这个问题。由于字符串的后一半是前一半的变换，因此首先判断第 k 个字符是在前一半还是后一半：

  • 如果在前一半，那么相当于最后一次操作没有发生变化，直接递归到前一半；
  • 如果在后一半，那么相当于最后一次操作发生了变化，需要先找到前一半的字符，然后根据最后一次操作的类型进行变换。

据此就可以构建出一个递归方程：

在执行完所有操作后，找到第个字符的值

所以可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
func kthCharacter(k int64, operations []int) byte {
	if len(operations) == 0 {
		return 'a'
	}

	if x := int64(1) << min(len(operations)-1, 62); k <= x {
		return kthCharacter(k, operations[:len(operations)-1])
	} else {
		return byte((int(kthCharacter(k-x, operations[:len(operations)-1])-'a')+operations[len(operations)-1])%26 + 'a')
	}
}

应当说用递归的方式来解决这个问题是非常直观的，时间复杂度为 O(n)，其中 n 是 operations 的长度。空间复杂度为 O(n)，主要是递归栈的空间。

上面用了 min(len(operations)-1, 62) 是因为 k 的数据类型是 int64（也就是 -(1 << 63) ~ (1 << 63 - 1)），所以如果 len(operations) > 62，那么 2^{len(operations)-1} 的值会超过 int64 的范围，因此 k 一定落在字符串的前半段，可以直接递归到前半段。

迭代解法

参照上面的代码继续思考，就可以得到迭代法的思路：这里其实本质就是在统计第 k 个字符是由字符 a 在 n 操作中变化了多少次。所以可以从后往前遍历 len(operations)，每次判断 k 是否在前半段，如果在前半段就继续往前遍历；如果在后半段，就根据操作类型确定字符是否发生变化。

1
2
3
4
5
6
7
8
9
10
11
func kthCharacter(k int64, operations []int) byte {
	ans := 0
	for i := min(len(operations)-1, 62); i >= 0; i-- {
		if x := int64(1) << i; k > x {
			k -= x
			ans += operations[i]
		}
	}

	return byte('a' + (ans % 26))
}

时间复杂度为 O(n)，其中 n 是 operations 的长度。空间复杂度为 O(1)，因为只使用了常数级别的额外空间。

到这里就完成了对 3307 的解答。而对于 3304，由于它的操作类型只有一种（即只进行字符变换），因此可以直接使用上面的迭代法。

1
2
3
4
5
6
7
8
9
10
11
func findKthCharacter(k int) byte {
	ans := 0
	for i := 62; i >= 0; i-- {
		if x := 1 << i; k > x {
			k -= x
			ans++
		}
	}

	return byte('a' + (ans % 26))
}

这里由于没有 operations 数组，所以直接从 62 开始遍历，直到 0。每次判断 k 是否在前半段，如果在后半段就增加 ans 的值。当然考虑到题干中 k 的范围是 1 <= k <= 500，所以实际上只需要遍历到 8 就可以了，因为 、，所以 8 已经足够覆盖所有可能的 k 值。

这里进一步分析就可以发现，不应该每次都从 62 开始遍历，而是可以根据 k 的值动态调整遍历的起始位置，也就是找到一个 i，使得 。这样可以减少不必要的遍历次数。

如何找到这个 i 呢？直接说结论，就是 bits.Len64(uint64(k)) - 1，也就是求出 k 的二进制位数长度，然后减去 1。这样就可以得到一个更简洁的代码实现。

代码实现

3304. 找出第 K 个字符 I

1
2
3
4
5
6
7
8
9
10
11
func kthCharacter(k int) byte {
	ans := 0
	for x := 1 << (bits.Len64(uint64(k)) - 1); x >= 1; x = x >> 1 {
		if k > x {
			k -= x
			ans++
		}
	}

	return byte('a' + (ans % 26))
}

基于此就可以完成对 3304 的解答。

3307. 找出第 K 个字符 II

1
2
3
4
5
6
7
8
9
10
11
func kthCharacter(k int64, operations []int) byte {
	ans := 0
	for i := bits.Len64(uint64(k)) - 1; i >= 0; i-- {
		if x := int64(1) << i; k > x {
			k -= x
			ans += operations[i]
		}
	}

	return byte('a' + (ans % 26))
}