leetcode
leetcode 1951 ~ 2000
字符串的总引力

字符串的总引力

难度:

标签:

题目描述

代码结果

运行时间: 100 ms, 内存: 16.4 MB


/*
 * 思路:
 * 使用Java Stream API来计算总引力。
 * 对于每一个子字符串,使用一个Set来存储不同的字符,
 * 然后使用Set的大小来计算引力。
 */
import java.util.Set;
import java.util.stream.IntStream;
import java.util.HashSet;
public class Solution {
    public int totalGravity(String s) {
        return IntStream.range(0, s.length())
            .map(i -> IntStream.range(i, s.length())
                .map(j -> {
                    Set<Character> uniqueChars = new HashSet<>();
                    s.substring(i, j + 1).chars().forEach(c -> uniqueChars.add((char)c));
                    return uniqueChars.size();
                }).sum())
            .sum();
    }
}

解释

方法:

这个题解利用了动态规划的思想与最后一次出现位置的记录来计算字符串的总引力。定义 sum_g 为到当前字符为止的所有子字符串的引力总和,ans 为到目前为止所有字符产生的引力总和。遍历字符串的每个字符,更新当前字符的最后出现位置。对于每个字符 c,在位置 i,计算新增引力 sum_g += i - last.get(c, -1),其中 last.get(c, -1) 给出字符 c 上一次出现的位置(如果没有出现过则为 -1)。然后将 sum_g 累加到答案 ans 中。这种方法有效地避免了对每个子字符串进行单独的引力计算,降低了计算复杂度。

时间复杂度:

O(n)

空间复杂度:

O(min(n, 26))

代码细节讲解

🦆
题解中提到使用动态规划的思想,请问这个动态规划的状态是如何定义的?
在这个题解中,动态规划的状态是通过变量 sum_g 来定义的,它表示包含当前字符 c 的所有子字符串的引力总和。这个状态在每一个字符的处理中被更新,以便计算出从字符串开始到当前字符为止的所有可能子字符串的引力总和。状态转移则是通过考虑当前字符最后一次出现位置与之前的出现位置之间的差异来进行,这样每次仅需更新一次状态,即可得到包含当前字符的所有子字符串的新增引力。
🦆
题解提到每次循环时,更新引力总和 sum_g += i - last.get(c, -1);这个表达式具体是如何计算新引力的?
这个表达式中,`i` 是当前字符 c 的索引,而 `last.get(c, -1)` 返回字符 c 上一次出现的位置,默认为 -1 如果之前未出现过。表达式 `i - last.get(c, -1)` 计算的是从上一次字符 c 出现的位置后一个位置到当前位置的距离,这个距离正好等于以当前字符 c 结尾的、包含字符 c 的所有新子字符串的数量。因此,sum_g 加上这个值表示将这些新子字符串的引力加到总引力中。
🦆
为什么更新字符的最后出现位置 last[c] = i 后,不需要再处理之前的出现位置对引力的影响?
更新字符的最后出现位置是为了记录这个字符最近一次出现的位置,这样在下次该字符再次出现时,可以计算出自上次出现以来新增的子字符串数量。一旦我们更新了这个位置,之前的出现位置对于未来的计算就不再有直接的影响,因为我们只关心最后一次出现到当前位置的新子字符串。因此,每次只需考虑当前的字符和它的最新出现位置,不需要回溯处理旧的出现位置。
🦆
如果字符串中含有非常多的重复字符,这种方法的效率如何?会不会因为重复字符较多而影响性能?
此方法的效率与字符串中字符的重复性没有直接关系,因为无论字符是否重复,算法都是线性遍历每个字符并更新状态。每次更新操作的时间复杂度是常数级的,所以总的时间复杂度依然是 O(n),其中 n 是字符串的长度。因此,即便字符串中重复字符很多,也不会对性能造成负面影响。这种方法的效率主要受到字符串长度的影响,而非字符的重复性。

相关问题