C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-05-12

class Solution {
public:
    /*
    int find_num1(int n){
        int count = 0;
        while(n){
            if(n%10 == 1){
                count++;
            }
            n /= 10;
        }
        return count;
    }
    
    
    //1-n中 1 出现的次数
    int NumberOf1Between1AndN_Solution(int n) {
        int cnt = 0;
        for(int i = 1;i <= n;i++){
            cnt += find_num1(i);
        }
        return cnt;
    }
    */
    int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0) return 0;
        vector<int> v;
        int ret = 0;
        while(n){
            v.push_back(n%10);
            n /= 10;
        }
        for(int i = v.size()-1;i >= 0;--i){
            auto left = 0,right = 0,t = 1;
            
            for(int j = v.size() - 1;j > i;--j){
                left = left * 10 + v[j];
            }
            for(int j = i-1;j >= 0;--j){
                right = right * 10 + v[j];
                t *= 10;
            }
            ret = ret + left*t;
            if(v[i] == 1){
                ret += (right+1);
            }else if (v[i] > 1)
                ret += t;
        }
        return ret;
    }
    
};

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-05-09

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) 
	{
		int res = 0, temp_val, temp_mod, multi = 10;
		do
		{
			temp_val = floor(n / multi);
			temp_mod = n % multi;
			res += temp_val * multi / 10;
			if(temp_mod * 10 >= multi)
				res += min(multi / 10, temp_mod - multi / 10 + 1);
			multi *= 10;
		} while (n * 10 >= multi);

		return res;
	}
};

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-04-18

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int num = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (i%10 == 1)
            {
                ++num;
            }
            int a = i / 10;
            for (; a > 0; a = a/10)
            {
                if (a%10 == 1)
                {
                    ++num;
                }
            }
            
        }
        
        return num;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-03-28

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if(n < 1) return 0;
        
        string str = to_string(n);
        int idx = str.length()-1;
        if( !idx ) return 1;
        
        int cnt(0), pre, rear(0), num, scale(1);
        while(idx >= 0)
        {
            num = str[idx]-48;
            pre = (idx > 0) ? stoi( str.substr(0, idx) ) : 0;
            
            if(num > 1){
                cnt += (pre+1)*scale;
                rear += num*scale;
                scale *= 10;   idx--;
                continue;
            }
            if(num == 1){
                cnt += pre*scale+rear+1;
                rear += scale;
                scale *= 10;   idx--;
                continue;
            }
            cnt += pre*scale;
            scale *= 10;   idx--;
        }
        return cnt;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-03-27

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int cnt = 0;
        for (int i = 1; i <= n; i *= 10)
        {
            int a = n / i, b = n % i;
            cnt += ( a + 8) / 10 * i + (a % 10 == 1 ? b + 1 : 0);
        }
        return cnt;
    }
};