思维私塾——一行代码解决算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了思维私塾——一行代码解决算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3595字，纯文字阅读大概需要6分钟。

内容图文

有些算法题目，只要掌握了思路就可以用很短的代码来实现它。比如下面这几道题目：

二的幂

问题

判断一个数字是否是2的n次方

解答

遇到2的幂次方，要建立位移操作的思想，如果n是二的幂，即最高位为1其他位置为0，那么n-1就是最高位为0，其余位置为1，那么n&(n-1)就是0

1boolean?isPowerOfTow(int?n){
2????return?(n>0)%%(n&(n-1))==0;
3}

三的幂

问题

判断一个数字是否为3的n次方

解答

int类型中不溢出情况下3的最高次方即为1162261467，那么只要这个数去约n为0，那么说明n的约数只有三，即为3的n次方.

同样的做法也可以适用于5的幂,7的幂,X的幂（X是一个素数）之类的题目。

1boolean?isPowerOfThree(int?n){
2????return?(n>0)&&(116261467%n)==0;
3}

二进制1的个数

问题

给定一个数字n，求n转换为二进制表示中1的个数

解答

JDK大法好，直接使用自带的方法：

• bitCount：返回二进制中1的个数
• lowestOneBit：返回二进制表示中最低位1的位置
• highestOneBit：返回二进制表示中最高位1的位置
• numberOfLeadingZeros：返回二进制表示中高位0的数目
• numberOfTrailingZeros：返回二进制表示中低位0的数目

1?int?bitCount(int?num)?{
2????????return?Integer.bitCount(num);
3????}

或者也可以不使用jdk类库的解法

1int?bitOfOne(int?num)?{
2????????return?num?==?0???0?:?1?+?bitOfOne(num?&?(num?-?1));
3????}

阶乘后的零

问题

给定一个数字n，求n！位数中的0的个数。

解答

这种问题我们要分析0的产生原因，因为10=52，对于一个n！的数字而言，末尾为0的数字即n！的约数中包含的52的次数，因为2的次数是足够的，也就是说这道题等价于求n！中约数5的个数（注意诸如25这种数字，约数中包括了2个5）。

1int?zeroAtTheEndCount(int?num)?{
2????????return?num?/?5?+?zeroAtTheEndCount(num?/?5);
3????}

熄灭的灯

问题

有x个灯，一个开关控制一个灯，按下开关会使灯熄灭或者打开，现在灯都是熄灭的状态，我们进行n次操作，每次操作都把编号为i的倍数的开关全部按下，即

• 将编号为1的倍数的开关全部按下
• 将编号为2的倍数的开关全部按下
• …
• 将编号为x的倍数的开关全部按下

已知灯的总数为x，求最后灯亮起来状态的数量

解答

首先任意取灯的编号n，会有几次操作会影响这个灯的状态呢？答案是n的所有约数的个数次。

好比说编号为12的灯，12的约数有1，2，3，4，6，12。也就是说编号为12的灯的状态会被切换6次，分别在第1，2，3，4，6，12次切换开关的时候。

那么从下面2种情况考虑：

• 假设n是一个非完全平方的数：因为为一个非平方的数的约数个数为偶数个，也就是说会切换偶数次状态，也就是说状态不会变。
• 假设n是一个完全平方数：完全平方数的约数是奇数个，其状态会发生改变。

那么按照题目的要求，一开始全是熄灭状态的，求亮起来状态的灯数目，就是说求会发生变化的编号的数目，也就是相当于求1～x之间完全平方数的个数。

1int?lightCount(int?num)?{
2????????return?(int)?Math.sqrt(num);
3????}

奇怪的数

问题

给定一个非空数组，其中除了一个元素只出现一次外，其他元素都出现了两次，求这个只出现一次的元素

解答

这里的一个关键运算符是^ 异或运算符，主要是利用到了异或运算a^b满足的如下规律：

• a^b=b^a 交换律
• a^b^c=a^(b^c)结合律
• a^a=0,同时0^0=0
• 0^a=a

1int?loseNumber(int[]?num)?{
2????????return?Arrays.stream(num).reduce(0,?(n1,?n2)?->?n1?^?n2);
3????}

约瑟夫环问题

问题

编号为1-n的n个战士围成一圈，从编号1的战士开始依次报数，数到m的战士会淘汰，以后的战士再重新报数，直到剩下一个士兵，求这个士兵的编号

解答

删除前（old）	删除后（new）
m-2	n-2
m-1	n-1
m	无
m+1	1
m+2	2

• 假设old为删除前的节点编号，new为删除后的节点编号

• - 关系：old=(new+m-1)%n+1

注意：并不是old=(new+m)%n，因为编号是从1开始的而不是从0 开始的，如果new+m==n的话，会导致最后的计算结果old=0.

1int?f(int?n,int?m){
2????if(n==1)?
3????????return?n;
4????return?(f(n-1,m)+m-1)%n+1;
5}

最后

• 如果觉得看完有收获，希望能关注一下，顺便给我点个赞，这将会是我更新的最大动力，感谢各位的支持
• 欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我
• 求一键三连：点赞、转发、在看。
• 如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。

——我是冢狐，和你一样热爱编程。

> 欢迎关注公众号“ Java冢狐”，获取最新消息

内容总结

以上是互联网集市为您收集整理的思维私塾——一行代码解决算法全部内容，希望文章能够帮你解决思维私塾——一行代码解决算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---