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

今天药忘吃喽~ 2023-01-08 13:24 119阅读 0赞

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

### 二的幂 ###

#### 问题 ####

判断一个数字是否是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=5*2，对于一个n！的数字而言，末尾为0的数字即n！的约数中包含的5*2的次数，因为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为删除后的节点编号
 *  \- 关系：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和计算机基础知识，保证让你看完有所收获，不信你打我
 *  求一键三连：点赞、转发、在看。
 *  如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。

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

![image][] image

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

[image]: /images/20221119/72514feb3bf542ffa5fff182b2ce9a9b.png