輸入1個(gè)整數(shù)n，求從1到n這n個(gè)整數(shù)的10進(jìn)制表示中1出現(xiàn)的次數(shù)。例如輸入12，從1到12這些整數(shù)中包括1的數(shù)字有1，10,11,12共出現(xiàn)5次
這個(gè)題目比較難
直接暴力
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
for(int i =1;i<=n;i++){
count +=NumberOf1(i);
}
return count;
}
public int NumberOf1(int num){
int count =0;
while(num!=0){
if(num%10==1){
count++;
}
num/=10;
}
return count;
}
}對(duì)數(shù)字n，有
對(duì)1到n內(nèi)的數(shù)統(tǒng)計(jì)1的次數(shù)，時(shí)間復(fù)雜度就是
編程之美上講授很詳細(xì)，不想敲字了
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
int factor = 1;
int low = 0;
int cur = 0;
int high = 0;
while(n/factor!=0){
cur = (n/factor)%10; //當(dāng)前位
low = n - (n/factor)*factor ;// 低位數(shù)字
high = n/(factor*10); //更高位
switch( cur){
case 0:
count+= high* factor;
break;
case 1:
count+= high* factor + low + 1;
break;
default:
count +=(high+1) * factor;
break;
}
factor *=10;
}
return count;
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
