Leetcode 233 - 数字 1 的个数

系统管理员 2021-10-18 16:52 245阅读 0赞

### 文章目录 ###

*  1. 暴力求解
 *   *  1.1 思路
     *  1.2 复杂度
     *   *  1.2.1 时间复杂度 O(nlogn)
         *  1.2.2 空间复杂度 O(1)
     *  1.3 代码
 *  2. 找规律（一）
 *   *  2.1 思路
     *   *  2.1.1 整除部分
         *  2.1.2 余数部分
     *  2.2 复杂度
     *   *  2.2.1 时间复杂度 O(logn)
         *  2.2.2 空间复杂度 O(1)
     *  2.3 代码
 *  3. 找规律（二）
 *   *  3.1 思路
     *  2.2 复杂度
     *   *  2.2.1 时间复杂度 O(logn)
         *  2.2.2 空间复杂度 O(1)
     *  2.3 代码

# 1. 暴力求解 #

## 1.1 思路 ##

对任意一个正整数 m，通过不断地除法和取余，可以计算出包含数字 1 的个数；遍历 \[1, n\] 内所有正整数，可以统计出所有数字 1 的个数，解题完毕。

## 1.2 复杂度 ##

### 1.2.1 时间复杂度 O(nlogn) ###

每次遍历，计算正整数 m 包含数字 1 个数的过程，消耗时间与整数位数成正比，时间复杂度 O(logn)；从 1 遍历到 n，故总体时间复杂度 O(nlogn)。

### 1.2.2 空间复杂度 O(1) ###

## 1.3 代码 ##

class Solution {
        public int countDigitOne(int n) {
            if (n < 1) {
                return 0;
            }
    
            int res = 0;
            for (int i = 1; i <= n; i++) {
                int m = i;
                while (m != 0) {
                    if (m % 10 == 1) {
                        res++;
                    }
                    m = m / 10;
                }
            }
            return res;
        }
    }

# 2. 找规律（一） #

## 2.1 思路 ##

这里，以 n = 117 为例，数字 1 一共出现 48 次，其中：

**个位**：`117/10 = 11······7`

*  1-110 为整除部分，出现 11 次：1、11、21、31、41、51、61、71、81、91、101
 *  111-117 为余数部分，出现 1 次：111

**十位**：`117/100 = 1······17`

*  1-100 为整除部分，出现 10 次：10、11、……、18、19、110
 *  101-117 为余数部分，出现 8 次：111、……、116、117

**百位**：`117/1000 = 0······117`

*  1-117 全部为余数部分，出现 18 次：100、101、102、……、116、117

### 2.1.1 整除部分 ###

**每 `10 * i` 个数，`i` 位上的 1 出现 `i` 次，即 `n / (i*10) * i (i = 1,10,100,1000……)`。**

*  每 10 个数，个位上的 1 出现 1 次。例如 1-10（1）、11-20（11）、21-30（21）等；
 *  每 100 个数，十位上的 1 出现 10 次。例如 1-100（10-19）、101-200（110-119）、201-300（210-219）等；

### 2.1.2 余数部分 ###

**`i` 位上的 1 额外增加次数与当前数位的值有关，具体为 `min(max((n mod (i*10))−i+1, 0), i)`。**

*  如果当前数位上的数是 0，额外增加 `0`，对应 min(max((n mod (i\*10))−i+1, `0`), i)，例如 107 十位额外增加 0；
 *  如果当前数位上的数是 1，额外增加 `次位数值+1`，对应 min(max(`(n mod (i*10))−i+1`, 0), i)，例如 117 十位额外增加 8；
 *  如果当前数位上的数是 2，额外增加 `当前数位基数`，对应 min(max((n mod (i\*10))−i+1, 0), `i`)，例如 127 十位额外增加 19；

如果个位上的数是 0，额外增加 `0`；否则，额外增加 `1`，符合上述规律。

## 2.2 复杂度 ##

### 2.2.1 时间复杂度 O(logn) ###

每次遍历时间复杂度 O(1)，遍历的次数等于 n 的位数，故总体时间复杂度 O(logn)。

### 2.2.2 空间复杂度 O(1) ###

## 2.3 代码 ##

class Solution {
        public int countDigitOne(int n) {
            if (n < 1) {
                return 0;
            }
    
            int res = 0;
            long i = 1;
            while (n >= i) {
                res += n / (i * 10L) * i + Math.min(Math.max(n % (i * 10L) - i + 1L, 0L), i);
                i *= 10L;
            }
            return res;
        }
    }

# 3. 找规律（二） #

## 3.1 思路 ##

> 规律与上一解法相同，思路都是逐位统计个数，同时分 0，1，>1 三种情况讨论。不同的是，该解法归纳出一个通用公式，更便于理解和实现。

以计算百位上 1 的个数为例，按照百位数字为 0，1，> 1 三种情况讨论：

*  如果当前数位上的数是 0，n = 3141092，a = 31410，b = 92，百位上 1 的个数为 3141 \* 100 + 0；
 *  如果当前数位上的数是 1，n = 3141192，a = 31411，b = 92，百位上 1 的个数为 3141 \* 100 + 92 + 1；
 *  如果当前数位上的数是 2，n = 3141592，a = 31415，b = 92，百位上 1 的个数为 3141 \* 100 + 100；

**通用公式 (a + 8) / 10 \* m + (a % 10 == 1) \* (b + 1)**

## 2.2 复杂度 ##

### 2.2.1 时间复杂度 O(logn) ###

每次遍历时间复杂度 O(1)，遍历的次数等于 n 的位数，故总体时间复杂度 O(logn)。

### 2.2.2 空间复杂度 O(1) ###

## 2.3 代码 ##

class Solution {
        public int countDigitOne(int n) {
            if (n < 1) {
                return 0;
            }
    
            int res = 0;
            long i = 1;
            while (n >= i) {
                res += (n / i + 8) / 10 * i + ((n / i) % 10 == 1 ? (n % i + 1) : 0);
                i *= 10;
            }
            return res;
        }
    }

**修订记录：**

<table> 
 <thead> 
  <tr> 
   <th>日期</th> 
   <th>版本号</th> 
   <th>作者</th> 
   <th>修订内容</th> 
   <th>备注</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>2019-8-13</td> 
   <td>1.0</td> 
   <td>moonspirit</td> 
   <td>创建文档</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>