字符串的总引力
难度:
标签:
题目描述
代码结果
运行时间: 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 += i - last.get(c, -1);这个表达式具体是如何计算新引力的?
▷🦆
为什么更新字符的最后出现位置 last[c] = i 后,不需要再处理之前的出现位置对引力的影响?
▷🦆
如果字符串中含有非常多的重复字符,这种方法的效率如何?会不会因为重复字符较多而影响性能?
▷