当前位置:首页 > 高性能开发 > 数据结构与算法

解决一路leetcode算法题的曲折过程及引发的思考

优良自学吧提供解决一路leetcode算法题的曲折过程及引发的思考,解决一道leetcode算法题的曲折过程及引发的思考第一次在leetcode解算法题,想来个开门红,先挑选一道简单的题目AC了再说。leetcode对每道题都有一个难度提示,分别是easy,medium,hard 于是在第一页中看到了几道标着easy的题目,突然看到一道easy题目的通过率只有 18.6%,也是挺

解决一道leetcode算法题的曲折过程及引发的思考

第一次在leetcode解算法题,想来个开门红,先挑选一道简单的题目AC了再说。leetcode对每道题都有一个难度提示,分别是easy,medium,hard

于是在第一页中看到了几道标着easy的题目,突然看到一道easy题目的通过率只有 18.6%,也是挺低的,在好奇心的驱使下点了进去。

题目的大概意思是:

  给定一个数值n,算出从0到n之间有多少个数是质数

这种题目的通过率只有18.6%?看到题目后我就觉得太简单了,明显是水题啊,于是着手做了起来,结果历经曲折,以下是我的四次尝试过程……

examination questions


 

Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n

 

Please use the following function to solve the problem:

int countPrimes(int n){

}


 

第一次尝试解决:

我的思路:先了解质数的判断定义:除了1和它本身外,不能被其他自然数整除。从这个判断定义上来看,用编程实现很简单。于是……

转换成编程思想:

The first step:给定一个n,对于大于2的数,从2开始,通过for循环,依次判断是否为质数,直到n-1

the second step:对每个要判断是否为质数的数,再进行从2到(自身-1)直接的数进行for循环遍历检查,一旦发现可以被某个数整除,则跳出,该数不是质数,进行下一个数的检查。

代码实现:

#include <stdio.h>

int countPrimes(int n) {
    if (n == 0 || n == 1 || n == 2){
        printf("0\n");
        return 0;
    }
    int temp = 0;
    int flag = 0;
    for (int i = 2; i < n; i++){
        for (int j = 2; j < i; j++){
            if (i%j == 0){
                flag = 1;
                break;
            }
        }
        if (flag == 0){
            temp++;
        }
        else{
            flag = 0;
        }
    }

    printf("%d\n",temp);
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    countPrimes(n);

    return 0;
}

自己找了几个值测试了一下

测试如下:

输入54 正确结果是16

结果正确

输入174 正确结果是 40

结果正确

 

都正确,这么简单的题?

于是赶紧去提交答案

结果显示:

 

失败!

用的时间太长了,测试值是49969

于是我用49969测试了一下,结果用了40秒才运算完成,这也太久了,肯定通不过,想到之前看到的通过率,我想我大概知道这道题其实没那么简单,leetcode也不可能水。

 

 

第二次尝试解决:

我知道那个for循环,如果数值非常大的话,那个运算量会很大,而且测试了很多不可能的值,比如 n = 40,他不可能被 大于 40/2 ~ 40之间的数整除吧,也就是从21到40之间的数值可以直接去掉,不用计算了,然后我就去掉这一部分,代码修改如下:

for (int j = 2; j < i; j++){
            if (i%j == 0){
                flag = 1;
                break;
            }
}

改成:

for (int j = 2; j < i/2; j++){ 
            if (i%j == 0){
                flag = 1;
                break;
            }
}

 

完整代码:

#include <stdio.h>

int countPrimes(int n) {
    if (n == 0 || n == 1 || n == 2){
        printf("0\n");
        return 0;
    }
    int temp = 0;
    int flag = 0;
    for (int i = 2; i < n; i++){
        for (int j = 2; j < i/2; j++){
            if (i%j == 0){
                flag = 1;
                break;
            }
        }
        if (flag == 0){
            temp++;
        }
        else{
            flag = 0;
        }
    }

    printf("%d\n",temp);
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    countPrimes(n);

    return 0;
}

提交答案:

 

