class Solution {
public:
    /*
    	我们从低位到高位求每位1出现的次数，累加求和即可
        例如：求0~abcde中1的个数，现在我们求c这一位中1出现的次数，其他位雷同
        有两部分组成
        第一部分：ab * 100，表示当ab这两位在0~ab-1范围内时，de可以从0~99取值
    	    第二部分：如果c>1时，当ab为ab时1的个数为0~99
                  如果c=1时，当ab为ab时1的个数为de + 1
                如果c<0时，当ab为ab是1的个数为0
    */
    int NumberOf1Between1AndN_Solution(int n)
    {
        int exp = 1;
        int ans = 0; 
        while(n / exp)
        {
        	ans += n / (exp * 10) * exp;
            if(n % (exp * 10) / exp  > 1) ans += exp;
            else if(n % (exp * 10) / exp == 1) ans += (n % exp + 1);
            exp *= 10;
        }
        return ans;
    }
};

python solution

def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int

        例：对于824883294，先求0－800000000之间（不包括800000000）的，再求0－24883294之间的。
        如果等于1，如1244444，先求0－1000000之间，再求1000000－1244444，那么只需要加上244444＋1，再求0－244444之间的1
        如果大于1，例：0－800000000之间1的个数为8个100000000的1的个数加上100000000，因为从1000000000－200000000共有1000000000个数且最高位都为1。
        对于最后一位数，如果大于1，直接加上1即可。
        """
        result = 0
        if n < 0:
            return 0
        length = len(str(n))
        listN = list(str(n))
        for i, v in enumerate(listN):
            a = length - i - 1  # a为10的幂
            if i==length-1 and int(v)>=1:
                result+=1
                break

            if int(v) > 1:
                result += int(10 ** a * a / 10) * int(v) + 10**a
            if int(v) == 1:
                result += (int(10 ** a * a / 10) + int("".join(listN[i+1:])) + 1)
        return result

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # 将1-n全部转换为字符串
        # 只需要统计每个字符串中'1'出现的次数并相加即可
        count = 0
        for i in range(1,n+1):
            for i in str(i):
                if i == '1':
                    count += 1
        return count

最怕遇到这种有逻辑,得小心翼翼的题目了
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        //统计每一位上1出现的次数
        int ret = 0, base = 1;
        while (n/base) {
            int bit = (n / base) - (n / base) / 10 * 10;
            if (bit == 0)
                ret += n / (base * 10)*base;
            if (bit == 1)
                ret += n / (base * 10)*base + (n - n/base*base ) + 1;
            if (bit > 1)
                ret += (n / (base * 10) + 1)*base;
            base *= 10;
        }
        return ret;
    }
};

public class Solution {
  public int NumberOf1Between1AndN_Solution(int n) {
	    if(n<0){
	    	return 0;
	    }
	    String str= Integer.toString(n);
	    int result = getNumberOf1(str, 0);
	    return result;
    }
	public static int getNumberOf1(String str,int index){
		int length = str.length()-index;
		if(length==1 && str.charAt(index)=='0'){
			return 0;
		}
		if(length==1){
			return 1;
		}
		//计算最高位的1
		int first = str.charAt(index)-'0';
		int result = 0;
		if(first>1){
			result += exp(length-1); 
		}else if(first==1){
			result += 1 + Integer.parseInt(str.substring(index+1));
		}
		//计算除了最高位的其他位
		result += first *(length-1)*exp(length-2);
		//计算比如2345中0---345中1的个数进行递归
		result += getNumberOf1(str, index+1);
		
		return result;
	}
	public static int exp(int n){
		int result =1;
		while(n>=1){
			result*=10;
			n--;
		}
		return result;
	}
}

    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count=0
        for i in range(1,n+1):
            while i:
                if i%10==1:
                    count+=1
                i=i/10
        return count

public int NumberOf1Between1AndN(int n){
   long count=0;
   long i=1;
   for(i=1;i<=n;i*=10){
     long a=n/i,b=n%i;
     count=count+(a+8)/10*i;
     if(a%10==1){
       count+=b+1;
     }
     return (int)count;
  }

看了一圈似乎都是在数字本身上纠结的，我这个算是另辟奇径，就是把数字先转换为字符串，再连接起来，再数1出现的次数

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        str_n = ''
        for i in range(1, n + 1):
            str_n += str(i)
        res = str_n.count('1')
        return res

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        //count表示1出现的总次数
		int count = 0;
		//从1到n循环n次，对每一个数求它包含多少个1
		for (int i = 1; i <= n; i++) {
			int temp = i;
			//求这个数包含多少个1
			while (temp != 0) {
				if (temp % 10 == 1) {
					count++;
				}
				temp = temp / 10;
			}
		}
		return count;
    }
}

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

一位一位的计算

思路来自B站视频。以下是原链接
https://www.bilibili.com/video/BV1uJ411573j?t=1824
假设n = 7543 [x] 29
如果要让百位的x = 1，那么需要考虑以下几种情况：

1. 百位的x就是1的时，考虑前面4位数小于7543的情况，一共是0000-7542=7543种可能，而后面2位数的取值可以任意，00-99=100种可能
   • 总次数 = 7543 * 100
2. 考虑前面4位数就取7543，若百位的x > 1，如n = 7543 [6] 29，那么就可以在比n小的数字中取到百位是1的数字，而后2位数还是可以随便取，还是100种可能
   • 总次数 = 1 * 100
3. 若百位的x = 1，如 n = 7543 [1] 29，此时后两位就不能随便取值(因为要小于n)，那么取值范围就是 00-29=30种可能
   • 总次数 = 1 * 30
4. 若百位的x = 0，如 n = 7543 [0] 29，那么不可能取到百位是1的情况，因为一定比n大

   class Solution:
       def NumberOf1Between1AndN_Solution(self, n):
           # 运行时间：31ms  占用内存：5860k
           m = len(str(n))  # 数字的长度
           count = 0
           for i in range(1, m+1):
               high = n // 10 ** i                       # 找到当前位之前的位数
               mid = n % 10 ** i // 10 ** (i - 1)        # 找当前位
               low = n % 10 ** (i - 1)                   # 找当前位后面的位数
               # 第(1)个情况
               count += high * (10 ** (i - 1))
   
               if mid > 1:
                   # 第(2.1)个情况
                   count += 10 ** (i - 1)
               elif mid == 1:
                   # 第(2.2)个情况
                   count += (low + 1)
           return count

   
   

    # 利用组合数解题
    # 依次遍历每一个数位，计算该位为1的数有多少个，将结果累加返回
    # 每个数位计算的时候，对除去该位的前缀，后缀分别计算组合数
    # 同时需要保证组合出的数字在n的范围之内，所以将情况分为三种，该数位原本为1或者为0，或者为其他
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n == 1:  # 边界情况
            return 1
        ans = 0  # 最后返回的1的个数
        x = str(n)  # n的字符串形式，便于前缀后缀的数字转换
        for i in range(len(x)):  # 遍历每一个数位，计算该数位为1同时整个数在n之内的整数个数
            pre = int(x[:i]) if x[:i] else 0  # 前缀，没有前缀为0
            l = len(x[i + 1:])  # 后缀的长度
            # 该位原本为0的时候，合法数的前缀必小于pre，范围为[0,pre)，共有pre种，后缀任意均合法，共有10**l种
            if x[i] == '0':
                ans += pre * 10 ** l
            # 该位原本为1的时候，合法数有两种
            # 一种是前缀范围为[0,pre)，共有pre种，后缀任意
            # 另一种是前缀为pre，后缀范围[0,suf]，共suf+1种
            elif x[i] == '1':
                suf = int(x[i+1:]) if x[i+1:] else -1  # 后缀范围，没有后缀为-1
                ans += pre * 10 ** l + suf + 1
            # 其他情况下，合法数前缀范围[0,pre]，后缀任意
            else:
                ans += (pre+1) * 10 ** l
        return ans

function NumberOf1Between1AndN_Solution(n)
{    var count=0;
     var j=0;
     var sum=0;
    for(var i=1;i<=n;i++){
        var kk=i.toString();
        j=0;
        count=0;
        while(kk.indexOf(1,j)!==-1){
                count++;
                j=kk.indexOf(1,j)+1;
            }
        
        sum+=count;
    }
 return sum;
}

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
    int count=0;
    int high=0,low=0,nor=0;
    for(int i=1;i<=n;i*=10){
      high=n/(i*10);
      low=n%i;
      nor=(n-high*(i*10))/i;
      if(nor==0)count+=high*i;
      else if(nor>1)count+=(high+1)*i;
      else {count+=high*i+low+1;}
    }                
     return count;   
    }
}

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        if(n<=0)
          return 0;
        for(int i=1;i<=n;i++)
        {
            while(i>0)
              {
                 if(i%10==1)
                     count++;
                 i=i/10;
              }
        }
        return count;
    }
}
超时，，，，，，

    public int NumberOf1Between1AndN_Solution(int n) {
        if(n<10)return n>=1?1:0;
        int times=(int)(Math.pow(10,String.valueOf(n).length()-1));
        int a=Integer.parseInt(String.valueOf(n).substring(0,1));
        int b=Integer.parseInt(String.valueOf(n).substring(1,String.valueOf(n).length()));
        return a>1?times+a*NumberOf1Between1AndN_Solution(times-1)+NumberOf1Between1AndN_Solution(b):
                b+1+NumberOf1Between1AndN_Solution(times-1)+NumberOf1Between1AndN_Solution(b);
    }

    public int NumberOf1Between1AndN_Solution(int n) {
        int times = 0,current, addOne = 0,powerOfTen = 0,n2 = n;

        while (n > 0){
            current = n % 10;
            n /= 10;

            if (current > 1) {
                addOne = 1;
            }
            else if (current == 1){
                times += (n2 % Math.pow(10,powerOfTen)) + 1;
            }
            times += (n + addOne) * Math.pow(10, powerOfTen);

            powerOfTen++;
            addOne = 0;
        }

        return times;
    }

class Solution {
public:
    // 计算从0到n中1的总数
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;
    	for(int i=0;i<=n;i++) {
            count += NumberOf1(i);
        }
        return count;
    }
    // 计算数字n中1的个数
    int NumberOf1(int n)
    {
        int count = 0;
        while(n) {
            if(n%10 == 1) count++;
            n /= 10;
        }
        return count;
    }
};