Leetcode 题
逻辑思维题
- 你家正在装修，你在网上买了A、B两个桶，A桶装红色颜料，B桶装蓝色颜料，两桶的颜料一样多。你准备从B桶舀一杯，倒入A桶中，搅拌均匀后再从A桶舀一杯，倒入B桶中，请问A桶的红蓝颜料比例 和B桶的蓝红颜料比例，谁的更高？
:::success
解析：
今天我来带大家分析一下红蓝桶问题哈，这道题目 “A桶的红蓝颜料比例”和“B桶的蓝红颜料比例”是一样的。那我们可以采用许多种方法，考虑这道题目，比如整体法、极限法、特殊值代入法、列式法。
方法一：整体法（或是极限法的变形）
请你把A、B两桶看成整体，不论是开始舀杯前，还是结束舀杯后，A、B两个桶的颜料均是一样多的，因此 “A桶的红蓝颜料比例”和“B桶的蓝红颜料比例”是一样的。
有的面试官可能会追问，你是否能用式子将其表达出来？
方法二：列式法
我们假设桶装的颜料大小是L，舀一杯的大小是X
第一步：A桶：L+X；B桶：L-X
第二步：搅拌均匀后：A桶红蓝颜料比例是 L ：X（无论是否有“从A桶舀一杯，倒入B桶”的操作，红蓝颜料比例是不变）
B桶：
蓝色颜料：L-X + (X/(L+X))X
红色颜料：(L/(L+X))X
算下来B桶蓝红颜料比例也是L：X
:::
你和小园一起去字节跳动的乒乓球室玩耍，球室桌上排列着100个乒乓球，由你和小园两个人轮流拿球装入口袋，能拿到第 100 个乒乓球的人为胜利者。条件是：每次拿球者至少要拿 1 个，但最多不能超过 5 个，问：如果你是最先拿球的人，你该拿几个？以后怎么拿就能保证你能得到第 100 个乒乓球？ :::success 解析：
博弈论问题。面试的时候，题目形式可以变成拿硬币、拿石头、拿XX等等，换一下描述对象，都有可能。
那用通俗一点的方法来处理，抓住核心：怎么样做能确保自己拿最后一个球？——那当然是最后一次的拿球机会留在自己手里。我们可以逆向思维思考这道题，如果只剩6个乒乓球，让对方先拿球，你一定能拿到第6个乒乓球（举例说明: 如果他拿1个，你拿5个;如果他拿2个，你拿4个;如果他拿3个，你拿3个;如果他拿4个，你拿2个;如果他拿5个，你拿1个。）我们再把100 个乒乓球从后向前按组分开，6个乒乓球一组。100不能被6整除，这样就分成17 组;第1组4个，后16组每组6个。这样先把第1组4个拿完，后16组每组都让对方先拿球，自己拿完剩下的。这样你就能拿到第 16 组的最后一个，即第100 个乒乓球。
综上所述：策略是你先拿 4 个，他拿 n 个，你拿 6-n个，依此类推，保证你能得到第 100 个乒乓球。
Leetcode 石子游戏 :::【赛马问题】一共有25匹马，赛场上有5条跑道，每次最多只能跑5匹。假设每匹马的水平发挥稳定，不用任何其他工具，只通过马与马之间的比赛进行PK（不存在并列情况）。请问最少比多少场，能选出最快Top3的马？ :::success 解析：
答案是7场。
先把25匹马随机分成5组（A、B、C、D、E组），分别进行一次比赛；5场比赛结束后，将这5场比赛的第一名的马选出来参加第6场比赛。将第6场比赛的第一名所在的组定为A组，第二名所在的组定为B组，第三名所在的组定为C组，以此类推。
第7场比赛选 A2、A3、B1、B2、C1的马参加，即可找出25匹马中跑得最快的3匹马。（D、E组的马无需考虑。）
:::
【赛马问题二】一共有64匹马，赛场上有8条跑道，每次最多只能跑8匹。假设每匹马的水平发挥稳定,不用任何其他工具，只通过马与马之间的比赛进行PK（不存在并列情况）。请问最少比多少场，能选出最快Top4的马？” :::success 解析：
答案是10场或11场
思路同上，把64匹马随机分成8组（A、B、C、D、E、F、G、H组），分别进行一次比赛；8场比赛结束后，将这8场比赛的第一名的马选出来参加第9场比赛。将第9场比赛的第一名所在的组定为A组，第二名所在的组定为B组，以此类推。
题中想选出跑得最快的4匹马，因此E、F、G、H组的马无需考虑。
A1一定是64匹马中跑得最快的。剩下在A2、A3、A4、B1、B2、B3、C1、C2、D1中选出跑得最快的前三名。在待定的9匹马中选8匹马参与第10场比赛，可以剔除A4参赛（剔除其他马也可以，只要第十一场比赛的情况说得通，即可）。
比如，当我们剔除A4时，如A3快于B1，则需要比第11场（A4与B1）判断出谁是第四名。 :::【毒药问题】有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有 1 瓶是毒药。任何喝下毒药的生物都会在一天内死亡。如果你想在一天内找到毒药，最少需要几只小动物？ :::success 解析：
将这1000个瓶子依次进行编号：1 , 2 , 3 , 4 , 5 , 6 … 1000，并转换为二进制（如0000000001 为第一瓶，0000000010第二瓶，0000000011 为第三瓶），即可得知2的10次方是1024，因此需要用10只小动物（假定为小白鼠）。从右往左算第N位，该位数上显示“0”代表第N只小白鼠不喝药水，“1”代表第N只小白鼠喝药水（如第三瓶0000000011，需要第1只小白鼠和第2只小白鼠喝药水，其余小白鼠不用喝）。观察哪几只小白鼠死亡，若死亡小白鼠是第N只，该位数计为1，由二进制转为十进制，便可推出是几号瓶子是毒药。 :::
若有收获，就点个赞吧
0 人点赞
