// Solution:https://www.cnblogs.com/lengender-12/p/6876897.html
// 总结一下以上的算法,可以看到,当计算右数第 i 位包含的 x 的个数cnt[i]时:
// - 取第 i 位左边(高位)数字组成的数,乘以 10^(i-1),得到基础值 a
// - 取第 i 位数字,计算修正值
// - 如果大于 x,则结果为 a + 10^(i-1);
// - 如果小于 x,则结果为 a;
// - 如果等于 x,则取第 i 位右边(低位)数字组成的数,设为 b,最后结果为 a + b + 1;
function NumberOf1Between1AndN_Solution(n) {
if(n < 1) return 0;
if(n < 9) return 1;
// let left = 0; // 第 i 位左边(高位)的数字组成的数
// let right = 0; // 第 i 位右边(低位)数字组成的数b
let cnt = 0; // 返回的结果总数
let i = 1; // 第i位(第i次迭代)
let n_i = 0; // 第i位数字 = Math.floor( n % (m*10) / m )
let m = 1; // m = Math.pow(10, i-1);
while( m <= n ) {
// 数字在第i位出现的次数
let cnt_i = 0;
// 取第 i 位左边(高位)数字组成的数,乘以 m=10^(i-1),得到基础值 a
let left = Math.floor( n / (m*10) );
let a = left * m;
console.log('a:\t',a);
// 取第 i 位数字 n_i
n_i = Math.floor( n % (m*10) / m );
if(n_i > 1) { // 如果大于 x,则结果为 a + 10^(i-1)
cnt_i = a + m;
} else if(n_i < 1) { // 如果小于 x,则结果为 a
cnt_i = a;
} else {
// 如果等于 x,则取第 i 位右边(低位)数字组成的数,设为 b,最后结果为 a + b + 1;
let right = n % m;
console.log('right:\t',right);
cnt_i = a + right + 1;
}
console.log('i='+i+'; \tn_i='+n_i+'; \tm='+m+'; \tleft='+left+'; \tcnt_i='+cnt_i);
cnt += cnt_i;
m *= 10;
i += 1;
console.log('judge: '+m+' < '+n+' = '+(m <= n));
}
return cnt;
}
let number = 2593;
console.log('number:\t', number);
let res = NumberOf1Between1AndN_Solution(number);
console.log('res:\t', res);
/*
* // 附:java实现
public static int NumberOf1Between1AndN_Solution(int n)
{
if(n < 1) return 0;
if(n < 9) return 1;
int high = 0;
int k = 0;
int cur = 0;
int count = 0;
for(int i = 1; (k = n / i) > 0; i *= 10){
high = k / 10;
count += high * i;
cur = k % 10;
if(cur > 1)
count += i;
else if(cur == 1)
count += n - k * i + 1;
}
return count;
}
*
*/