算法学习：二进制的神奇用途

terry 2年前 (2023-09-27) 阅读数 62 #数据结构与算法

世界上有10种人，一种懂二进制，一种不懂。如果你懂笑话的话，这篇文章就是给你看的

单数

leetcode 有这么一道题，单数。问题是找到数组中唯一存在的数字。，其他数字显示两次。这个问题很简单。我们可以使用哈希表来存储所有数字的时间，然后找到幂为 1 的数字。使用二进制代码解决此问题会快得多。

二进制解决方案

二进制文件有一个称为按位异或的运算符。它的作用是如果两个位数相同则为0，如果不同则为1，即1^1=0, 0^0=0, 1^0=1, 0^1=1 ；

通过该运算符的性质，我们知道，任意一个数与其位进行异或，结果都是00000000，而任意数进行异或，结果就是00000000。你得到的只是这个数字。且A^B^C=C^B^A，该算子满足交换律。我们来看一个简单的js解决方案：


/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    return nums.reduce((res, cur) => res ^ cur);
};

复制代码

毒药问题

有8个相同的瓶子，其中7个是白水，一个是毒药。任何喝下这种毒药的生物都会在一周内死亡。现在你一周只有3只老鼠，你如何识别哪个瓶子里装着毒药？

解决方案理念

我们使用二进制代码对每个水瓶进行编号。数字为000,001,010,011,100,101,110,111分别对应瓶子1-8。然后让第一只老鼠喝第一个 1，第二只老鼠喝第二个 1，第三只老鼠喝第三个 1。假设第四瓶水有毒，那就说明011有毒

第一只老鼠喝了100,101,110,111，结果：没有死亡，记为0
第二只老鼠喝了010,011,110,111，结果：死了，记录为1♷ 第三只老鼠喝了001,011,101,111，结果：死了，记录为1

第四瓶水，根据死亡结果，恰好是011，难道只是巧合？恐怕不是。我们可以用数学思维来证明这个问题

证明

任意老鼠喝毒药会死还是不会死。一只老鼠可以检查两瓶药有毒，即2^1，两只老鼠可以检查2^2瓶药，三只老鼠可以检查2^3。一瓶药，那怎么试药呢

我们让每只老鼠喝下一定数量的所有药，如果老鼠死了，就说明一定数量的毒药是1。 first 如果老鼠喝了所有第一个数字为 1 的毒药，并且死亡，则表示第一个毒药的编号为 1。如果没有死，则表示第一个毒药的编号为 0
如果这里没有三只老鼠死亡，则意味着毒药的三个数字都为0，这恰好是三只老鼠都没有喝下的第一瓶。

延伸问题

有1000个一模一样的瓶子，其中999个是普通水，一瓶是毒药。任何喝下这种毒药的生物都会在一周内死亡。现在你只有10只老鼠，一周时间，你如何识别哪一瓶有毒？

根据上面的问题，我们可以知道2^10 = 1024 > 1000，我们还可以通过对每个瓶子进行二进制编号来检查哪个瓶子有毒。

问题升级

现在有一个有趣的问题：如果你有两周的时间，你至少需要多少只老鼠才能在1000个瓶子里找到毒药？请注意，在第一轮测试中死亡的小鼠不能继续参加第二轮测试。拓展问题的思路。三种情况，第一轮是死的，第二轮是死的，第二轮是活的，上题中的老鼠有两种情况并且使用的是二元制，那么很明显我们必须使用三元制这个问题。 3^6 = 729, 3^7 = 2187，显然我们至少需要7只老鼠。

如何喂药

还是和以前一样。第一轮，我们让每只老鼠喝下2号药。如果老鼠死了，就意味着中毒了。数字是2。当所有的老鼠都死了的时候，我们就连第二轮都不需要了，直接把毒药数量设置为2222222就可以了。
如果第二轮还剩下很多老鼠，那就意味着如何许多毒药的编号为0或1。我们还剩下k只老鼠，需要确认k位二进制数，因为这些数字被排除在第二种可能性之外。既然回到了上一个问题，我们可以继续使用上一轮的喂食方法。