亲宝软件园·资讯

展开

牛逼!一行代码居然能解决这么多曾经困扰我半天的算法题

帅地 人气:2

春节假期这么长,干啥最好?当然是折腾一些算法题了,下面给大家讲几道一行代码就能解决的算法题,当然,我相信这些算法题你都做过,不过就算做过,也是可以看一看滴,毕竟,你当初大概率不是一行代码解决的。

学会了一行代码解决,以后遇到面试官问起的话,就可以装逼了。

一、2 的幂次方

问题描述:判断一个整数 n 是否为 2 的幂次方

对于这道题,常规操作是不断这把这个数除以 2,然后判断是否有余数,直到 n 被整除成 1 。

我们可以把 n 拆成二进制看待处理的,如果 n 是 2 的幂次方的话,那么 n 的二进制数的最高位是 1,后面的都是 0,例如对于 16 这个数,它的二进制表示为 10000。

如果我们把它减 1,则会导致最高位变成 0,其余全部变成 1,例如 10000 - 1 = 01111。

然后我们把 n 和 (n - 1)进行与操作,结果就会是 0,例如(假设 n 是 16)

n & (n-1) = 10000 & (10000 - 1) = 10000 & 01111 = 0

也就是说,n 如果是 2 的幂次方,则 n & (n-1) 的结果是 0,否则就不是,所以代码如下

int isPow(n){
    return (n & (n - 1)) == 0;
}

二、一行代码搞定经典的约瑟夫环

约瑟夫环问题,我相信大家在大一大二的时候就接触过了,很多人也都会拿来作为环形链表的一个应用,然而环形链表并非最优的解决方法,今天我就用一行代码干掉它,并且几乎算是最优解了。

鉴于有些人把这道题忘了,我还是把这道题的描述贴出来一下吧

问题描述:编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈,从编号为 1 的士兵开始依次报数(1,2,3…这样依次报),数到 m 的 士兵会被杀死出列,之后的士兵再从 1 开始报数。直到最后剩下一士兵,求这个士兵的编号。

先给出代码,后面在解释。

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

原理是这样的:

如果我们把士兵删除后,重新给这些士兵编号的话,那么删除前和删除后,这些编号存在某种数学关系,我们只需要找出这个关系即可。

我们定义递归函数 f(n,m) 的返回结果是存活士兵的编号,显然当 n = 1 时,f(n, m) = 1。假如我们能够找出 f(n,m) 和 f(n-1,m) 之间的关系的话,我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为


1

m - 2

m - 1

m

m + 1

m + 2

n

进行了一次删除之后,删除了编号为 m 的节点。删除之后,就只剩下 n - 1 个节点了,删除前和删除之后的编号转换关系为:

删除前 --- 删除后

… --- …

m - 2 --- n - 2

m - 1 --- n - 1

m ---- 无(因为编号被删除了)

m + 1 --- 1(因为下次就从这里报数了)

m + 2 ---- 2

… ---- …

新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1, 2, 3 的节点。

假设 old 为删除之前的节点编号, new 为删除了一个节点之后的编号,则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

这样,我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了,而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下:

注:有些人可能会疑惑为什么不是 old = (new + m ) % n 呢?主要是因为编号是从 1 开始的,而不是从 0 开始的。如果 new + m == n的话,会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}

怎么不是一行而是两行?如果你经常刷题,那肯定希望自己的代码看起来越短越简介越好,至于会不会变的更难理解?我懒的理,所以代码如下

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

当然,我之前写过一篇文章,用了三种方法来解决约瑟夫环,感兴趣的也可以看:记一道阿里笔试题:我是如何用一行代码解决约瑟夫环问题的

只出现一次是数

问题描述:给你一个整型数组,数组中有一个数只出现过一次,其他数都出现了两次,求这个只出现了一次的数。

这道题可能很多人会用一个哈希表来存储,每次存储的时候,记录 某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为 O(n),空间复杂度也为 O(n)了。

然而这道题其实可以采用异或运算来解决,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,并且异或运算支持交换律,基于这个特点,我们只需要把这一组整型全部异或一下,最后的结果就是我们要找的数了。

例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下:

由于异或支持交换律和结合律,所以:

1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。

通过这种方法,可以把空间复杂度降低到 O(1),而时间复杂度不变,相应的代码如下

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

说好的一行代码的呢?

这不是为了先让你看的懂吗?一行代码解决方案如下:

// 例如使用这个函数的时候,我们最开始传给 i 的值是 1,传给 result 的是 arr[0]
//例如 find(arr, 1, arr[0])
int find(int[] arr,int i, int result){
    return arr.length <= i ? result : find(arr, i + 1, result ^ arr[i]);
}

实不相瞒,这道题用了一行代码之后,更加复杂 + 难懂了,,,,,,不好意思,我错了,不该把简单的问题搞复杂了再扔给面试题的。

四、n 的阶乘

问题描述:给定一个整数 N,那么 N 的阶乘 N! 末尾有多少个 0?例如: N = 10,则 N!= 3628800,那么 N! 的末尾有两个0。

我先给出个代码让大家品尝一下,在细细讲解

int f(n){
    return n == 0 ? 0 : n / 5 + f(n / 5);
}

对于这道题,常规操作是直接算 N!的值再来除以 10 判断多少个 0 ,然而这样肯定会出现溢出问题,并且时间复杂度还大,我们不妨从另一个思路下手:一个数乘以 10 就一定会在末尾产生一个零,那么,我们是否可以从哪些数相乘能够得到 10 入手呢?

答是可以的,并且只有 2 * 5 才会产生 10。

注意,4 * 5 = 20 也能产生 0 啊,不过我们也可以把 20 进行分解啊,20 = 10 * 2。

于是,问题转化为 N! 种能够分解成多少对 2*5,再一步分析会发现,在 N!中能够被 2 整除的数一定比能够被 5 整除的数多,于是问题近似转化为求 1…n 这 n 个数中能够被 5 整除的数有多少个,

注意,像 25 能够被 5整除两次,所以25是能够产生 2 对 2 * 5滴。有了这个思路,代码如下:

int f(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int j = i;
        while(j % 5 == 0){
            sum++;
            j = j / 5;
        }
    }
    return sum;
}

然而进一步拆解,我们发现

当 N = 20 时,1~20 可以产生几个 5 ?答是 4 个,此时有 N / 5 = 4。

当 N = 24 时,1~24 可以产生几个 5 ?答是 4 个,此时有 N / 5 = 4。

当 N = 25 时,1~25 可以产生几个 5?答是 6 个,主要是因为 25 贡献了两个 5,此时有 N / 5 + N / 5^2 = 6。

可以发现 产生 5 的个数为 sum = N/5 + N/5^2 + N/5^3+….

于是,一行代码就可以搞定它了

int f(n){
    return n == 0 ? 0 : n / 5 + f(n / 5);
}

总结

有木觉得很牛逼?以后面试官问你这些题,你就把这行代码扔给他!!!

当然,想要一直保持牛逼,还得多看一些算法书,我也有整理了一些

在此贡献给大家,都是一些值得看的算法书

大家可以在我的微信公众号『帅地玩编程』获取『我要学算法』获取下载链接。

老铁,要不点个赞再走可好?么么哒

1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

2、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。

保存让你看完有所收获,不信你打我。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书。

作者简洁

作者:大家好,我是帅地,从大学、校招一路走来,深知算法,计算机基础知识的重要性,所以申请了一个微星公众号『帅地玩编程』,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习。 转载说明:未获得授权,禁止转载

加载全部内容

相关教程
猜你喜欢
用户评论