题目链接
分析
代码实现
复杂度分析

2588 统计美丽子数组数目

· 2025-3-6 · 1 次阅读 · 字数统计: 208字 · 阅读时长≈ 1分钟

· 算法题解 · LeetCode

题目链接

2588. 统计美丽子数组数目

分析

对于美丽子数组来说，统计其中所有数在二进制下 $1$ 的位置，每一个位置的数量均为偶数

故原问题等价于判断数组异或和是否为 $0$

又异或操作满足结合律，且任何数于其自身做异或操作为 $0$

所以我们使用前缀和来计算子数组的异或和，使用哈希表记录前缀数组异或和出现的次数

遍历计算即可

代码实现

 class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        long long ans = 0;
        int t = 0;
        unordered_map<int, int> um;
        um[0] = 1;
        for(int x : nums) {
            t ^= x;
            ans += um[t]++;
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$
空间复杂度： $O (n)$

1328 破坏回文串

Nickname

Website

0/500

0 comments

文章

2874 有序三元组中的最大值

题目链接2873. 有序三元组中的最大值 I 2874. 有序三元组中的最大值 II 分析要想使得三元组的计算值最大，那么就要使 $n u m s [i]$ 和 $n u m s [k]$ 的值最大维护前缀最大值和后缀最大值，枚举 $j$ 即可算出最大值代码实现class Solution { pub

2140 解决智力问题

题目链接2140. 解决智力问题分析定义 $d p [i]$ 为解决前 $i$ 道题目可以获得的最大分数，我们发现由于每道题的 $b r a i n p o w e r$ 不固定，我们求解 $d p [i]$ 时要遍历 $j \in [0, i - 1]$ 的所有 $d p [j]$ ，那么时间复杂度将会是 $O (n^{2})$ 考

2278 字母在字符串中的百分比

题目链接2278. 字母在字符串中的百分比分析遍历后计算即可，也可以使用STL实现代码实现class Solution { public: int percentageLetter(string s, char letter) { int cnt = ranges::coun

2109 向字符串添加空格

题目链接2109. 向字符串添加空格分析双指针遍历字符串，每次 $i$ 走到 $s p a c e s [i d x]$ 的值就加入一个空格，再将 $i d x$ 的值 $+ 1$ 代码实现class Solution { public: string addSpaces(string s, vector&l

2360 图中的最长环

题目链接2360. 图中的最长环分析遍历每一个节点，并且记录下遍历到的时间由于每一个节点只有一个出边，那么从任意节点开始遍历，都会出现以下三种情况中的一种： (1) 走到一个没有出边的节点 (2) 走到一个遍历过的节点，但该节点在之前的遍历中就已经访问过 (3) 走到一个遍历过的节点，该节点在这

2716 最小化字符串长度

题目链接2716. 最小化字符串长度分析根据题意，只要有相同的字符就可以删除，计算 $s$ 中不同字符的个数即可使用集合去重运算即可，实际实现中可使用位运算优化代码实现class Solution { public: int minimizedStringLength(string

2712 使所有字符相等的最小成本

题目链接2712. 使所有字符相等的最小成本分析对于每两个相邻的不同值，均要进行操作使其相等遍历遇到相邻的值不同时，选择 $i$ 和 $n - i$ 中比较小的即可代码实现class Solution { public: long long minimumCost(string s) &

2829 k-avoiding 数组的最小总和

题目链接2829. k-avoiding 数组的最小总和分析考虑比 $k$ 小的数如果将 $1$ 加入数组内，我们就不能选择 $k - 1$ ；如果将 $2$ 加入数组内，我们就不能选择 $k - 2 \dots$ 以此类推，对于比 $k$ 小的数，我们取其中较小的一半 $1$ 到 $\lflo

2255 统计是给定字符串前缀的字符串数目

题目链接2255. 统计是给定字符串前缀的字符串数目分析遍历 $w o r d s$ 中的每一个字符串毕竟即可代码实现class Solution { public: int countPrefixes(vector<string>& words, string s) &#

2116 判断一个括号字符串是否有效

题目链接2116. 判断一个括号字符串是否有效分析记左括号为 $1$ 分，右括号为 $- 1$ 分，括号字符串有效的条件等价于：该字符串的分数为 $0$ ，且该字符串任意前缀的分数均大于等于 $0$ 由于字符串中存在可以更改的字符，我们创建两个变量 $m i n_{c} n t$ 和 $m a x_{c} n t$ ，分别记录

2643 一最多的行

题目链接2643. 一最多的行分析枚举每一行，统计 $1$ 的个数，当前行的 $1$ 数量大于之前的最大数量时，更新答案代码实现class Solution { public: vector<int> rowAndMaximumOnes(vector<vector&l

2610 转换二维数组

题目链接2610. 转换二维数组分析使用一个哈希表记录每个数字出现的次数，然后放到对应行的数组里即可由于题目保证数据在 $1 - n$ ，所以可以使用数组存储加速运算代码实现class Solution { public: vector<vector<int>> f

2614 对角线上的质数

题目链接2614. 对角线上的质数分析遍历判断即可，由于数据范围较小，直接判断快过质数筛代码实现class Solution { public: int diagonalPrime(vector<vector<int>>& nums) { in

1963 使字符串平衡的最小交换次数

题目链接1963. 使字符串平衡的最小交换次数分析可以容易想到一个贪心的思路，每次将最前面的]和最后的[交换但是对于形如 ]*]*[*[ 的括号段来说，我们可以通过交换最前面的]和最后的[的，一次交换解决两个统计原串中非平衡字串中左括号出现的次数即可，除 $2$ 后即为答案，对于奇数情况，多进

2012 数组美丽值求和

题目链接2012. 数组美丽值求和分析分别求出数组的前缀最大值和后缀最小值，遍历进行比较即可代码实现class Solution { public: int sumOfBeauties(vector<int>& nums) { int n = nums.s

2269 找到一个数字的 K 美丽值

题目链接2269. 找到一个数字的 K 美丽值分析遍历每一个长度为 $k$ 的子字符串计算即可可以使用 $10^{k}$ 来作为模数取出长度为 $k$ 的子字符串代码实现class Solution { public: int divisorSubstrings(int num, int

2588 统计美丽子数组数目

题目链接2588. 统计美丽子数组数目分析对于美丽子数组来说，统计其中所有数在二进制下 $1$ 的位置，每一个位置的数量均为偶数故原问题等价于判断数组异或和是否为 $0$ 又异或操作满足结合律，且任何数于其自身做异或操作为 $0$ 所以我们使用前缀和来计算子数组的异或和，使用哈希表记录前缀数组异

1328 破坏回文串

题目链接1328. 破坏回文串分析对于长度为 $1$ 的串来说，必定为回文串，直接返回空串即可对于其余回文串来说，找到第一个不等于 $a$ 的字母修改为 $a$ 时字典序最小如果回文串除中心外出现全是 $a$ 的情况，将最后一位修改为 $b$ 时字典序最小代码实现class Solution

132 分割回文串

题目链接131. 分割回文串 132. 分割回文串 II 分析定义 $d p [i]$ 为前缀 $s [0]$ 到 $s [i]$ 的最小分割次数状态转移方程为 $Misplaced &$ 预先计算 $isPa

2506 统计相似字符串对的数目

题目链接2506. 统计相似字符串对的数目分析对于每一个字符串，使用一个数组来存储字符串中出现的字母，这个数组可以压缩成一个二进制数 $m a s k$ 使用一个哈希表统计每个 $m a s k$ 出现的次数，遍历求和即可代码实现class Solution { public: int simil

分类

算法题解notes-of-problems

机器学习machine-learning

算法algorithm

游戏引擎game-engine

程序语言programming-language

标签

LeetCodeLeetCode

计算机视觉computer-vision

视角合成view-synthesis

洛谷Luogu

字符串string

	class Solution {
	public:
	long long beautifulSubarrays(vector<int>& nums) {
	long long ans = 0;
	int t = 0;
	unordered_map<int, int> um;
	um[0] = 1;
	for(int x : nums) {
	t ^= x;
	ans += um[t]++;
	}
	return ans;
	}
	};