range的奇偶性判断 算法题求解

最近看到狗家面经里有一题， 看了不少讨论好像也没个很理想的解法。 发出来看看地里的大牛有什么想法。。。
假设有个数组，要实现一个函数， 每次输入的input (int startIndex, int endindex, RangeSumEvenOrOdd)，基于之前的输入，判断当前输入是否valid。

e.g.
1st input (0, 10, Even) -> valid;   (目前没有从0到10的信息， 所以默认valid)
2nd input (11, 15, Even) -> valid; （同上）
3rd input (0, 15, Odd) -> False, 根据前两个输入，0-15必须是even

输入范围没有限制。你可以认为这个数组是随意长度。 需要考虑 overlap。 比如
4st input (3, 7, odd),  这个时候（0，2）和（8， 10） 应该是一个even一个odd才能满足之前的输入。

有什么好办法吗？

magicsets 发表于 2021-3-22 14:24
这个问题可以有个通用解法，不需要输入是range（比如可以 input ([0, 3, 5], Even) -> valid，也就是0/3/5 ...

这个的确应该是通用方法。 不过面试时候按这个思路写代码感觉很困难。。。

这个问题可以有个通用解法，不需要输入是range（比如可以 input ([0, 3, 5], Even) -> valid，也就是0/3/5号位置的元素加起来是偶数），不过利用range这一性质可能可以有进一步优化

方法很简单就是列方程：
--
1st input (0, 10, Even) => x0 + ... + x10 = 2 * s1
2nd input (11, 15, Even) => x11 + ... + x15 = 2 * s2
3rd input (0, 15, Odd) => x0 + ... + x15 = 2 * s3 + 1
...

这里所有的x和s要求取任意整数值，那么所联立的不定方程组是一个经典问题，称为线性丢潘图方程组（system of linear Diophantine equations)。

我们知道总体上来说丢潘图方程是不可计算的（希尔伯特第十问题）。不过线性丢潘图方程组不仅可以判定是不是有解，还可以求通解，方法类似高斯消元法解线性方程组，可以参考这里：
https://www.math.uwaterloo.ca/~w ... /GilbertPathria.pdf

至于进一步优化，注意到所有x项的系数都是1，而且range型输入会造成方程组的系数矩阵上每一行上的1都是连续的，那么很可能会有巧妙的优化手段.. 这个楼主可以自己研究一下


补充内容 (2021-03-24 10:11 +8:00):
丢潘图 -> 丢番图

Prefix sum + Union Find

[0, 10, even] => none(没有数) union 10，0到10的和一定和none奇偶性相同，而none的prefix sum 为0
[11, 15, even] => 10 union 15，-10 union -15（负数为了发现odd是否矛盾）
[0, 15, odd] => wrong, none 和15已经在一个group

[3, 7, odd] => 2 union -7，-2 union 7，用负数来表示奇偶性相反
[8, 10, even] => 7 union 10, -7 union -10
[0, 2, even] => wrong, 因为 {none, 10, 7, -2} 为一个group，与这里的 none union 2 产生矛盾。

FightForLife 发表于 2021-3-22 13:55
Prefix sum + Union Find

[0, 10, even] => none(没有数) union 10，0到10的和一定和none奇偶性相同，而no ...

感觉这个方法应该可以。 基本思路就是union find， 因为node没有范围所以用map而不是array来存储父子关系。
对于输入int startIndex, int endindex， 同符号相连表示even， 异符号相连表示odd。 但是对于startIndex=0要特殊处理下， 我觉得如果startIndex=0， 可以将它map到Integer.MAX_VALUE 和Integer.MIN_VALUE。

面试时能想到Union Find的思路不容易

并查集的思路没毛病，但是楼上的解法有点小问题。如果input range是[0,10,even]，需要union(null, 10)和(-null, -10)。-null虽然没有意义，但是-10有意义，否则遇到[0,5,odd]会出问题。另外[1,10, even]，需要要同时union(+0, +10)和union(-0, -10)。正负0太奇怪了，不如定义x为代表[0, x), 这样正负0就代表正负null, [1,10,even]就需要union(1, 11)和union(-1,-11)，这样可能会清晰一些。

