题目
思想:
注意预处理和前缀和
前缀和是一种算法,用于求出一个数组的前缀和。数组的前缀和定义为在数组的某个位置的前缀元素的和。换句话说,前缀和就是将一个数组的每个位置的元素与其之前的元素相加。
这个代码使用前缀和来优化查询过程。它预处理了每个单词的首尾字母是否是元音,然后将这些结果保存在一个列表中。然后,它使用前缀和计算每个查询结果。
具体来说,对于每个查询 (i, j),它将统计从 words[i] 到 words[j] 中满足条件(首尾字母都是元音)的单词数。这可以通过使用 counts[j+1] - counts[i] 来完成。这是因为 counts[j+1] 包含了从 words[0] 到 words[j] 中满足条件的单词数,而 counts[i] 包含了从 words[0] 到 words[i-1] 中满足条件的单词数。因此,counts[j+1] - counts[i] 即为从 words[i] 到 words[j] 中满足条件的单词数。
在代码中,counts 数组使用前缀和预处理,因此可以在 O(1) 时间内计算每个查询的结果。这使代码的总运行时间从 O(n^2) 降至 O(n)
1 | class Solution: |
1 | class Solution: |