整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）
題目描述
求出113的整數(shù)中1出現(xiàn)的次數(shù),并算出1001300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1员帮、10、11剑辫、12阱飘、13因此共出現(xiàn)6次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)速妖。
思路
- 設(shè)n=abcde高蜂，自右至左，從1開(kāi)始標(biāo)號(hào)罕容。
- 如果第i位上的數(shù)字為0备恤，則第i位可能出現(xiàn)1的次數(shù)由其高位決定稿饰，若沒(méi)有高位，則視為0露泊，此時(shí)第i位可能出現(xiàn)1的次數(shù)為：其高位數(shù)*10(i-1)喉镰，例如若c為0，則次數(shù)為ab*102;
- 如果第i位上的數(shù)字為1惭笑，則第i位上可能出現(xiàn)1的次數(shù)受其高位和低位影響侣姆，若沒(méi)有，則視為0沉噩，此時(shí)第i位可能出現(xiàn)1的次數(shù)：其高位數(shù)*10(i-1)+（低位數(shù)+1）捺宗，例如若c為1，則次數(shù)為ab*102+（de+1）;
- 如果第i位上的數(shù)字大于1川蒙，則第i位上可能出現(xiàn)1的次數(shù)受其高位影響蚜厉，若沒(méi)有，則視為0畜眨，此時(shí)第i位可能出現(xiàn)1的次數(shù)：（其高位數(shù)+1）*10(i-1)昼牛，例如若c大于1，則次數(shù)為（ab+1）*102;
實(shí)現(xiàn)代碼
function NumberOf1Between1AndN_Solution(n) {
if (n < 0) return 0;
var high, low, cur, temp, i = 1;
high = n;
var count = 0;
while (high !== 0) {
high = parseInt(n / Math.pow(10, i)); // 第i位數(shù)的高位
temp = n % Math.pow(10, i);
cur = parseInt(temp / Math.pow(10, i - 1)); // 第i位數(shù)
low = temp % Math.pow(10, i - 1); // 第i位數(shù)的低位
if (cur === 1) {
count += high * Math.pow(10, i - 1) + low + 1;
} else if (cur < 1) {
count += high * Math.pow(10, i - 1);
} else {
console.log(count, high);
count += (high + 1) * Math.pow(10, i - 1);
}
i++;
}
return count;
}
