招银科技笔试题：求数字N中有多少个M

输入m∈[1,9]，输入任意正整数n，求n里出现了多少次数字m

第一种是线性实现，轮询每个数字，到百万量级时就不行了

//
//    
//
//    
int count_nums(int m, int n)
{
    int count = 0;
    char n_str = m + '0';
    //  n里多少个数字有m
    for(int i=1; i<n; ++i){
        for(const char &ch : to_string(i))
            if(ch == n_str){
                count += 1;
                break;
            }
    }

    return count;
}

第二种是先构造一个每位有多少相同数字的表，然后查表实现，由牛客网@言1997 同学提供
帖子地址：https://www.nowcoder.com/discuss/630291?source_id=profile_create_nctrack&channel=-1

//
//    输入m∈[1,9]，输入任意正整数n，求n里出现了多少次数字m
//
//    第一种是线性实现，鄙视
int count_nums2(int m, int n)
{
    int n1 = n / 10, k = 10, idx;
    vector<int> count = { 0,1 }, nums = { n % 10 };
    while (n1 > 0) {
        count.push_back(count.back() * 9 + k);
        nums.push_back(n1 % 10);
        k *= 10;
        n1 /= 10;
    }
//    for(int i:count) cout<<i<<' ';
//    cout<<endl;
//    for(int i:nums) cout<<i<<' ';
//    cout<<endl;
    int ans = 0;
    for (int i = nums.size() - 1; i > -1; --i) {
        k /= 10;
        //cout<<k<<endl;
        if (nums[i] <= m) {
            ans += count[i] * nums[i];
            if (nums[i] == m) {
                ans += n % k;
                break;
            }
        }
        else {
            ans += count[i] * (nums[i] - 1) + k;
        }
    }
    return ans;
}

第三种是我自己实现的查表法，毕竟懂原理是一方面，会敲出来是另一方面

vector<int> create_table(int number, bool print=false)
{
    // 构造表
    vector<int> unit_count = {0, 1};
    for(int unit=100; unit < number; unit*=10) {
        int count = 9 * unit_count[unit_count.size()-1] + unit / 10;
        unit_count.push_back(count);
    }

    // 输出构造后的表结构
    cout << "{ ";
    if(print)
        for(const int& val : unit_count)
            cout << val << ' ';
    cout << " }" << endl;

    //
    return unit_count;
}


int count_nums3(int m, int n, const vector<int>& table = vector<int>())
{
    int ret = 0;
    vector<int> tb = table.empty() ? create_table(n) : table;

    //  将目标拆分为两部分
    int tail = 0;
    auto str = to_string(n);
    auto idx = str.find(m+'0');
    if(idx != string::npos && idx != str.size()-1) {
        n = stoi(str.substr(0, idx+1));
        auto tmp = str.substr(idx+1, str.size()-idx);
        tail = stoi(tmp);
        n *= pow(10, tmp.size());
        str = to_string(n);
    }

    //
    int unit = 1;
    for(int i=0, len=str.size();
        i < len;
        ++i, unit*=10)
    {
        int bit = str[len - i - 1] - '0';   //  获取该十进制bit上的元素
        auto tmp = (bit - (bit > m)) * tb[i] + (bit > m) * unit;
        ret += tmp;
    }

    //
    cout << ret << "   " << tail << "  " << n << endl;
    ret += tail;
    return ret;
}

这里是测试用的主函数

int main() {
    //  输入m∈[1,9]，输入任意正整数n，求n里出现了多少次数字m
    int m, n;
    m = 2;
    n = 316541656;

    //
    auto table = create_table(n, true);
    auto res = count_nums3(m, n, table);
    cout << "count_nums3:\t" <<  res << endl;
    cout << "count_nums2:\t" <<  count_nums2(m, n) << endl;
    cout << "count_nums:\t" <<   count_nums(m, n) << endl;
}