1. 问题描述:
给你两个非负整数 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^92. 思路分析:
一看到题目比较容易想到的是使用for循环枚举每一个数字判断当前的数字是否是奇数,如果是奇数那么对其计数即可,但是仔细一分析发现还有其他的办法,对于一个区间上的奇数与偶数分布基本上是均匀的,也就是大部分情况下是一半一半分布的,所以我们是可以根据区间的起点与终点计算对应的奇数与偶数的数目,主要分为四种情况:
对于这种比较容易分析的题目我一般是写出具体的例子,这样更容易确定边界上的一些问题,而且小的数据更容易计算正确的答案,比如写出一个区间为[1-10]
1 2 3 4 5 6 7 8 9 10
计算[3, 9]的奇数数目: (9 - 3) / 2 + 1 = 3
计算[3, 10]的奇数数目:(10 - 3) / 2 + 1 = 3
计算[2,10]的奇数数目:(10 - 2)/ 2 = 4
计算[2, 9]的奇数数目:(9 - 2)/ 2 + 1 = 4
所以总结上面的请主要是分为三种区间起点是奇数的情况,区间端点是偶数-偶数,偶数-奇数的情况返回即可,可以利用与操作来判断奇数还是偶数
3. 代码如下:
class Solution: def countOdds(self, low: int, high: int) -> int: if low & 1 == 1: return (high - low) // 2 + 1 else: if high & 1 == 0: return (high - low) // 2 else: return (high - low) // 2 + 1