例如, 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次
注意:11 这种情况算两次
数据范围:
进阶:空间复杂度 ,时间复杂度
int NumberOf1Between1AndN_Solution(int n) { int cnt = 0; int a=0,b=0; for(long long m=1;m<=n;m*=10){ a = n/m; b = n%m; cnt+=(a+8)/10*m + (a%10==1)*(b+1); } return cnt; }
注意:只有n的第m位为1时需要计算后缀,后缀计算为 (n/m%10==1)*(b+1),
即(n/m%10==1)判断第m位是否为1,若为1,则加上(b+1),若不为1,则只计算前缀。(若计算2的个数,可以改为(n/m%10==2)*(b+1),若计算3的个数,可以改为(n/m%10==3)*(b+1)…以此类推)
class Solution { public: /* 我们从低位到高位求每位1出现的次数,累加求和即可 例如:求0~abcde中1的个数,现在我们求c这一位中1出现的次数,其他位雷同 有两部分组成 第一部分:ab * 100,表示当ab这两位在0~ab-1范围内时,de可以从0~99取值 第二部分:如果c>1时,当ab为ab时1的个数为0~99 如果c=1时,当ab为ab时1的个数为de + 1 如果c<0时,当ab为ab是1的个数为0 */ int NumberOf1Between1AndN_Solution(int n) { int exp = 1; int ans = 0; while(n / exp) { ans += n / (exp * 10) * exp; if(n % (exp * 10) / exp > 1) ans += exp; else if(n % (exp * 10) / exp == 1) ans += (n % exp + 1); exp *= 10; } return ans; } };
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
例:对于824883294,先求0-800000000之间(不包括800000000)的,再求0-24883294之间的。
如果等于1,如1244444,先求0-1000000之间,再求1000000-1244444,那么只需要加上244444+1,再求0-244444之间的1
如果大于1,例:0-800000000之间1的个数为8个100000000的1的个数加上100000000,因为从1000000000-200000000共有1000000000个数且最高位都为1。
对于最后一位数,如果大于1,直接加上1即可。
"""
result = 0
if n < 0:
return 0
length = len(str(n))
listN = list(str(n))
for i, v in enumerate(listN):
a = length - i - 1 # a为10的幂
if i==length-1 and int(v)>=1:
result+=1
break
if int(v) > 1:
result += int(10 ** a * a / 10) * int(v) + 10**a
if int(v) == 1:
result += (int(10 ** a * a / 10) + int("".join(listN[i+1:])) + 1)
return result
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { if (n < 1) return 0; int len = getLenOfNum(n); if (len == 1) return 1; int tmp = (int) Math.pow(10, len - 1); int first = n / tmp; int firstOneNum = first == 1 ? n % tmp + 1 : tmp; int otherOneNUm = first * (len - 1) * (tmp / 10); return firstOneNum + otherOneNUm + NumberOf1Between1AndN_Solution(n % tmp); } private int getLenOfNum(int n) { int len = 0; while (n != 0) { len++; n /= 10; } return len; } }左神书中原题,比剑指offer中的讲解好得多,向左神致敬!
最怕遇到这种有逻辑,得小心翼翼的题目了 class Solution { public: int NumberOf1Between1AndN_Solution(int n) { //统计每一位上1出现的次数 int ret = 0, base = 1; while (n/base) { int bit = (n / base) - (n / base) / 10 * 10; if (bit == 0) ret += n / (base * 10)*base; if (bit == 1) ret += n / (base * 10)*base + (n - n/base*base ) + 1; if (bit > 1) ret += (n / (base * 10) + 1)*base; base *= 10; } return ret; } };
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { if(n<0){ return 0; } String str= Integer.toString(n); int result = getNumberOf1(str, 0); return result; } public static int getNumberOf1(String str,int index){ int length = str.length()-index; if(length==1 && str.charAt(index)=='0'){ return 0; } if(length==1){ return 1; } //计算最高位的1 int first = str.charAt(index)-'0'; int result = 0; if(first>1){ result += exp(length-1); }else if(first==1){ result += 1 + Integer.parseInt(str.substring(index+1)); } //计算除了最高位的其他位 result += first *(length-1)*exp(length-2); //计算比如2345中0---345中1的个数进行递归 result += getNumberOf1(str, index+1); return result; } public static int exp(int n){ int result =1; while(n>=1){ result*=10; n--; } return result; } }
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int count=0; for (int i = 0; i <= n; i++) { String s = Integer.toString(i); char[] chars = s.toCharArray(); for (char aChar : chars) { if(aChar=='1'){ count++; } } } return count; } }
看了一圈似乎都是在数字本身上纠结的,我这个算是另辟奇径,就是把数字先转换为字符串,再连接起来,再数1出现的次数
class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here str_n = '' for i in range(1, n + 1): str_n += str(i) res = str_n.count('1') return res
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { //count表示1出现的总次数 int count = 0; //从1到n循环n次,对每一个数求它包含多少个1 for (int i = 1; i <= n; i++) { int temp = i; //求这个数包含多少个1 while (temp != 0) { if (temp % 10 == 1) { count++; } temp = temp / 10; } } return count; } }
思路来自B站视频。以下是原链接
https://www.bilibili.com/video/BV1uJ411573j?t=1824
假设n = 7543 [x] 29
如果要让百位的x = 1,那么需要考虑以下几种情况:
class Solution: def NumberOf1Between1AndN_Solution(self, n): # 运行时间:31ms 占用内存:5860k m = len(str(n)) # 数字的长度 count = 0 for i in range(1, m+1): high = n // 10 ** i # 找到当前位之前的位数 mid = n % 10 ** i // 10 ** (i - 1) # 找当前位 low = n % 10 ** (i - 1) # 找当前位后面的位数 # 第(1)个情况 count += high * (10 ** (i - 1)) if mid > 1: # 第(2.1)个情况 count += 10 ** (i - 1) elif mid == 1: # 第(2.2)个情况 count += (low + 1) return count
# 利用组合数解题 # 依次遍历每一个数位,计算该位为1的数有多少个,将结果累加返回 # 每个数位计算的时候,对除去该位的前缀,后缀分别计算组合数 # 同时需要保证组合出的数字在n的范围之内,所以将情况分为三种,该数位原本为1或者为0,或者为其他 def NumberOf1Between1AndN_Solution(self, n): # write code here if n == 1: # 边界情况 return 1 ans = 0 # 最后返回的1的个数 x = str(n) # n的字符串形式,便于前缀后缀的数字转换 for i in range(len(x)): # 遍历每一个数位,计算该数位为1同时整个数在n之内的整数个数 pre = int(x[:i]) if x[:i] else 0 # 前缀,没有前缀为0 l = len(x[i + 1:]) # 后缀的长度 # 该位原本为0的时候,合法数的前缀必小于pre,范围为[0,pre),共有pre种,后缀任意均合法,共有10**l种 if x[i] == '0': ans += pre * 10 ** l # 该位原本为1的时候,合法数有两种 # 一种是前缀范围为[0,pre),共有pre种,后缀任意 # 另一种是前缀为pre,后缀范围[0,suf],共suf+1种 elif x[i] == '1': suf = int(x[i+1:]) if x[i+1:] else -1 # 后缀范围,没有后缀为-1 ans += pre * 10 ** l + suf + 1 # 其他情况下,合法数前缀范围[0,pre],后缀任意 else: ans += (pre+1) * 10 ** l return ans
function NumberOf1Between1AndN_Solution(n) { var count=0; var j=0; var sum=0; for(var i=1;i<=n;i++){ var kk=i.toString(); j=0; count=0; while(kk.indexOf(1,j)!==-1){ count++; j=kk.indexOf(1,j)+1; } sum+=count; } return sum; }数字转换成字符串,匹配字符1的个数,原谅我是个数学渣。。。。。
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int count=0; int high=0,low=0,nor=0; for(int i=1;i<=n;i*=10){ high=n/(i*10); low=n%i; nor=(n-high*(i*10))/i; if(nor==0)count+=high*i; else if(nor>1)count+=(high+1)*i; else {count+=high*i+low+1;} } return count; } }这个问题可以先用数学方法化简,可以把时间复杂度降至o(logn),否则直接遍历累加的时间复杂度为o(nlogn),可以说题目真正想问的应该是这种o(logn)的方法。