31.整数のうち1が現れる回数（1からnまでの整数のうち1が現れる回数）

『剣指Offer』ブラシ問題GitHubリンク
タイトルリンク

タイトルの説明

1~13の整数のうち1が出現する回数を求め、100~1300の整数のうち1が出現する回数を算出する?そのため、1~13に含まれる1の数字を1、10、11、12、13と特別に数えて6回も現れたが、後の問題には仕方がない.ACMerはあなたたちが彼を助けることを望んで、そして問題をもっと普遍化して、すぐに任意の非負の整数区間の中で1の出現の回数(1からnの中で1の出現の回数)を求めることができます.

問題を解く構想.

一人一人の上位1の出現回数を合わせると、求めた総回数になります.
百位を例にとると、12x45のうち、百位はxであり、百位前の数字は12であり、百位後の数字は45である.この場合は3つのケースに分けられます.

x == 0この場合、後ろの数字は百桁上1の出現回数に影響を及ぼさず、前の数字のみの影響、すなわち、12 * 100、100は百桁となる.

x == 1この場合、前の数字の影響も後の数字の影響も受けますが、12 * 100後、1がまた後の数字+1ほど複数回(12100から12145まで)、つまり12 * 100 + 45 + 1.

x > 1、この場合は必ず12100-12199合計100(100桁)個1を含むので、100桁上1の出現回数も後の数字には関係なく12 * 100 + 100つまり(12 + 1) * 100となる.

Code

function NumberOf1Between1AndN_Solution(n)
{
    // write code here
    var count = 0;
    var i = 1;
    var pre = 0, back = 0, cur = 0;
    while(n >= i){
        pre = parseInt(n / (i * 10));
        back = n - parseInt(n / i) * i;
        cur = parseInt(n / i) % 10;
        if(cur == 0){
            count += pre * i;
        }else if(cur == 1){
            count += pre * i + back + 1;
        }else{
            count += (pre + 1) * i
        }
        i *= 10;
    }
    return count;
}