剑指--1~n整数中1出现的次数
剑指–1~n整数中1出现的次数1,题目:2,思路:方法一:分而治之:将 1 ~ n 的个位、十位、百位、…的 1出现次数相加,即为 1 出现的总次数。设数字 n 是个 x 位数,记 n 的第 i 位为 ni,则可将 n 写为 NxNx-1…N2N1称Ni为 当前位 ,记为 cur,将 " Ni-1Ni-2…N2N1 称为‘低位’ ,记为 low ;将 " NxNx-1… Ni+2Ni+1 称为 高
剑指–1~n整数中1出现的次数
1,题目:
2,思路:
方法一:分而治之:
将 1 ~ n 的个位、十位、百位、…的 1出现次数相加,即为 1 出现的总次数。
设数字 n 是个 x 位数,记 n 的第 i 位为 ni,
则可将 n 写为 NxNx-1…N2N1
称Ni为 当前位 ,记为 cur,
将 " Ni-1Ni-2…N2N1 称为‘低位’ ,记为 low ;
将 " NxNx-1… Ni+2Ni+1 称为 高位 ,记为 high。
将 10^i称为 位因子 ,记为 digit。
-
首先初始化,cur指针指向数字的个位,其前面的位数都是high位,刚开始是没有low位的,
-
然后根据cur的值进行res的计算:
-
cur=0;执行res+=high*digit
-
cur=1;执行res+=high*digit+low+1
-
cur>1;执行res+=high*digit+digit
-
每次计算完,以后,cur指针会向前移动,然后其对应的high位,cur位,还有low位都已经变了,然后根据cur为0 或1 或>1来计算这轮res的值
-
就这样指针移动,计算值,最后的res值就是所求值
下面为对应的图解:
方法二:递归:
根据,本例中的是999中1的个数:300, 99的话就是20 ; 9的话就是1 ;9999就是4000 这里找到规律,实现递归的调用。
3,代码:
方法一:分而治之(将 1 ~ n 的个位、十位、百位、…的 1出现次数相加,即为 1 出现的总次数)。
class Solution {
public int countDigitOne(int n) {
//将 1 ~ n 的个位、十位、百位、...的 1出现次数相加,即为 1 出现的总次数。
/*
设数字 n 是个 x 位数,记 n 的第 i 位为 ni,
则可将 n 写为 NxNx-1......N2N1
称Ni为 当前位 ,记为 cur,
将 " Ni-1Ni-2......N2N1 称为‘低位’ ,记为 low ;
将 " NxNx-1... Ni+2Ni+1 称为 高位 ,记为 high。
将 10^i称为 位因子 ,记为 digit。
首先初始化,cur指针指向数字的个位,其前面的位数都是high位,刚开始是没有low位的,
然后根据cur的值进行res的计算:
cur=0;执行res+=high*digit
cur=1;执行res+=high*digit+low+1
cur>1;执行res+=high*digit+digit
每次计算完,以后,cur指针会向前移动,然后其对应的high位,cur位,还有low位都已经变了,
然后根据cur为0 或1 或>1来计算这轮res的值
就这样指针移动,计算值,最后的res值就是所求值
*/
int digit = 1, res = 0;//先初始化,因为给一个数字,cur指针先指向最后一位,也就是个位,其十位,百位,,,都是high,是没有low位的,在后面的循环中,cur往前移动一位,则对应的high少一位,low就多一位
int high = n / 10, cur = n % 10, low = 0;//这个也是初始化
while(high != 0 || cur != 0) {
if(cur == 0) res += high * digit;
else if(cur == 1) res += high * digit + low + 1;
else res += (high + 1) * digit;
low += cur * digit;//计算完一轮的high,low,cur等指针会移动,下面是移动后的指针赋值
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
}
代码二:递归
class Solution {
public int countDigitOne(int n) {
//方法二:用到了递归
return f(n);
}
//下面我们都用 1234 和 2345 来举例
private int f(int n){
// 上一级递归 n = 20、10之类的整十整百之类的情况;以及n=0的情况
if(n== 0) return 0;
// n < 10 即为个位,这样子只有一个1
if(n < 10) return 1;
String s = String.valueOf(n);//数值转为字符串
//长度:按例子来说是4位
int length = s.length();
//这个base是解题速度100%的关键,本例中的是999中1的个数:300
// 99的话就是20 ; 9的话就是1 ;9999就是4000 这里大家应该发现规律了吧。
int base = (length-1)*(int)Math.pow(10,length-2);
//high就是最高位的数字
int high = s.charAt(0) - '0';
//cur就是当前所数量级,即1000
int cur = (int)Math.pow(10,length -1);
if(high == 1){
//最高位为1,1+n-cur就是1000~1234中由千位数提供的1的个数,剩下的f函数就是求1000~1234中由234产生的1的个数
return base + 1 + n - cur + f(n - high * cur);
}else{
//这个自己思考
return base * high + cur + f(n- high * cur);
}
}
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)