编辑代码


// 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;   
    }
 * 
 */