题目链接

LeetCode

题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

解题思路

方法一：暴力求解（不推荐） 的个数，然后累加，时间复杂度高。

  1. class Solution {
  2. public:
  3.     int computerInt(int n){
  4.         int res = 0,tmp;
  5.         while(n){
  6.             tmp = n%10;
  7.             if(tmp==1)
  8.                 res++;
  9.             n /= 10;
  10.         }
  11.         return res;
  12.     }
  13.     int countDigitOne(int n) {
  14.         int res = 0;
  15.         for(int i=1;i<=n;i++){
  16.             res += computerInt(i);
  17.         }
  18.         return res;
  19.     }
  20. };

方法二(密码锁)：

类似密码锁，先固定一位为1，即计算当前位置取1时，其他位置的所有可能.
image.png
43. 从 1 到 n 整数中 1 出现的次数 - 图2
image.png
43. 从 1 到 n 整数中 1 出现的次数 - 图4
image.png
43. 从 1 到 n 整数中 1 出现的次数 - 图6

  1. case 1: cur=0
  2.      2  3   0  4
  3.      千位和百位可以选 00 01 02....22  十位可以取到1时( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9  共有 23 * 10 种排列
  4.      当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
  5.      但是2301不应该算进来，这个1是 单独  出现在个位的（而11，121,111这种可以被算多次）
  6.      即 23*10
  7. case 2: cur=1
  8.    2  3  1  4
  9.    千位和百位可以选 00 01 02....22  十位可以取到 1 个位可以选 0-9  共有 23 * 10 中排列
  10.    当千位和百位取23,十位取1，个位可以取 0-4 即 2310-2314共5个
  11.    即 23 *10 + 4 +1
  12. case 3: cur>1 即2-9
  13.    2  3  2  4
  14.    千位和百位可以选00 01 02....22  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9  共有 23 * 10 中排列
  15.    当千位和百位取23,十位取1，个位可以取0-9 即 2310-2319共10个 （其中2311，被计算了两次，分别是从个位和十位分析得到的1次）
  16.    即 23 *10 + 10

image.png
代码如下：

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        int high = n/10,cur = n%10,low = 0;
        double digit = 1;
        while(high!=0||cur!=0){
            if(cur==0){ // 当前位为 0 时，1到n中 1 的个数
                res += high * digit;
            }else if(cur==1){ // 当前位为 1 时，1到n中 1 的个数
                res += high * digit + low + 1;
            }else{ // 当前位大于 1 时，1到n中 1 的个数
                res += high * digit + digit;
            }
            low += cur*digit;
            digit *= 10;
            cur = high%10;
            high /= 10;
        }
        return res;
    }
};
  • 时间复杂度：O(logN)
  • 空间复杂度：O(1)