狗家VO 挂筋

面了下狗家，挂了，三轮coding，面筋题我就不说了，地里都有
有一轮遇到了一个没有见过的题目，想了半天还不知道怎么做，大家可以讨论一下。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我除了想出了暴力，枚举每个数字的奇偶，想不起其他的办法，而且这种range如何保存，用什么数据结构呢？

不知道楼上的都在说啥 把每个前缀和看成一个节点 然后做并查集就好啦

楼上说的对 , prefix sum 感觉可以做

Rieman 发表于 2021-3-3 10:01
可以請層主再多說明一下如何使用並查集嗎? 感謝

这个题其实不告诉你每个数或者prefix_sum[i]的奇偶
而每一条 i, j, 奇/偶，
其实告诉你的是prefix_sum[i]之间的相对关系
比如sum(a[i]..a[j]) = 奇数,
其实告诉你的是 prefix_sum[j] - prefix_sum[i-1] = 奇数, which means prefix_sum[j] 和prefix_sum[i-1]不是同奇偶的
所以根据这个就可以每次把prefix_sum[j], prefix_sum[i-1]对应的node放到相同/不同的set里去了(或者产生矛盾)

分不够看不了隐藏内容，但是如果是求range sum可以用prefix sum或者segment tree/binary indexed tree?

if 2-8 odd  then 9-10 odd
if 2-8 even then 9-10 even
if 9-10 even then 11 odd
if 9-10 odd then 11 even

2-8 odd, 9-10 odd, 11 even => 2-11 is even
or
2-8 even, 9-10 even, 11 odd => 2-11 is odd

所以2-11奇数 偶数都可能啊。

xtt2016 发表于 2021-2-24 10:54
楼上说的对 , prefix sum 感觉可以做

这题不知道N个数字是什么 没法prefix sum吧 而且题目描述有问题 2-11为什么返回false。

如果9 是 1，10 是2， 11 是2， 2是1， 其他数字都是0。这个是符合这三个条件的，楼主你这描述有点迷糊啊。

memo[j] 存 i+ (i+1) +...j 的奇偶

如果来了个（a ，b， 奇偶性）对于所有k，memo[a][k],
if k == b return
if k > b, recursive call (b, k)
if k <b, recursive call(k, b)
（回退的时候记得更新memo）
这样一直循环下去应该是可以的 空间O（N^2） 时间最坏N^2 * M M是query个数(这个不是很确定）

解方程，高斯消除法解同余方程，最多O(N^3)x9 - x1 = 0
x11 - x9 = 1
x11 - x1 = 0

prefix 奇偶 instead of sum， 可以更简单；
遇到偶数，prefix sum的奇偶性不变，遇到基数，prefix sum的奇偶行就改变。
0 = 1, isEven, false; accumulative/prefix sum isEven, false;
1  = 2, true; false * true = false;
2 = 3, false; false * false = true;
3 = 4, true; true * true = true;

range 1 - 3,  accumulative isEven at 3 -  accumulative isEven at 0 = true - false = false;
return isEven = false, 是奇数