求出1的个数

求出1的个数 原题目, 题定一十题制个数N～下写从1题始～到N的所有整～然后一下其中出题的所有数数"1"的。个数 例如, N=2～下写1～2。题题只出题了1个"1" N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。题题"1"的是个数5 题出一函～返回写个数1到N之题出题"1"的～比如 个数f(12)=5 1package org.blogjava.arithmetic; 2 3/** 4 * @author Jack.Wang 5 * @see 6 */ 7public class CountNumber { 8 9 private int count1Num(int num) { 10 int sum = 0; 11 while (num != 0) { 12 sum += (num % 10 == 1) ? 1 : 0; 13 num /= 10;14 } 15 return sum; 16 } 17 18 private int countNum(int n) { 19 int sum = 0; 20 for (int i = 1; i <= n; i++) { 21 sum += count1Num(i);22 } 23 return sum; 24 } 25 26 private int countNumNew(int n) { 27 int count = 0; 28 int factor = 1; 29 int lower; 30 int current; 31 int higher; 32 while (n / factor != 0) { 33 lower = n - (n / factor) * factor;34 current = (n / factor) % 10;35 higher = n / (factor * 10);36 switch (current) { 37 case 0: 38 count += higher * factor;39 break; 40 case 1: 41 count += higher * factor + lower + 1; 42 break; 43 default: 44 count += (higher + 1) * factor;45 } 46 factor *= 10; 47 } 48 return count; 49 } 50 51 /** 52 * @param args 53 */ 54 public static void main(String[] args) { 55 System.out.println("两个算法的题果相等"); 56 /** 57 * 方法一, 题题题看上出不是一题题题～因题不需要太多的思考～只要稍点程序个并个懂 的人都想到～题题的题题如下。会 58 * 题方法题题但是题算法的致命题题是效率～的题题题题度个很个它 是 O(N)*count(int num)函的题题度数= 59 * O(N)*logN。可题如果N很从大题题题度成题性增题。是否题有更好的方法～我题的是算法题题的角度考题最题的方法, 题看方法二。 60 */ 61 long start = System.currentTimeMillis();62 CountNumber cn1 = new CountNumber(); 63 System.out.println("第一算法的题果个"+cn1.countNum(100000000));64 long end = System.currentTimeMillis();65 long time1 = end - start; 66 /** 67 * 方法二, 题题方法分题分析N的每一位上1出题的可能性～题者可以自己按照题题的思想分析一下～最题得出你会 68 * 一题题～就是通题分析个N而不是遍题1到N的每一就可以得出答案～如果个数N的题度题Len的题题题 算法的题题度题O (Len)。 题题题律题 69 * 1. 如果位上题数0～1的目由题位以上的定～乘以题位的分位数数决并 比如百位上是0～高位上是14题百位上出题1的目数 题 14*100。 70 * 2. 如果位上题数1～1的目由高位和低位共同定。数决 比如高位是14低位是112～题百位出题1的目题数 14×100+;112+ 1, 71 * 3. 如果位上大于数1～题百位出题1的目题数 ;14+1,×10072 */ 73 start = System.currentTimeMillis();74 CountNumber cn2 = new CountNumber(); 75 System.out.println("第二算法的题果个"+cn2.countNumNew(100000000)); 76 end = System.currentTimeMillis();77 long time2 = end - start; 78 System.out.println("第一算法的题延比第二算法的多个个" + (time1 - time2) / 1000 + "秒"); 79 } 80 81 /** 82 Console Out: 83 两个算法的题果相等 84 80000001 85 80000001 86 第一算法的题延比第二算法的多个个27秒 87 */ 88}