【力扣算法题】统计奇数数目

【力扣算法题】统计奇数数目

---

文章目录

• 【力扣算法题】统计奇数数目
• 题目介绍
• 题解
• • 1. 分情况（个人解法）
  • 2. 大减小（力扣官方解法）

---

题目介绍

给定一个非负整数区间，求该区间内（包括最小最大值）奇数的数量

---

题解 1. 分情况（个人解法）

对于一个非负整数区间[low, high]，我们有

• low奇，high奇：中间奇数数量为 floor((high - low) / 2) + 1
• low奇，high偶：中间奇数数量为 floor((high - low) / 2) + 1
• low偶，high奇：中间奇数数量为 floor((high - low) / 2) + 1
• low偶，high偶：中间奇数数量为 floor((high - low) / 2)

可见，前3种情况的计算方法相同，于是我们可以仅仅分出两种情况来编写代码

下面为C++源码：

int countOdds(int low, int high) {
    // low是否为奇数
    bool loOdd = (low % 2) != 0;
    // high是否为奇数
    bool hiOdd = (high % 2) != 0;

	// 情况1：low和high都是偶数
    if(!(loOdd || hiOdd))
    {
        return (high - low) / 2;
    }
    else //情况2： 其余3种情况
    {
        return 1 + (high - low) / 2;
    }
}

2. 大减小（力扣官方解法）

对于区间[0, n]，且n大于0，我们可以直接列出求奇数数量的公式：pre(n) = floor(1 + n / 2)
那么对于一个非负整数区间[low, high]，可以根据上面的公式计算出[0, low]和[0, high]之间的奇数数量

这时候，乍一看结果已经出来了，就是：pre(high) - pre(low)
但因为题目的要求，我们必须考虑到low和high都被包括在计算内，然而下面的问题就是容易疏忽的点

• 当low为奇数时，pre(high) - pre(low)的结果会比实际结果小

因此，我们使用pre(high) - pre(low - 1)作为最终的公式

• 当计算pre(low - 1)时，无论low为奇数还是偶数，都不会被包括在pre(low - 1)的奇数数量中

C++源码如下（该源码来自力扣官网）：

int pre(int x) {
	// 此处二进制的移位 *** 作符等于十进制的 / 2
    return (x + 1) >> 1;
}

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

//作者：LeetCode - Solution
//链接：https ://leetcode-cn.com/problems/count-odd-numbers-in-an-interval-range/solution/zai-qu-jian-fan-wei-nei-tong-ji-qi-shu-shu-mu-by-l/

（看完官方代码我感觉我写的全是废品 =_=）