给出一个正整数数组A,牛牛想知道其中有多少子数组满足:里面所有数字的乘积等于里面所有数字的异或。 一个数组的子数组指数组中非空的一段连续数字。请用go语言写出时间复杂度小于O(n^2)的答案
时间: 2023-05-29 10:07:04 浏览: 72
思路:
- 对于一个子数组,如果它满足乘积等于异或,那么这个子数组里面最多只有一个偶数。
- 遍历数组,用一个变量even表示当前子数组中偶数的个数,用一个变量xor表示当前子数组中所有数字的异或和,用一个变量product表示当前子数组中所有数字的积。
- 如果当前数字是偶数,那么even++,如果even大于1,则不满足条件,直接跳过。如果当前数字是奇数,那么如果even等于0,则不满足条件,直接跳过;否则继续判断。
- 如果当前数字是奇数且even等于1,则判断当前子数组的乘积是否等于异或和,如果相等,则满足条件,统计答案。
- 遍历完数组后,得到满足条件的子数组个数。
代码实现:
```go
func solve(A []int) int {
ans := 0
even, xor, product := 0, 0, 1
for i := 0; i < len(A); i++ {
if A[i]%2 == 0 {
even++
if even > 1 {
even, xor, product = 0, 0, 1
continue
}
} else {
if even == 0 {
even, xor, product = 0, 0, 1
continue
}
}
xor ^= A[i]
product *= A[i]
for even == 1 && product != xor {
product /= A[i-even]
xor ^= A[i-even]
even--
}
if even == 1 && product == xor {
ans++
}
}
return ans
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)