2016-01-21

leetcode-319的算法思考

题目

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3.

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].

So you should return 1, because there is only one bulb is on.

题目含义

就是说给n个开关分别对应控制这n个灯泡的亮灭，步骤如下:

开始时开关都是关的，为方便叙述，位置从1开始
step=1,将所有位置的开关打开
step=2,将所有位置为2的倍数的开关转换状态
…
step=n,转换完开关后,统计还有多少灯泡开者

解法

1.直观解法

思路

分析完题目后,首先想到的就是把开关这些控制流程自己模拟
一遍，用布尔数组模拟开关，最后统计为true的开关数就可以
了。

那就开始写吧，leetcode支持c/c++，感觉够了，至于能不能
用STL库还不清楚，自己动手写一些常用数据结构，虽说性能有
损失，但是为了AC,也只能自己注意性能了，尽量不要手动分配
大的数组。

int bulbswitcher(int n){
    //c99支持的关键字_Bool,ansi不支持,leetcode测试通过
    _Bool *p=(_Bool *)malloc(sizeof(_Bool)*n);
    if(p==NULL){
        exit(-1);
    }
    //全为false,避免求反时未定义
    memset(p,0,sizeof(_Bool)*n);
    
    for(j=0;j<n;++j){           //step 1->n
        for(i=j;i<n;i+=j+1){    //对应的开关,每次跳跃的间隔j+1
            *(p+i)=!(*(p+i));   //不知道编译器是否会优化，所以采用这种直接寻址方式
        }
    }
    
    //统计为true的开关,如果有c++的accumulate更好
    sum(p,n);
}

上传到leetcode jude,不一会儿出现了Limit except，发现它的测试数是10000000,
总用时1+s,这么大数字居然超时了.我自己在线下测试的结果：

普通编译:
开启-O2 优化

可以发现这种算法复杂度O(n^2),数字一大性能就不行了。普通编译结果也是超过1s,看来leetcode没有做优化,并且超时时间设置1s,
如此只能再想其他解法.

2.进阶方案

总觉得这样转换的状像是符合某种数学规律，也许是常年的理工教育培养了这种直觉，
我就试一试究竟有没有规律,基于现有代码很好改动。

void test(int max){
    for(int i=0;i<max;++i){
        printf("%3d:%3d\n",i,bulbswitcher(i));
    }
}

打印结果:
leetcode-3

居然有这么多一样的，看起来像台阶一样，必须满足某种条件才能增加一级.
那我再改进一下试探方法,为了一查究竟这么多相同的数字有什么关系，以及开关
数n和最后结果的关系，采用哈希表去做，c没有，其实开个大数组也行，我这里用
的是Go。

func test(n int){
    m:=make(map[int]int,n)
    for i:=0;i<1000;i++{
        m[bulbswitcher(i)]++
    }
    
    //无序表，对key排序    
    sort.SortInts(map_keys)
    for _,k:=range map_keys{
        fmt.Printf("%3d:%3d\n",k,m[k])
    }
}

运行结果:
leetcode-4

果然有关系!原来最后的结果对应的原始开关数n是一个奇数等差数列:

第i级,ret表示n在这一级内，则最终的结果
cnt表示有多少个n是对应ret这个结果的，也就是n的范围
关系如下:
       2*ret+1 = cnt 
=>     ret = (cnt-1)/2

现在我们只要求出这个范围cnt就行了。由于k对应的最后的结果，而v对应n,表明我们需要判断这个n落在哪一级内，
也就是将v加起来，直到加到第i级超过n的值，那么n就是在这一级内。
基于这种思想有代码:

int magic(int n){
    if(n<=0){
        return 0;
    }
    int i,cnt=0;
    for(i=3;cnt<n;i+=2){ //第i级所包含的原始开关数范围,cnt统计n之前的数量
        cnt+=i;
    }
    return (i-3)>>1;//因为数列没有cnt=1对应的ret
}

改进之后算法复杂度为O(n/2)=>O(n)，现在上传改进的代码,这次通过了，耗时0s,但是在分布图里，
居然只打败了同样用C的6.83%,看来很多人结果比我好啊，也不知道
它的测试数字是不是都是一样的。

看一下能不能继续改进。对了，奇数等差数列不是有求和公式吗?我们知道n，直接求它在那一级的范围
内，不就是ret的值么?避免了一个个去加然后判断,这就是最终版本的方法。

3.最终解法

因为奇数2n-1的求和公式:

对于上面的关系有:

         sum = (2*ret+1+3)*ret/2
     =>      =  ret*ret + 2*ret

所以反推有:     
     ->    n <= ret*ret
     =>   ret = sqrt(n) 向下取整

这种解法C函数表示就是floor(sqrt(n))
所以改进的代码:

int final_magic(int n){
    if(n<=0){
        return 0;
    }
    return floor(sqrt(n));//隐式转型
}

这样简单多了。然后上传leetcode测试结果,35个测试全部通过，
耗时0ms，居然还是打败6.88%,郁闷

4.三种解法的单元、性能测试

为了测试的方便，我将代码改写成go，然后使用自带test，之前2方案
比较快，所以以它为基准测试其他2种正确性。开始的时候都是手写的测试
case,用map去对比,本想设置测试上限10000000，但是超过了10分钟，出
现了panic，10万以上第一种方法就很慢了。
测试代码部分:

const(
    MAX = 10000   //测试范围
)

//通用测试方法，传入测试函数参数
func test(t *testing.T,Func func(int) int){
    for i:=0;i<=MAX;i++{
        if Func(i)!=Magic(i){
            //结果出错
            t.Errorf("%3d:%3d calc failed.",i,Func(i))
        }
    }
} 

TestCommon(t){
    test(t,Common)
}

TestFinalMagic(t)

性能测试，代码类似:

//通用性能测试方法
func bench(b *testing.B,Func func(int) int){
    for i:=0;i<=MAX;i++{
        Func(i)
    }
}

BenchmarkCommon(b)
BenchmarkMagic(b)
BenchmarFinalkMagic(b)

测试结果:
leetcode-5

总结

第一种最符合程序员解决问题的思维，也很容易理解。后面的方法已经脱离了问题，变成了纯粹的数学问题
无奈第一种性能要差得多。这大概就是提醒我们，抽象生活问题成数学问题，然后去解决它吧。很惭愧，我
没有通过分析问题去提炼其中的数学规律，而是凭感觉试出来的，
最后，学到的是go中的函数参数了，顺便复习了C语言的一些内容。