微软面试题-凯发k8网页登录

java, c , linux c, c#.net 技术,软件架构,领域建模,it 项目管理

 原题目:
 给定一个十进制数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 http://jack2007.blogjava.net/
 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)×100
72         */

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}

89




本博客为学习交流用,凡未注明引用的均为本人作品,转载请注明出处,如有凯发k8网页登录的版权问题请及时通知。由于博客时间仓促,错误之处敬请谅解,有任何意见可给我留言,愿共同学习进步。
posted on 2008-10-16 18:10 jack.wang 阅读(4052) 评论(11)  编辑  收藏 所属分类: 数学&算法
# re: 微软面试题---求出1的个数之小解 2008-10-16 22:07
n=12,写下 1,2,3,4,5,6,7,8,9,10,12。这样"1"的个数是5??  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-16 22:38 jack.wang
@testsssss
不好意思打错了。  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-16 22:43
@testsssss
缺了个11  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 01:14
不好意思,我借用你这道题目在cnblogs上发了一篇blog...  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 10:01
感觉没什么用啊  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 12:36
还有一种方法,就是转成string 然后一个一个字符去匹配就ok  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 14:44
只要将1-n的数字作为字符串叠加在一起,然后用"1"作为分隔符将字符串分割为数组,数组长度减一就是“1的个数”。  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 14:45
当然要先排除只有一个"1"的情况。  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 17:01
@lancelot
你大概以为字符串叠加这算法能达到o(n)复杂度
但实际上这种就是nlogn复杂度的算法。
因为integer向string转换过程中有logn的复杂度。
对每项数字都转换,那总共就有nlogn的复杂度。
如果你还想把数字都叠一起算,那么你的空间开销都将由原来的logn达到 nlogn  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-17 17:48
def f n
result=0
n.times do |i|
result=result (i.to_s).count('1')
end
return result
end

f 12
12
f 1200
640
当然速度是慢,可是工作中在你研究复杂度时我已经完成开发开始新的模块了  回复  
  

# re: 微软面试题---求出1的个数之小解 2008-10-20 13:44
@lvcha
这样很无聊啊~~  回复  
  

网站地图