计算连续范围内奇/偶数个数

发表于 更新于 阅读次数： 本文字数： 602 阅读时长 ≈ 2 分钟

简介

这篇就讨论一个问题，“计算连续范围内奇/偶数个数”，很简单，就是给定一个范围[a,b]，计算出这个范围内的奇数、偶数个数

如：[1,18]

这个范围奇数9个，偶数9个，问题很简单

说明

其实这个我毕设的一个计算需要，其实是根据周次和单双周计算有多少周，下面列个表

单双周 单周 双周
1-18 18 9 9
1-17 17 9 8
2-18 17 8 9
2-17 16 8 8

上面的例子包含了所有情况，即对于范围[a,b]

分别代表了

  • 奇数-偶数
  • 奇数-奇数
  • 偶数-偶数
  • 偶数-奇数

先说最容易的，单双周计算最简便b-a+1

单周或是双周计算方式最随着a,b的不同而不同

当然有人会说了，这一个遍历不就完事了，但是我绝不可能那么做的，这很明显是有数学关系的，之前刷题也见过不少是数学关系的，可以直接找到其中关系，计算出来的

再次分析上面的表格

单双周（y=b-a+1） 单周 双周
1-18 18 9（y/2） 9（y/2）
1-17 17 9（y/2+1） 8（y/2）
2-18 17 8（y/2） 9（y/2+1）
2-17 16 8（y/2） 8（y/2）

看出了吗？

其中肯定有数学关系的，这里把a、b用奇1，偶0来表示

单双周（y=b-a+1） 单周 双周
1-18（1-0） 18 9（y/2） 9（y/2）
1-17（1-1） 17 9（y/2+1） 8（y/2）
2-18（0-0） 17 8（y/2） 9（y/2+1）
2-17（0-1） 16 8（y/2） 8（y/2）

这样就很明显了

  • 单周，1-1情况下+1
  • 双周，0-0情况下+1

转换一下就是

  • 单周，a、b与运算为1，可以+1
  • 双周，a、b或运算为0，可以+1

这里单双周0，单周1，双周2，那么伪代码就如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int compute(int a, int b, int singleOrDouble){
    if(singleOrDouble==0){
        return b - a + 1;
    }else if(singleOrDouble == 1){
        if(((a & b) & 1) == 1){
            b++;
        }
        return (b - a + 1) / 2;
    }else if(singleOrDouble == 2){
        if(((a | b) & 1) == 0){
            b++;
        }
        return (b - a + 1) / 2;
    }
}

这其中利用了位运算，非常有趣

当然还有很多地方可以可以用这种解决方法，LeetCode上也有很多类似的

总结

很多时候探索的过程是最珍贵的