每日算法学习记录 - 250531

今天完成了两道 LeetCode 题目，主要用到了前缀和的思想。记录如下：

---

1. 2559. 统计范围内的元音字符串数

题目

思路

前缀和

解题过程

我们可以先预处理出一个前缀和数组 nums，其中 nums[i] 表示 words 数组中从下标 0 到下标 i（包含 i）的字符串里，以元音字母开头且以元音字母结尾的字符串的总个数。

预处理完成后，对于每个查询 [left, right]：

• 如果 left == 0，则区间 [0, right] 内满足条件的字符串数量就是 nums[right]。
• 如果 left > 0，则区间 [left, right] 内满足条件的字符串数量为 nums[right] - nums[left - 1]。

复杂度

• 设 m 为 words 数组的长度，n 为 queries 数组的长度。
• 时间复杂度: $O(m+n)$
  • 预处理前缀和数组 nums：遍历 words 数组一次，对每个单词调用 isVowel。isVowel 操作检查首尾字符，可视为 $O(1)$。总共 $O(m)$。
  • 处理 n 个查询：每个查询通过前缀和数组 $O(1)$ 计算。总共 $O(n)$。
  • 因此，总时间复杂度为 $O(m+n)$。
• 空间复杂度: $O(m)$
  • 用于存储前缀和数组 nums。

Code

class Solution {public int[] vowelStrings(String[] words, int[][] queries) {int n = queries.length, m = words.length;int[] ret = new int[n], nums = new int[m];nums[0] = isVowel(words[0]);for (int i = 1; i < m; i++) {nums[i] = nums[i - 1] + isVowel(words[i]);}for (int i = 0; i < n; i++) {int left = queries[i][0], right = queries[i][1];ret[i] = left == 0 ? nums[right] : nums[right] - nums[left - 1];}return ret;}private int isVowel(String s) {int n = s.length();if ((s.charAt(0) == 'a' || s.charAt(0) == 'e' || s.charAt(0) == 'i' || s.charAt(0) == 'o' || s.charAt(0) == 'u') && (s.charAt(n - 1) == 'a' || s.charAt(n - 1) == 'e' || s.charAt(n - 1) == 'i' || s.charAt(n - 1) == 'o' || s.charAt(n - 1) == 'u')) {return 1;}return 0;}
}

---

2. 3152. 特殊数组 II

题目

思路

前缀和

解题过程

一个数组 nums 的子数组 nums[from...to] 是“特殊”的，当且仅当其中所有相邻元素的奇偶性都不同。

我们可以预处理一个前缀和数组 prefixBadPairs。prefixBadPairs[i] (for i > 0) 表示在 nums 数组的 nums[0...i] 部分中，有多少对相邻元素 (nums[k-1], nums[k]) (其中 1 <= k <= i) 具有相同的奇偶性（我们称之为“坏对”）。prefixBadPairs[0] 可以设为 0。

对于一个查询 [from, to]：

• 如果 from == to，子数组只有一个元素，根据定义它总是特殊的。
• 如果 from < to，我们需要检查 nums[from...to] 中是否存在“坏对”。
  这些“坏对”可能发生在 (nums[from], nums[from+1]), (nums[from+1], nums[from+2]), …, (nums[to-1], nums[to])。
  • prefixBadPairs[to] 包含从 (nums[0],nums[1]) 到 (nums[to-1],nums[to]) 的所有坏对。
  • prefixBadPairs[from] 包含从 (nums[0],nums[1]) 到 (nums[from-1],nums[from]) 的所有坏对。
  • 他们的差值 prefixBadPairs[to] - prefixBadPairs[from] 即为从 (nums[from],nums[from+1]) 到 (nums[to-1],nums[to]) 范围内的坏对数量。
• 如果这个差值为 0，则说明子数组 nums[from...to] 中没有相邻元素奇偶性相同，该子数组是特殊的，结果为 true。否则，结果为 false。

复杂度

• 设 N 为 nums 数组的长度，M 为 queries 数组的长度。
• 时间复杂度: $O(N+M)$
  • 预处理 prefixBadPairs 数组需要 $O(N)$ 时间。
  • 处理 M 个查询，每个查询 $O(1)$ 时间。
• 空间复杂度: $O(N)$
  • 用于存储 prefixBadPairs 数组。

Code

class Solution {public boolean[] isArraySpecial(int[] nums, int[][] queries) {int n = nums.length, m = queries.length;boolean[] ret = new boolean[m];int[] prefixBadPairs = new int[n];for (int i = 1; i < n; i++) {prefixBadPairs[i] = prefixBadPairs[i - 1];if ((nums[i] % 2) == (nums[i - 1] % 2)) {prefixBadPairs[i]++;}}for (int i = 0; i < m; i++) {int from = queries[i][0], to = queries[i][1];ret[i] = (prefixBadPairs[to] - prefixBadPairs[from] == 0);}return ret;}
}