leetcode 233. Number of Digit One 从1到n的数组中出现数字1的数量 + 寻找规律，公式计算

逃离我推掉我的手 2022-06-08 12:15 131阅读 0赞

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:  
Given n = 13,  
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

这道题是查1的数量，网上看了个做法，但是没搞懂，后来我突发奇想到使用字符串来做，但是超时，但是先这么办吧。

代码如下：

/*
     * http://www.cnblogs.com/grandyang/p/4629032.html
     * 
     * 搞不懂
     * */
    public class Solution
    {
        public int countDigitOne(int n) 
        {
            int res = 0, a = 1, b = 1;
            while (n > 0) 
            {
                if((n % 10 == 1))
                     res += (n + 8) / 10 * a + b;
                else 
                     res += (n + 8) / 10 * a;
    
                b += n % 10 * a;
                a *= 10;
                n /= 10;
            }
            return res;
        }
    
        /*
         * 我通过字符串来做，但是超时
         * */
        public int countDigitOneByStr(int n)
        {
            int count=0;
            StringBuilder builder=new StringBuilder();
            for(int i=1;i<=n;i++)
                builder.append(i+"");
    
            for(int i=0;i<builder.length();i++)
            {
                if(builder.charAt(i)=='1')
                    count++;
            }
            return count;
        }
    }

下面是C++的做法，看了很久才明白这一道题的意思，我最直接的做法就是使用字符串做判断，但是肯定会超时，所以我参考了网上的一个做法，就是找规律做的

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <string>
    #include <map>
    
    using namespace std;
    
    class Solution
    {
    public:
        int countDigitOne(int n) 
        {
            int res = 0, a = 1, b = 1;
            while (n > 0)
            {
                if ((n % 10 == 1))
                    res += (n + 8) / 10 * a + b;
                else
                    res += (n + 8) / 10 * a;
    
                b += n % 10 * a;
                a *= 10;
                n /= 10;
            }
            return res;
        }
    };