上期题目：每期一题之1：小朋友开party
题解：（先定义一个概念：图中一个点的度(degree)，指的是有多少条边与这个点相连。）
显然，如果图中一共有偶数条边，那么直接满足要求，不需删任何点。下面只考虑有奇数条边的情况。
情况一：如果我们删掉一个奇数度的点，那么同时会删掉奇数条边，那么就得到了一个有偶数条边的图。在这种情况下，我们当然是删掉权值最小的那个点。而且容易看出，如果我们删除的点集里包含奇度点，那么只需删除一个奇度点即可，再多的都是多余操作。
情况二：在情况一以外，另外一种可能就是我们只删偶数度的点。这时可以发现，如果我们只删除一个偶度点，或者多个不相连的偶度点，是没有作用的，结果还是奇数条边。只有删除两个相连的偶度点（即删除一条两端都是偶度点的边），才会改变边数的奇偶性。同理，只需删一条这样的边即可，再多都是多余操作。
所以最终算法就非常简单了，我们先统计所有点的度，然后选中最小权值的奇度点，记为v1；再考察所有满足“两个顶点都是偶数度”的边，选中权值最小的那条边（边的权值为两个顶点权值之和），记为v2。v1和v2的较小者即为最终答案。算法时间复杂度为O(E)。
本期题目：猜数字
这是多年以前我毕业时面试国内某司被问的一道题，题目本身非常的不错，虽然未必适合拿来当面试题。当时能做出来我自己也是很高兴的 😀
我们两人玩一个猜数字的游戏。我根据一个给定的概率分布（这个分布我们两人都知道），在1~N里随机选一个数字，你通过问一些问题，猜出这个数字是多少。你的问题是类似“这个数字是奇数吗？”或者是“这个数字是4或者6或者9吗？”，更形式化地说，你每次询问一个集合，我告诉你我选的数是不是在这个集合内。现在要求是设计一个算法，对于一个给定的概率分布，得到一个最优的猜数方案，使得问题轮数的期望(aka.平均要问多少个问题)最小。
例子：为了简单起见，假设只有3个数，概率分布是[p1=0.1, p2=0.1, p3=0.8]。那么你的最优策略应该是先问，这个数是不是3。我有80%的概率说是，直接结束；有20%的概率说不是，这样你要再花一次机会。所以总的问题轮次的期望为 0.8 * 1 + 0.2 * 2 = 1.2
问题(1)：若N=8，且8个数字是均匀分布，每个都是1/8的概率，怎么做？
问题(2)：若N<=10，概率分布任意，怎么做？
问题(3)：若N<=1000，怎么做？