Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
A:
就是每一位计算有多少个。
分为高一位 有多少个导致现在重复的。 和现在位有多少个1
public class Solution { public int countDigitOne(int n) { long num1s = 0; for(int i =0;i<32;i++){// for each digit long div = (long)Math.pow(10,i); if(div > n) break; num1s += n/(div*10)* div + helper(n%(div*10),div); // number of repeats + at this position } return (int)num1s; } private long helper(long x,long powerOf10){// get the number of 1s at x's first digit (x/powerOf10 < 10) long res = x/powerOf10; if(res==0) return 0; if(res >1) return powerOf10; return x - res * powerOf10 + 1; // for case x = 10, } }
这里的关键点是: 如何分解这个答案: 我们的分解方式是:
1: 从低到高,每一位计算
2: 对数字位 i(i = 0 to 31);
2.1 )看高于它的数字位, 会导致有多少个重复1(在i位上)的。
2.2) 看改位置:会有多少个重复的1 出现。 也就是 hepler函数。(这里又分为: 该位是否 为 1. 看1 的位置重复完了没有。 )
Mistakes:
1: 刚开始 计算高位重复的,给减了一
No comments:
Post a Comment