失败!

自己用49969这个值测试了一下,结果用时24秒

好吧,虽然是比之前40秒少了不少,但是时间还是太长了啊

 

 

第三次尝试解决:

通过第二次尝试解决联想一下,上面的情况是把n除以2之后,把后面一大部分去去掉(比如40/2 = 20 ,然后去掉20~40之间的数,不检查),那么除以3,除以4呢,是否可以以此类推?

通过运算验证,这个算法思路是正确的

那么从2开始,如果不能被整除,然后去掉后面1-1/2部分(对于40来说,就是20~40部分,大约20个数)

再从3开始,然后去掉后面1-1/3部分(对40来说,就是13~40部分,结合上面一步,本次省略了 13~20,也就是大约7个数)

在从4开始……

如此一来,这样就可以减少了大量的不必要的测试项了!

做法:引入变量t = 1,每检查一次,t = t+1,然后 i = j / i

int t;
    for (int i = 2; i < n; i++){
        t = 1;
        for (int j = 2; j < i/t; j++){
            if (i%j == 0){
                flag = 1;
                break;
            }
            t++;
        }
        if (flag == 0){
            temp++;
        }
        else{
            flag = 0;
        }
    }

完整代码:

#include <stdio.h>

int countPrimes(int n) {
    if (n == 0 || n == 1 || n == 2){
        printf("0\n");
        return 0;
    }
    int temp = 0;
    int flag = 0;
    int t;
    for (int i = 2; i < n; i++){
        t = 1;
        for (int j = 2; j < i/t; j++){
            if (i%j == 0){
                flag = 1;
                break;
            }
            t++;
        }
        if (flag == 0){
            temp++;
        }
        else{
            flag = 0;
        }
    }

    printf("%d\n",temp);
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    countPrimes(n);

    return 0;
}

测试了 49969这个值,结果很快就出来,不到1秒钟!

这下可以通过了吧,应该可以AC了

提交一下:

失败!

怎么回事!这也不行!这leetcode的要求这么高?难道它的时间要求设置为0.1秒这样的级别?!

这次提示是 1500000 这个值测试不得通过,时间还是太长了。居然拿这么大的值来测试!

本机测试了一下,用时大约2秒(光标闪了两下的时间)就出来了,不过对于严格的leetcode来说,时间还是太长了。

 

 

第四次尝试解决:

我意识到这个问题不能用上面的算法来解决,因为这个算法对于那个 质数的判断定义 来说,感觉已经是最优算法了。只能重新设计算法,于是把代码全部删了,重新再来!

拿起草稿纸,好好思考一下如何解决,思考存在什么更好的方法以及规律,思考发现了一些规律如下:

比如18,它能被2,3,6,9 整除,而6又能被2整除,所以在检测到被6整除之前,肯定已经检查到可以被2整除了,已经break了,所以我发现,凡是2的倍数,只要用2来判断就好了,也就是说2代表了所有的双数。同样的,3也是,有了3,就不用9来检查了,能被9整除的肯定能被3整除。

于是我们来观察下面一组数字:

2,3,4,5,6,7,8,9,10,11

2符合要求

3符合要求

4由于是2的倍数,所以不符合要求

5符合要求

6由于是2的倍数,所以不符合要求

7符合要求

8由于是2的倍数,所以不符合要求

9由于是3的倍数,所以不符合要求

10由于是2的倍数,所以不符合要求

11符合要求

我们可以发现,符合要求的都是质数(关于用数学来证明这个结论,不是讨论的重点)

也就是说,我们仅仅需要检测一个数是否能被比它小的质数整除,如果可以,说明它不是质数,如果都不可以,说明他是质数

转换成编程思想:

  用一个数组arr来存放这些质数,先给定arr[0] 为2,初始化,再用2来判断下一个值是否是质数,如果是,那么arr[1] == 该质数,再检查下一个数,检查是否可以被arr[0] 和 arr[1] 整除,以此类推

 

