[数据结构与算法]LeetCode-【模拟】数字1的个数

题目描述

题目分析

由于n取值过大，使用0~n的遍历会很慢
但是我们发现，n的位数只有9位！！！
那么是否可以按照位数遍历，求每一位字符可以取值为1的次数，然后把所有位对应的次数叠加，问题就迎刃而解了
那么每一位次数如何去求？
可以按照当前字符，把字符串切开为前后两段，把前后两段取值种数相乘即可。

针对几个特殊情况：110 13
我们可以把当前字符分为是否大于1，等于1还是小于1，分情况讨论：

1. 如果大于1，如3120中的2，则前乘因子为32，后乘因子为10（因为可以取0~9）
2. 如果等于1，如果首字符如123的1，前乘因子1后乘因子24；如果不是首字符如213的1，则当百位取2时，后乘因子只能取0~4，百位不是2时，后乘因子为10
3. 如果小于1，如201的0，则后乘因子同1，不同的是前乘因子需要-1，比如输入0，则最终结果ans = (1 - 1)*1 = 0

python实现

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        n_str = str(n)      #将整数转化为字符串
        n_len = len(n_str)  #整数长度
        former_mul,latter_mul = 0,0     #按当前字符划分前乘因子和后乘因子
        ans = 0                         #输出结果
        for cur_index in range(n_len):
            cur_char = n_str[cur_index]
            if cur_char>'1':
                latter_mul = pow(10, n_len - 1 - cur_index)
                former_mul = 1 + n/pow(10, n_len - cur_index)
                ans += former_mul*latter_mul
            elif cur_char == '1':           #当前字符为1时后乘因子分情况讨论
                former_mul = 1 + n/pow(10, n_len - cur_index)
                if former_mul == 1:
                    #若为首字符
                    latter_mul = n%pow(10, n_len - 1 - cur_index) + 1
                    ans += former_mul*latter_mul
                else:
                    #当 former_mul 与 n 切割后的前半段相同时，latter_mul取值不再是10的倍数
                    latter_mul1 = n%pow(10, n_len - 1 - cur_index) + 1
                    latter_mul2 = pow(10, n_len - 1 - cur_index)
                    ans += 1*latter_mul1 + (former_mul-1)*latter_mul2
            else:
                #当前字符为0
                latter_mul = pow(10, n_len - 1 - cur_index)
                former_mul = n/pow(10, n_len - cur_index)
                ans += former_mul*latter_mul    
        return ans

代码性能