【问题】 有三顶红帽子和两顶白帽子.将其中的三顶帽子分别戴在 A、B、C三人头上.这三人每人都只能看见其他两人头上的帽子,但看不见自己头上戴的帽子,并且也不知道剩余的两顶帽子的颜色。 问A: “你戴的是什么颜色的帽子?” A回答说:“不知道。” 接着，又以同样的问题问B。 B想了想之后，也回答说:“不知道。” 最后问C。 C也想了一会回答说:“我知道我戴的帽子是什么颜色了。” 当然，C是在听了A、B的回答之后而作出回答的。试问:C戴的是什么颜色的帽子? 【回答】 A回答不知道，说明A看到肯定不是两顶白帽，要么是两顶红帽，要么是一白一红； B回答不知道，在他知道自己和C是要么两顶红帽，要么一白一红的前提下，说明C肯定不是白帽子，否则他就知道自己是红色的了。说明C是红帽子！ C根据这一点推断出自己是红帽子！
100枚硬币平放在桌面上，10枚正面朝上，90枚反面朝上，不能看，不能仔细摸，可以移动翻转硬币。请问如何江它们分为正面朝上硬币数目相等的两堆？
方案：将其中10枚硬币移出来，翻个个。
解释 ：加入移出的硬币里有9枚反，1枚正，翻转后就是9正1反，剩下的硬币里是81枚反，9枚正。
——如何避免有的人抢不到，有的人抢的很多，有的人抢的很少？
容易想到的是：随机区间 ( 0, 剩余金额 )，这样会导致先抢的人拿得多。
思路： 假设一共有 N 元，一共有 K 个人，则可以每个人拿到的钱为 random(N - (K - 1) * 0.01)，即保证后面K-1个人至少还有0.01元，然后更新N为剩余的钱，直到最后一个人就直接拿N。
生成随机数的方法：
或者：
——用 0-4 随机数生成器 rand4() 来生成0-6随机数 rand6()
初步印象：乘以四分之六不就行了？——不行！
- rand4()，0-4随机数：0、1、2、3、4共5个数
- rand6()，0-6随机数：0、1、2、3、4、5共7个数
思路：生成一个比6大的数据范围，并且能够确定每个数字出现的概率都相同。
rand4() * rand4() 和 rand4() + rand4() 得到的各个数的概率是不同的！
【n进制计算】 如果对0-4进行排列，得到16个数字，每个数字都是唯一的，说明每个数字出现的概率都是一致的！ 
故而rand4() * 5得到也是随机的 ，rand4() * 5 + rand4()也是随机的。所以可以对其中的0-20进行三等分。 结果： 代码：
两根香，一根烧完1小时，如何测量15分钟 思路：
先将一根香的一端点燃，另一根香的两端全部点燃。当第二根香全部烧完时，此时已经过了半个小时。再将第一根香的另一端也点燃，那么此时第一根香剩下部分烧完的时间就是 15 min。
7.1 topN问题
——如何在很大的数量级的数据中，找出前1000大的数据？ 来源于知乎
（1）数据还不够大的话：分治法
答：如果全部排序一遍的话，或者部分排序的话，时间复杂度就会很高。可以用分治法，比如快排操作。 随便找一个数t，用快排，使得左边的数大于它，右边的数小于它，如果前面一部分总数大于1000个，那么继续在前一部分进行快排查找，否则在后一部分进行查找。如果左边的数量等于1000，那么久找到了。
时间复杂度：O(N) 计算过程：快排的过程，时间是O(n)，第二次减半，O(n/2)，第三次O(n/4)，显然是小于O(2n)的，所以就算作O(n)
——但是这样如果数据量很大，空间复杂度就会很高！
（2）数据超大，2G，怎么办？
可以把快排分出来的两部分数据放在txt文件里，第二次就从文件中读出来进行快排partition，但是这样的磁盘读写效率很低。
——用堆！
在内存中维护一个1000数的小顶堆（每个结点都比它的左右子节点小），小顶堆的根节点是最小的一个数。 即：取前1000个数（设为m），构成小顶堆（O(mlogm)），然后从文件中读取数据(共n个），和堆顶大小相比，如果比堆顶还小，就直接丢弃，如果比堆顶大，就替换堆顶，并且调整小顶堆。所有数据处理完毕后，小顶堆内就是top1000大的数了。（需要所有数据遍历一遍）
复杂度：时间复杂度为O(nmlogm)，空间复杂度是10000（常数）。
这样的话，数据就只需要读取一次，不存在多次读写的问题了。
eg:从1000个数中找出前50个
7.2 寻找最小的前K个数
https://blog.csdn.net/u012485480/article/details/78060752
如果是找到最小的前K个数，则用大顶堆！
——先取k个数构建大顶堆，根节点最大，每次从数据文件中取一个数，如果比堆定小，则用其替换根。然后重建大顶堆。读取完毕后，该堆中的数据为最小的k个数！
在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。
解法：首先假设是32位无符号整数。
- 1.读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。 说明：整数范围是0 - 2^32 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16（4G/256M = 16）种值，每16个值算一段， 0～15是第1段，16～31是第2段，……2^32-16 ～2^32-1是第256M段。一个64位无符号整数最大值是0～8G-1，这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。
- 2.从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的区段，也是中位数所在的区段）的数值范围，设为[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。
- 3.再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。
- 4.对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。
场景题：需求：谁关注了我，我关注了谁，谁与我互相关注。表该如何设计，索引怎么建。查询语句怎么写。 粉丝关注表使用四列，主键id，userId，fansId，是否互相关注。用两行数据来保存互相的关注关系，这样查询起来更方便，用空间换时间。 主键有主键索引，剩下的字段不适合建索引，因为字段重复太多。
——经典博弈论问题 https://www.jianshu.com/p/ec769d3a1e89
有5个海盗，获得了100枚金币，于是他们要商量一个方法来分配金币。商议方式如下： (1) 由5个海盗轮流提出分配方案。 (2) 如果超过半数海盗（包括提出者）同意该方案，则按照该方案分配。 (3) 如果同意该方案的人数（包括提出者）小于等于半数，则提出者要被扔到海里喂鱼，剩下的海盗继续商议分配。 (4) 海盗们都是绝对理性的，以自己尽可能多获得金币为目的。但是在收益相等的情况下，会倾向把提出者扔到海里。
问：第一个海盗应该提出怎样的分配方案，才能保证自己既不被扔到海里，又能使自己利益最大化？ 
直接分析第一个海盗的最优选择，是困难的，可以利用递归思想。 老一：如果我被扔海里，剩下4个，老二的最优方案是啥？我只要给老二多一点，就能赢得支持。 老二：如果我被扔海里，剩下3个，老三的最优方案是啥？我只要给老三多一点，就能赢得支持。 老三：如果我被扔海里，剩下2个，老四的最优方案是啥？我只要给老四多一点，就能赢得支持。
整个递归过程： 
递归到最后两人为止： 老四：没有任何选择的余地，哪怕支持把所有钱都给老五，老五仍然反对（因为同意该方案的人小于等于半数了，提出者要被扔海里），导致老四被扔海里，金币归老五所有。 因此，
- 老三心想：老四没有最优决策，无论我提出什么要求，老四一定会同一，二老五一定不同意。所以他的最优决策是自己独占100枚硬币。
- 老二心想：如果没有我，老三能够获得100枚硬币，所以不会同意我，但是可以设法笼络老四和老五，形成3:1的局面。所以老二给老四老五一人一枚硬币，老三0枚，所以老四老五会同意。自己独占98枚。
- 老一心想：如果么有我，老二能获得98枚，所以干脆笼络剩下三个人中的两个。所以如果给原本只有0枚的老三一枚，老三肯定支持。置于老四和老五，本来可以得到1枚，所以必须比老二给的多。要么给老四两枚金币，放弃老五，要么给老五两枚金币，放弃老四。
如果是七名海盗： 
【题目】：高考成绩2000万数据，分数0-750，如何快速知道你的排名，如何知道任一分数排名？
【思路】：利用桶排序。 将分数分成 0 - 150， 151 - 300， 301 - 450， 451 - 600， 601 - 750 共五个区间（每个区间内还可以再分），将 2000 万分数据按照成绩分到对应的成绩区间中。这样就可以快速查到对应分数的排名了。
——从十亿数据中找到次数是2的数字 + 判断某个数是否在十亿数据中
【问题的提出】：遍历一遍这些数据或者二分查找，时间复杂度是没办法优化到哪里去了，但是10亿数据处理起来，占用的内存可以达到4G——内存不够！
如何用更小的内存来标记一个数字？——bit位 【位图】 如图是一个int占4个字节，32位，本来4个字节只能存一个int，现在利用位图可以存（映射）32个数字。 
https://blog.csdn.net/lucky52529/article/details/90172264
位图法思想： 对于40亿个 unsigned int 的整数，每个数字用1个二进制数（一个二进制数占用1Bit，1Byte = 8Bit）来表示该数字是否存在，0为不存在，1为存在。从低位开始数： 第1个二进制数表示整数0是否存在， 第2个二进制数表示整数1是否存在， 第3个二进制数表示整数2是否存在， 依次类推 … … 第4294967296个二进制数用于表示整数4294967295是否存在。
unsigned int 在32&64位编译器的范围为 0～4294967295，4294967296个二进制数大约占用512M内存，是一个可以接受的范围。
（1）从十亿数据中找出次数为2的数字
思路：先遍历找出最大最小值，从而减小位图中数组的长度。再用位图做。
（2）判断某个数是否在四十亿数据中
https://blog.csdn.net/v123411739/article/details/86652806
（3）判断某个URL是否存在在100亿个URL当中
首先不能用hashMap，因为存储量太大了。 布隆过滤器： —— 可以用于判断某个URL是否位于庞大的黑名单中（屏蔽网友/请求）、过滤垃圾邮件等 介绍：是一个很长的二进制矢量（很长的bit类型数组）和一系列随机映射函数（hash函数）。优点是空间效率和查询时间都很优秀，缺点是有一定的误识别率， 判断过程：假如创建一个bit数组，长度为m，每个元素值是0，有k个哈希函数。当输入一个url的时候，这个URL会经过k个hash函数处理，得到多个哈希值（v1, v2, …, vk），分别除以数组长度m，对m取模，可以得到数组的下标位置，将这些下标的元素都置为1。把这100亿个url都这样操作一遍，之后当输入这个需要判断的URL的时候，如果相应下标的元素值都已经是1了，说明已经在黑名单里面了。 
如果100亿个url都放在hashMap里面，假设每个64k，共需要超过640GB，使用布隆过滤器，约需要23GB。 缺点：宁可错杀一百，也不能放过一个。在黑名单中的一定会被查出来，不在黑名单里的有可能也会被过滤出来，存在失误率，
等价于点在圆周的情况。 考虑n个点，n个点在同一半圆内，我们把逆时针方向最后一个点称作关键点。 选定一个点A，这n个点再以A为关键点的同一半圆内的充要条件是什么？ ——每个点都是1/2，所以所有点都在的概率是1/2^(n-1)
由于对称性，这n个点在以其它点为关键点的同一半圆内的概率也是1/2^(n-1)
所以n个点都在同一半圆内的概率是：n / 2^(n-1) 故而： 三个点就是：3/4 四个点就是：4/8=1/2
64匹马，8个赛道，找出前4名最少需要比赛多少场？ 参考：https://zhuanlan.zhihu.com/p/398143738
解答： 先分成8组 第一轮：赛8场 每组各赛一场，得到每组的前四名
第二轮：赛1场 从8组里面选出第一名进行比赛，可以得到一定被淘汰的马： 
第三轮：1场或2场 
此时A1已经确定是第一名了，D1是最危险的，我们选择除了D1之外的8匹马进行比赛： 加赛的情况： 如果C1是以第二名的成绩晋级，那么第二名将在A2-4，B2-3，C2中产生，所以并不知道D1与他们比谁快，需要7匹马加赛一场。 不加赛的情况： 如果C1岁以第3名到第7名的成绩完赛，那么除了D1这8匹马中的前3名就直接进入前4，无需进行加赛。