【剑指offer】43 1-n整数中1出现的次数（难）

蔚落 2021-10-03 02:24 249阅读 0赞

[面试题43. 1～n整数中1出现的次数][43. 1_n_1]

难度中等28

输入一个整数 `n` ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

**示例 1：**

输入：n = 12
    输出：5

**示例 2：**

输入：n = 13
    输出：6

解题思路：刚开始自己用的普通方法，结果时间超限了。

class Solution {
        public static int countOne(int n){
            int count = 0;
            StringBuilder sb = new StringBuilder();
            if(n>9){
                int temp = n%10;
                n = n/10;
                sb.append(temp);
            }
            sb.append(n);
            String s = String.valueOf(sb);
            for(int i = 0;i<s.length();i++){
                if(s.charAt(i) == '1')
                    count++;
            }
            return count;
        }
        public int countDigitOne(int n) {
            int sum = 0;
            for(int i = 1;i<=n;i++){
                sum+=countOne(i);
            }
            return sum;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70][]

思路是对的，就是方法太low，遇到比较大的数字就会时间超限。

解法二：

dfs（n）表示数字n有多少个1；

我们可以利用这样的例子进行思考，

假设数字为1234，则high = 1 pow = 1000 low = 234；

其中当高位为1的时候的1的个数 234+1（low+1）；

然后就是pow中1的个数为 dfs（pow）

low中1的个数为 dfs（low）

最后结果就是low+1+dfs(pow)+dfs(low)

假设数字是2234 则high = 2,pow = 1000 low = 234

则可以将数字分成 0 - 999，1000-1999，2000-2234，

在0-999范围内，dfs（pow-1）

在1000-1999范围内分为两部分

当高位确定是1的时候：就是1的个数就是pow

抛开高位为1的情况：就是dfs(pow-1)

2000-2234

就是dfs（low）

最后的结果就是

pow+high\*dfs（pow-1）+dfs（low）

class Solution {
        public int dfs(int n){
            if(n<=0)
                return 0;
            String s = String.valueOf(n);
            int high = s.charAt(0) - '0';
            int pow = (int)Math.pow(10,s.length()-1);
            int low = n-high*pow;
            if(high == 1){
                return dfs(pow-1)+low+1+dfs(low);
            }else{
                return pow+high*dfs(pow-1)+dfs(low);
            }    
        }
        public int countDigitOne(int n) {
            return dfs(n);
        }
    }

[43. 1_n_1]: https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70]: /images/20211003/833e68efa88e434dbdc6250946857640.png