算法：一行代码解决的算法题

超、凢脫俗 2023-07-10 08:56 39阅读 0赞

一、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 + 1

m + 2  
…  
n  
…

进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]  
新的环中只有 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 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：

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

![在这里插入图片描述][20200301202236673.png]

通过这种方法，可以把空间复杂度降低到 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);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301201813912.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[20200301202236673.png]: https://img-blog.csdnimg.cn/20200301202236673.png