leetcode
leetcode 1501 ~ 1550
具有给定数值的最小字符串

具有给定数值的最小字符串

难度:

标签:

题目描述

代码结果

运行时间: 35 ms, 内存: 16.5 MB


/*
 * 题目思路:
 * 我们使用 Java Streams 来简化字符串的生成过程。
 * 首先生成一个含有 n 个 'a' 的字符数组,然后通过调节每个字符的数值来达到 k 的总和。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String getSmallestString(int n, int k) {
        // 初始数值减去 n * 1,因为每个 'a' 的数值是 1
        k -= n;
        // 使用 IntStream 创建字符数组并转换为字符串
        return IntStream.range(0, n)
                .mapToObj(i -> {
                    // 从末尾开始增加数值
                    int add = Math.min(k, 25);
                    k -= add;
                    return String.valueOf((char)('a' + add));
                })
                .sorted((a, b) -> -a.compareTo(b)) // 倒序排列
                .collect(Collectors.joining());
    }
}

解释

方法:

这个题解的策略是首先尽可能地使用字符 'z'(数值为 26),因为我们想要字典序最小的字符串,所以 'z' 应尽可能地放在字符串的末尾。通过计算 k-n,我们可以得知除了全部用 'a' 以外我们还需要多少数值,因为每个 'a' 贡献了 1 点数值,所以 k-n 就是除了全 'a' 字符串外需要的额外数值。然后,这个额外的数值用尽量少的 'z' 字符来构成,每个 'z' 能贡献 25 点(因为 'z' = 26 而一个 'a' 已经计算过了)。divmod(k-n, 25) 可以得到需要多少个 'z' 和剩下的余数,余数将通过一个字符('a' 到 'y' 之间)来补充。最后,构造这个字符串:先放尽可能多的 'a',接着是一个由余数确定的字符,最后是所有的 'z'。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到通过计算 `k-n` 来确定需要除 'a' 之外的额外数值,在某些输入下 `k-n` 是否可能为负?如果是,应如何处理?
在题解的设定中,`k-n` 表示除了每个位置最小可能值 'a' 外,额外需要的总数值。理论上,`k` 应不小于 `n`(因为每个位置最小是 'a',总和至少为 `n`)。如果 `k-n` 为负,这可能表示输入参数不合理,因为 `k` 应至少等于 `n`。在实际应用中应检查输入值,确保 `k >= n`,否则返回输入错误。
🦆
在题解中,`divmod(k-n, 25)` 用于计算需要多少个 'z' 和余数,但如果 `k-n` 小于 25 会如何影响构建过程?
如果 `k-n` 小于 25,`divmod(k-n, 25)` 的结果是 `(0, k-n)`。这意味着不需要 'z' 字符,余数 `k-n` 将直接转化为一个对应的字符(从 'a' 到 'y')。在这种情况下,字符串将由 `n-1` 个 'a' 和一个字符 `chr(ord('a') + (k-n-1))` 组成,没有 'z' 字符。
🦆
题解中构建最终字符串时,使用了表达式 `chr(ord('a') + q)` 来添加一个字符,这里的 `q` 是否有可能超过 25?如果超过了如何处理?
在正常逻辑下,`q` 作为 `divmod(k-n, 25)` 的余数,其值范围是 0 到 24。因此,`q` 不可能超过 25。如果 `q` 超过 25,这将是代码实现或逻辑错误,应重新检查 `divmod` 的使用是否正确。
🦆
题解假设添加的 'z' 字符始终足以构建所需的数值,但如果 `p` 的计算结果为0,即不需要添加 'z',这种情况下的字符串构建逻辑是否仍然有效?
当 `p` 为 0 时,表示不需要添加任何 'z' 字符。这种情况下,字符串将由 `n-1` 个 'a' 和一个由余数 `q` 确定的字符组成(`chr(ord('a') + q)`),余数 `q` 正是 `k-n` 的值。因此,构建逻辑在 `p` 为 0 时依然有效,只是字符串中不包含 'z' 字符。

相关问题