题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#
整数中1出现的次数（从1到n整数中1出现的次数）
http://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6
本题解决思路：递归算法
具体思路：
编写一个输入为数字n的函数：
若n为个位数，且n<1，则1出现的次数为0；
若n为个位数，且n<10，则1出现的次数为1；
以上是显然的，一下为了更简明的说明原理，适当的地方以n为21231为例进行说明
若n不为个位数，则对n进行"降位"（假设n去掉首位后的剩余数字为m，例如21231去掉首位后为1231），具体情况又依据首位的数字不同而有不同情况：（显然n的首位数字必然大于等于1）
若n的首位数字为1，则说明当1作为首位时，共计出现m+1次（之所以+1是因为存在m为0000这种情况），此外，剩余1都在m中出现，由于首位为1，那么除1~m（例如1~1231）这一序列外，必然还存在1~9999这一序列（出现1次）；
若n的首位数字大于1，与上一行情况不同在于，当1作为首位时，共计出现 10^(n的位号-1) 次（例如n=21231时，1xxxx共计出现10000次），此外，剩余1都在m出现以及在1~9999这一序列出现，且后者共计出现“n的首位数字”次（例如n=21231时，出现2次）
由此，递归建立
代码如下：
# -*- coding:utf-8 -*- class Solution: def NumberOf1Between1AndN_Solution(self, n): return cal_one(n) def cal_one(n): if n < 1: return 0 elif n < 10: return 1 else: n_str = str(n) # 将n转化为字符串 n_len = len(n_str) # 获取n的位数 n_1st = int(n_str[0]) # n的首位数字 n_others = int(n_str[1:n_len]) # 获取剩余数字 if n_1st == 1: return int(n_others)+1+cal_one(pow(10, n_len-1)-1)+cal_one(n_others) else: return pow(10, n_len-1)+n_1st*cal_one(pow(10, n_len-1)-1)+cal_one(n_others) # write code here
OPPO公司福利 1202人发布
查看17道真题和解析