java算法题-在区间范围内统计奇数数目

在leetcode（https://leetcode-cn.com/）上看到一道有趣的算法题：

给你两个非负整数 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

这样的题你会怎么用java实现呢？

判断一个数x是否为奇数很容易，比如x%2>0时，则x为奇数，基于这个分享一下我的解题思路：

• 普通

在给定的范围low到high之间从low往右遍历和从high往左遍历

public int countOdds(int low, int high) {
    if (low == high) {
        return low % 2 > 0 ? 1 : 0;
    }
    int sum = 0;
    for (; low <= high if low='= high)' if low 2> 0) {
                sum += 1;
            }
        } else {
            if (low % 2 > 0) {
                sum += 1;
            }
            if (high % 2 > 0) {
                sum += 1;
            }
        }
        low++;
        high--;
    }
    return sum;
}

• 进阶

上边的方法其实还不够优雅，毕竟需要一个一个数去遍历，虽然是从两个方向同时进行判断，但当给定数的值很大的时候，就比较耗时了，比如在low=327296043,high=769434803时，程序执行的耗时高达1152ms（以leetcode平台执行该函数所需的时间为参考），对于一个好的算法来说这是严重不合格的。那么我们换种思路，其实个位数分别为1，2，3，4，...8，9等10个数之间，奇数的个数是固定的，为5个，比如1，2，3，4，...8，9这几个数之间有5个奇数，对应的比如31,32,33,34，...，38，39,这几个数之间也有5个奇数，所以我们只需要将给定的两个数low和high处理一下变为两个个位数都为0的数，然后计算下这两个数之间包含多少个“长度为10，个位数从1到9的数”，然后乘以5，再加上两个数处理前的一些奇数就可以得到我们想要的结果了，代码如下：

public int countOdds(int low, int high) {
        if (low == high) {
            return low % 2 > 0 ? 1 : 0;
        }
        Long sum = 0L;
        int startLowUnitsDigit = low % 10;
        int startHighUnitsDigit = high % 10;
        long newLow = low;
        long newHigh = high;
        if (startLowUnitsDigit > 0) {
            newLow = low + (10 - startLowUnitsDigit);
        }
        if (startHighUnitsDigit > 0) {
            newHigh = high - startHighUnitsDigit;
        }
        if ((newHigh - newLow) % 10 == 0) {
            sum=(newHigh - newLow)*5/10;
            for (; low <= newlow if low='= newLow)' if low 2> 0) {
                        sum +=1;
                    }
                } else {
                    if (low % 2 > 0) {
                        sum +=1;
                    }
                    if (newLow % 2 > 0) {
                        sum +=1;
                    }
                }
                low++;
                newLow--;
            }
            for (; newHigh <= high if high='= newHigh)' if newhigh 2> 0) {
                        sum +=1;
                    }
                } else {
                    if (newHigh % 2 > 0) {
                        sum +=1;
                    }
                    if (high % 2 > 0) {
                        sum +=1;
                    }
                }
                newHigh++;
                high--;
            }
        } else {
            for (; low <= high if low='= high)' if low 2> 0) {
                        sum +=1;
                    }
                } else {
                    if (low % 2 > 0) {
                        sum +=1;
                    }
                    if (high % 2 > 0) {
                        sum +=1;
                    }
                }
                low++;
                high--;
            }
        }
        return sum.intValue();
    }

给定同样的值，low=327296043,high=769434803，好家伙，这里的执行时间一下子从1152ms降为0ms（以leetcode平台执行该函数所需的时间为参考），程序性能大大提升。

以long存储sum是因为计算的结果可能超过int值的最大范围

程序执行结果：

输入：low=327296043，high=769434803
输出：221069381

leetcode上对该答案的分析如下：

84 / 84 个通过测试用例

状态：通过

执行用时: 0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗: 35.4 MB, 在所有 Java 提交中击败了14.80%的用户

执行用时分布图表

执行消耗内存分布图表

大家有更好的解题思路吗？欢迎在评论区作答哈~