首页 > 代码库 > LintCode-Digit Counts
LintCode-Digit Counts
Count the number of k‘s between 0 and n. k can be 0 - 9.
Example
if n=12, in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have FIVE 1‘s (1, 10, 11, 12)
Analysis:
Method 1: directly count every number.
Method 2: Analytical solution.
Every time, calculate how many k has appears on a specific postion, i.e., on 1, 10, 100,.....
Solution 1:
1 class Solution { 2 /* 3 * param k : As description. 4 * param n : As description. 5 * return: An integer denote the count of digit k in 1..n 6 */ 7 public int digitCounts(int k, int n) { 8 int[] record = new int[10]; 9 Arrays.fill(record,0);10 for (int i=0;i<=n;i++){11 String temp = Integer.toString(i);12 for (int j=0;j<temp.length();j++){13 int ind = (int) (temp.charAt(j)-‘0‘);14 record[ind]++;15 }16 }17 return record[k];18 19 }20 };
Solution 2:
1 class Solution { 2 /* 3 * param k : As description. 4 * param n : As description. 5 * return: An integer denote the count of digit k in 1..n 6 */ 7 public int digitCounts(int k, int n) { 8 int res = 0; 9 int base = 1;10 while (base<=n){11 int part1 = n/(base*10);12 if (base>1 && k==0 && part1>0) part1--;13 part1 *= base;14 int bar = n/base%10;15 int part2 = 0;16 if (k<bar) part2 = base;17 else if (k==bar) part2 = n%base+1;18 if (k==0 && n<base*10) part2 = 0;19 res += part1+part2;20 base*=10;21 }22 return res; 23 }24 };
LintCode-Digit Counts
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。