2026-11-21:字符对转换后字典序最大的字符串。用go语言,给定一个整数数组 nums。对数组中的每个元素 x,先构造一个长度为 x、全部由小写字母 a 组成的字符串。
之后可以重复执行一种变换:若字符串中存在两个相邻且相同的字母,就把它们替换成字母表中紧随其后的那个字母。例如,aa 可变为 b,bb 可变为 c;但 z 后面没有字母,所以 zz 不能再变。
对于每个 x,需要在所有能够得到的字符串中,找出字典序最大的那个。最后按照 nums 中元素的顺序,把对应的最大字符串组成一个字符串数组返回。
字典序比较规则如下:从左到右比较两个字符串,在第一个不同的位置上,字母更靠后的字符串更大;如果其中一个字符串是另一个字符串的前缀,则长度更长的字符串更大。
每个 x 的求解过程相互独立。
1 <= nums.length <= 100000。
1 <= nums[i] <= 1000000000。
输入: nums = [2,5,7]。
输出: ["b","ca","cba"]。
解释:
nums[0] = 2:"aa" → "b"。
nums[1] = 5:"aaaaa" → "baaa" → "bba" → "ca"。
nums[2] = 7:"aaaaaaa" → "baaaaa" → "bbaaa" → "bbba" → "cba"。
因此,ans = ["b", "ca", "cba"]。
题目来自力扣4036。
大体步骤如下:
一、整体框架
对数组 nums 中的每一个整数 x 独立求解。为每个 x 生成一个字符串,最终按照原数组顺序把所有答案字符串放进结果数组返回。不同 x 之间没有任何依赖,前一个元素的结果不会影响后一个元素。
二、单个 x 的构造过程
对于当前的 x,不实际从长度为 x 的全 a 字符串开始一步步模拟相邻相同字母合并,而是直接利用合并规律构造字典序最大的结果。
合并规律可以这样理解:字母表中第 0 个字母是 a,第 1 个是 b,第 2 个是 c,依此类推,第 25 个是 z。连续两个相同字母可以合并成后一个字母,因此 2 个 a 可以变成一个 b,4 个 a 可以变成一个 c,8 个 a 可以变成一个 d。一般地,2 的 i 次方个 a 最终可以合并成字母表中下标为 i 的字母,也就是从 a 往后数第 i 个字母。
由于字母表到 z 就结束,下标 25 对应 z,不能再往更高的字母合并。因此需要把 x 分成两部分:
第一部分是完整包含多少个 2 的 25 次方。这个数量等于 x 右移 25 位,也就是 x 除以 2 的 25 次方后取整数商。每一个这样的完整块都可以变成一个 z。因为 z 已经是最大字母,而且两个 z 不能再合并,所以这些 z 应当直接放在结果字符串的最前面。z 的数量就是 x 右移 25 位得到的值。
第二部分是 x 中低 25 位的部分,也就是除去所有完整 2 的 25 次方块之后剩下的部分。低 25 位对应字母 a 到 y,下标范围是 0 到 24。
接下来处理低 25 位:
先求出 x 的最高有效二进制位下标。这个下标表示 x 用二进制表示时最高位 1 所在的位置。例如 x 的二进制长度减一就是最高有效位下标。然后把这个下标限制在不超过 24,因为更高的部分已经用 z 处理过了。
之后从高位到低位依次检查低 25 位中的每一位。对于当前位置 i,检查 x 的二进制第 i 位是否为 1。
如果第 i 位是 1,说明 x 中包含 2 的 i 次方这一块。这一块可以完全合并成字母表中下标为 i 的字母,也就是从 a 开始往后数第 i 个字母。把这个字母追加到当前结果字符串的末尾。
如果第 i 位是 0,说明没有这一块,不需要追加任何字符,直接继续检查下一位。
由于遍历顺序是从高位到低位,也就是从较大的字母到较小的字母,因此追加到结果中的字母整体上是从大到小排列的。这样可以让较大的字母尽量出现在字符串前面,从而得到字典序最大的字符串。
处理完所有允许的低位之后,当前结果字符串就是 x 对应的答案。把该字符串放入答案数组的对应位置。
三、为什么这样构造是字典序最大的
合并操作本质上是在把若干个 a 按照二进制权重向上合并。2 的 i 次方个 a 可以变成一个下标为 i 的字母。对于低 25 位,x 的二进制表示是唯一的,因此能合并出的字母集合也是确定的:某一位为 1,就对应一个该位下标的字母;某一位为 0,就没有这个字母。
在字母集合确定后,字典序比较时越靠前的字符影响越大。把较大的字母放在前面,一定会使字符串字典序更大。因此应当先放 z,再按照字母下标从大到小依次放低 25 位对应的字母。代码中的构造正好符合这一点:先放所有 z,然后从最高有效位向下检查,遇到为 1 的位就追加对应字母。
四、用示例说明
当 x 等于 2 时,2 右移 25 位得到 0,所以没有 z。低位的最高有效位是 1。检查第 1 位为 1,对应字母 b;第 0 位为 0,不追加。结果是 b。
当 x 等于 5 时,5 的二进制是 101。右移 25 位为 0,没有 z。最高有效位是 2。第 2 位为 1,追加 c;第 1 位为 0,跳过;第 0 位为 1,追加 a。结果是 ca。
当 x 等于 7 时,7 的二进制是 111。没有 z。第 2 位为 1 追加 c;第 1 位为 1 追加 b;第 0 位为 1 追加 a。结果是 cba。
因此示例 nums 等于 2、5、7 时,返回 b、ca、cba。
五、总时间复杂度
设 n 是 nums 的长度。对每个 x,低 25 位的检查最多进行 25 次,也就是常数次;额外追加 z 的次数是 x 右移 25 位。对于题目给定的 x 不超过 10 的 9 次方,x 右移 25 位最多约为 29,也是一个很小的常数。每个 x 构造出的字符串长度最多约为 25 加 29,即最多约 54 个字符。因此每个元素的处理时间有常数上界。
总时间复杂度为 O(n)(在题目给定数值范围下)。如果不利用具体上界,可以写成 O(n 乘以每个元素处理其低位和高位块的数量),即与 n 和每个 x 的二进制长度以及 x 除以 2 的 25 次方的商有关;在给定约束下简化为 O(n)。
六、总额外空间复杂度
如果不把最终返回的字符串数组及其内容算作额外空间,那么每个元素只需要一个临时字符串,其长度最多约为 54 个字符,是常数大小,因此额外空间复杂度为 O(1)。
如果把最终返回的答案数组以及其中所有字符串内容也算入空间,那么所有答案字符串的总长度最多约为 54 乘以 n,因此总空间复杂度为 O(n)。在题目约束下,这个 n 的量级就是答案总字符数的量级。
Go完整代码如下:
package main
import (
"bytes"
"fmt"
"math/bits"
)
func largestString(nums []int) []string {
ans := make([]string, len(nums))
for idx, x := range nums {
// 单独处理 'z'
s := bytes.Repeat([]byte{'z'}, x>>25)
// 然后从 'y' 到 'a'
for i := min(24, bits.Len(uint(x))-1); i >= 0; i-- {
if x>>i&1 > 0 { // x 的 i 位是 1,所以有字母 i
s = append(s, 'a'+byte(i))
}
}
ans[idx] = string(s)
}
return ans
}func main() {
nums := []int{2, 5, 7}
result := largestString(nums)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
def largestString(nums):
ans = []
for x in nums:
# 先构造 x >> 25 个 'z'
parts = ['z'] * (x >> 25)
# 从 min(24, x.bit_length() - 1) 到 0 遍历
upper = min(24, x.bit_length() - 1)
for i in range(upper, -1, -1):
if (x >> i) & 1:
parts.append(chr(ord('a') + i))
ans.append(''.join(parts))
return ansif __name__ == "__main__":
nums = [2, 5, 7]
result = largestString(nums)
print(result)
C++完整代码如下:
std::vector
string
> largestString(
const
std::vector<
int
>& nums) {
std::vector
string
> ans;
ans.reserve(nums.size());
for
(
int
x : nums) {
std::
string
s;
// 单独处理 'z':x >> 25 个 'z'
s.
append
(x >>
25
,
'z'
);
// 等价于 bits.Len(uint(x)) - 1,即 floor(log2(x))
int
upper =
-1
;
for
(
int
t = x; t >
0
; t >>=
1
) {
++upper;
}
upper = std::min(
24
, upper);
// 从高位到低位,检查 x 的第 i 位是否为 1
for
(
int
i = upper; i >=
0
; --i) {
if
((x >> i) &
1
) {
s.push_back(static_cast
(
'a'
+ i));
}
}
ans.push_back(std::move(s));
}
return
ans;
}
int
main() {
std::vector<
int
> nums = {
2
,
5
,
7
};
std::vector
string
> result = largestString(nums);
for
(
const
auto& s : result) {
std::cout << s <<
' '
;
}
std::cout << std::endl;
return
0
;
}
芯谷ai:xinguhub.com/sign-up?aff=txk5
我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。
热门跟贴