每日一题day8-在区间范围内统计奇数数目

题目：

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。
示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

提示：

0 <= low <= high <= 10^9

思路：

如果我们暴力枚举 [low, high]中的所有元素会超出时间限制。
我们可以使用前缀和思想来解决这个问题，定义pre(x) 为区间 [0, x]中奇数的个数，很显然：
pre(x)=(x+1)/2;

故答案为 pre(high) - pre(low−1)。

java代码：

class Solution {
    public int countOdds(int low, int high) {
        return pre(high) - pre(low - 1);
    }

    public int pre(int x) {
        return (x + 1) >> 1; //相当于(x+1)/2, 但效率更高
    }
}