Leetcode#1523-在区间范围内统计奇数数目

题目描述

给你两个非负整数 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]内的奇数数目有两种情况，记区间内总数目为n。当n为偶数时，显然奇数数目为n/2，当n为奇数时，那么去除low后的区间中的奇数数目为(n-1)/2,然后只需加上判断low是否是奇数即为奇数数目的结果。
• 前缀和思想
  记pre(x)为区间[0,x]内的奇数数目，那么pre(x)=⌊(x+1)/2⌋（见思路1），那么区间[low,high]内的奇数数目即为pre(high)-pre(low-1)。

源码

class Solution {
public:
    int pre(int x)
    {
        return (x+1)>>1;
    }
    int countOdds(int low, int high) {
        /*
        int ans=high-low+1;
        if(ans%2==0)
        {
            ans/=2;
        }
        else
        {
            ans=ans/2+(low%2);
        }
        return ans;
        */
        return pre(high)-pre(low-1);
    }
};

题目来源

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。