分析:下面代码定义的数组长度为200,不用太大,因为第200个质数的值是1223,那么它的平方是:1495729,对于n = 1500000来说,绰绰有余了

当然,为了保守起见,这个值可以设置大一点。

为了提高运算速度,这里限制了作为基数的质数个数为200个,超过200个部分,不进行运算,因为也没必要。

if (flag == false){
            if (k < 199){
                k++;
                arr[k] = i;
            }
            temp++;
}

代码实现:

#include <stdio.h>

int countPrimes(int n) {
    if (n == 0 || n == 1 || n == 2){
        return 0;
    }
    if (n == 3){
        return 1;
    }

    int temp = 0;
    bool flag = false;
    int arr[200] = { '\0' };
    int k = 0;
    arr[0] = 2;

    for (int i = 3; i < n; i++){
        for (int j = 0; j <= k; j++){
            if (i%arr[j] == 0){
                flag = true;
                break;
            }
        }

        if (flag == false){
            if (k < 199){
                k++;
                arr[k] = i;
            }
            temp++;
        }
        else{
            flag = false;
        }
    }

    return temp+1;
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n",countPrimes(n));

    return 0;
}

 

用时大约0.1秒,这下应该可以通过了。

提交一下:

成功!

终于通过了!还记得当初认为它是水题吗?看来通过率低原来是这么来的……

 

 

引发的思考:

从运行时间上来看本题的运算提升过程: 40秒 --> 24秒 --> 1.5秒 --> 0.1秒

01.秒 与 40秒的差距是400倍,一个好的算法和解决方案,可以节省400倍的时间!

在我们平时做项目或者为了完成某些功能达到某个结果的时候,也许仅仅是为了达到而达到,结果正确就ok,但是很多时候,这种情况下可能仅仅满足自己的要求或者是小范围内符合要求,在很广的面上来看,很有可能完全不能用。

比如数据库设计,设计得好的,很快就可以查询到所要的数据。设计不好的,在短期内可能发现不了什么问题,但是到了数据庞大的时候,也许就没有实用性。有前辈跟我讲过,他有个项目是交水电费系统,测试的区域是一个小镇,查询速度不错。后来推广了,范围扩大到一个市,结果查询某一家的水电费情况,居然用了5分钟才查出来,明显是没有做到合理的设计。

那么,如何从一开始就做到尽量防止存在后顾之忧呢?我思考如下:

第一,要对问题的本质有非常明确的了解,不能只知其一不知其二。比如上面我的解题过程,仅仅知道质数的判断定义,并没有对里面存在的规律进行深入了解,造成了解题失败。

第二,在解决问题之前,尽可能的思考多种解法方案,记录下来,分析各种方案在时间效率,空间使用度的优劣。再选上符合要求的最好的方案去实施。切忌想到一个方法,它可以解决问题,但是很有可能不是最优方法,但是为了快速解决问题而拒绝思考,最后可能会照成不必要麻烦。(重写代码,代价更高),这个道理可能大家都懂,但是很少人真正有这样去做一件事情。

第三,学会站在巨人的肩膀上。本次解题,由于想要锻炼自己的思维和练习手感,所以要求自己一定要独立完成。但是在我们平时解决问题中,要学会借力。很多前人研究过的方法,他也许用了好长的时间才研究出来的从目前看最优的方法,那么我们学习他的方法,理解他的思维,用他的方法这样我们可以快速解决问题,同时也把知识化为自己的,这样效率最高,所以不要固执,学会使用google,让自己站在巨人的肩膀上前行,收获会是最大的。

 

3楼March On
perfect
2楼stevenczp
贴一下我的代码, leetcode上95ms AC,,用的是筛法,,int countPrimes(int n) {,bool* map = (bool*)malloc(n * sizeof(bool));,memset(map, 0, n * sizeof(bool));,,for (int i = 2; i lt;= sqrt(n); i++),{,if (map[i]),continue;,int t = 2 * i;,while (t lt; n),{,map[t] = true;,t += i;
1楼之奇一昂
学习了,顶一下

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