给定正整数N、M，均介于1~10 ^ 9之间，N ＜= M，找出两者之间(含N、M)的位数为偶数的数有多少个

/*******************************************************
给定正整数N、M，均介于1~10 ^ 9之间，N <= M，找出两者之间(含N、M)的位数为偶数的数有多少个。

测试用例：

输入：N = 1, M = 100
输出：90
样例说明：[1, 100]区间上，有10~99元素的位数是2位，是偶数，这些整数的数量为90。

输入：N = 1, M = 1000
输出：91
********************************************************/

#include <iostream>
#include <cmath>
#include <vector>

#define _DEBUG 

class Solution
{
public:
    std::vector<std::pair<int, int> > m_vpDict;
    // 初始化一个字典
    void initDict(int bitNum)
    {
        for (int i = 0; i < bitNum; i++)
        {
            m_vpDict.push_back(std::pair<int, int>(pow(10, i), pow(10, i + 1) - 1));
        }
    }
    // 判断一个数是几位数
    int bitNum(int value)
    {
        if (value == 0)
        {
            return 0;
        }
        return 1 + bitNum( value / 10);
    }

    // 判断区间偶数个数
    int mostDouble(int start, int end)
    {
        int ret = 0;
        int startBits = bitNum(start);
        int endBits = bitNum(end);
        // 边界条件
        if (endBits - startBits == 0)
        {
            if (startBits % 2 != 0)
            {
                return 0;
            }
            else
            {
                return end - start + 1;
            }
        }

        if (startBits % 2 == 0)
        {
            ret += m_vpDict[startBits - 1].second - start + 1;
            startBits += 2;
            for (int i = startBits + 2; i < endBits; i += 2)
            {
                ret += 9 * pow(10, i);
            }
            if (endBits % 2 == 0)
            {
                ret += end - m_vpDict[endBits - 1].first + 1;
            }
        }
        else
        {
            startBits += 1;
            for (int i = startBits; i < endBits; i += 2)
            {
                ret += 9 * pow(10, i - 1);
            }
            if (endBits % 2 == 0)
            {
                ret += end - m_vpDict[endBits - 1].first + 1;
            }
        }

        return ret;
    }
};

int main()
{
    Solution solution;
    // 字典初始化
    solution.initDict(9);
#ifdef DEBUG
    // 测试字典初始化
    for (auto iter : solution.m_vpDict)
    {
        std::cout << iter.first << "    " << iter.second << std::endl;
    }

    // 测试bitNum函数
    std::cout << solution.bitNum(1254785) << std::endl;
#endif // DEBUG

    
    std::cout << solution.mostDouble(50, 80) << std::endl;
    
    return 0;
}