补充内容 (2021-03-24 11:47 +08:00):
+null就是“偶”, -null就是“奇”,一个意思。

bigboss789 发表于 2021-3-23 00:20
这个的确应该是通用方法。 不过面试时候按这个思路写代码感觉很困难。。。

额，思路的话这边建议这么来。
首先Prefix Sum的转化应该不难想到，a[ i]+ ... a[j] = s[j] - s[i-1].
然后，问题就变成s[j] - s[i-1]为奇数或者偶数
这件事进一步转化成s[j] - s[i-1]为奇数 <=> s[j]和s[i-1]一个为奇数 另一个为偶数
和s[j] - s[i-1]为偶数，那么两者同为奇数或偶数

把奇数和偶数转化为T/F (你也可以继续叫奇数偶数，反正是一个意思)，则这件事就是2-SAT，于是拆点，s 拆成 T/F

图中的边a-->b表示取了a就必须同时取走b，那么
s[j] - s[i-1]为奇数就代表T[i-1 ] <--> F[j]且F[i -1] <--> T[j]
s[j] - s[i-1]为偶数就代表T[i- 1] <--> T[j]且F[i -1] <--> F[j]

那么原问题就变成加入一个新的条件是否会使得任何一个T[i ]和F[i ]进入同一个联通分量（一个变量不能同时为真和假），于是就变成上面这种并查集的情况了。


具体边界需要考虑一下，大概应该没错。

对每个点维护一个 diff[x] 表示 x的奇偶性是否与p[x]相同。每一个query如果parent相同，可以从diff[x]和diff[y]和odd/even来判断是否出错

1. int find(x) //get the parent of x
   
2. {
   
3. if(x != p[x]) //need to update diff[x];
   
4. {
   
5.     int rt = find(p[x]);
   
6.     diff[x] ^= diff[p[x]];
   
7.     p[x] = rt;
   
8. }
   
9. return p[x];
   
10. }
    
11. 
    
12. 或者用拓展域做，x表示和x奇偶性相同的点，x+n表示和x奇偶性不同的点。
    
13. for (x, y, even):
    
14. if(find(x) == find(y + n)) error! break;
    
15. 
    
16. p[find(x)] = find(y); //x和y奇偶性一样，所以add x to y, also add x + n to y + n
    
17. p[find(x + n)] = find(y + n);
    
18. 
    
19. for (x, y, odd):
    
20. if(find(x) == find(y)) error! break;
    
21. p[find(x)] = find(y+n);
    
22. p[find(x + n)] = find(y);

复制代码

参考了下各位大佬的想法，我觉得可以把输入的页码转换成一个字母+页码变成node，然后用并查集的思路。大概代码如下：

1. 
   
2. 
   
3. boolean isValid(int start, int end, boolean isOdd)
   
4. {
   
5. start = start-1;
   
6. // 分别应对even 和odd的情况
   
7. String nodeAStart = "A" + start, nodeBStart = “B" + start;
   
8. Sting  nodeAEnd = "A" + end,  nodeBEnd = "B" + end;
   
9. 
   
10. if (isOdd)
    
11. {
    
12.   if （isConnect(nodeAStart, nodeAEnd) || isConnect(nodeBstart, nodeBend)）
    
13.         return false;
    
14.      connect(nodeAStart, nodeBend);
    
15.      connect(nodeBstart, nodeAEnd);
    
16. }
    
17. else
    
18. {
    
19.   if （isConnect(nodeAStart, nodeBEnd) || isConnect(nodeBstart, nodeAend)）
    
20.         return false;
    
21.   connect(nodeAStart, nodeAEnd);
    
22.   connect(nodeBstart, nodeBend);
    
23. }
    
24. return true;
    
25. }
    
26. 
    
27. 
    
28. 
    

复制代码