题目分析

我做这种题目，主要是按照位数变化找规律，先看一看0~~9有多少个2，0~~99有多少个2，0~999有多少个2。

数学

知道原理后，使用迭代实现即可。算法的**时间复杂度为$O(log(n))$，空间复杂度为$O(log(n))$**。

我们也可以节省空间复杂度，因为n位数2的个数是$n * 10^{n - 1}$，在这里为了方便说明和使用，就使用了数组进行保存。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int numberOf2sInRange(int n) {
        vector<int> cnt = { 0 };
        int length = 0, ten = 1, tmp = n, res = 0;
        while (tmp >= 10) {
            tmp /= 10;
            cnt.push_back(++length * ten);
            ten *= 10;
        }
        for (int i = length; i >= 0; i--) {
            int high = n / ten;
            n = n % ten;
            if (high == 1) res += cnt[i];
            else if (high == 2) res += cnt[i] * 2 + n + 1;
            else if (high != 0) res += high * cnt[i] + ten;
            ten /= 10;
        }
        return res;
    }
};

刷题总结

对于数学问题，我们要学习小学生的做法，这类问题往往数字很大，不能使用线性，甚至更高复杂度的代码，老老实实找规律即可。