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 ans

if __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助力您的未来发展。