换个角度思考问题

最近在看一本书，叫做《思考的乐趣》，第26节“我最爱的证明”，里面介绍了这样一则有趣的问题（文章链接在此）：

设想一个平面上布满间距为1的横纵直线，形成由一个个1×1正方形组成的网格。任意给一个面积小于1个单位的图形，证明这个图形总能放在网格中而不包含任何一个格点。

初看这个论断，觉得似乎是正确的，但又不知从何下手。文中指出证明的思路很巧妙，让人感到数学的美妙。我的感触是，文中的证明大大地换了个角度，很有峰回路转的感觉。正在读这篇文章的你，不妨先思考一下，别急着往下看答案。

如果陷入了拼命去构造各种各样的图形类别，去思考不同类别图形的情况下，怎么去摆放这样的图形，使得图形不覆盖到格点，就如同陷入了泥沼，很难绕清楚路线了。思考问题的情况往往类似，如果一条路走不通，又觉得似乎并不复杂，不愿意轻易放弃，就很容易陷进去难以自拔。这样的问题思考情形并不特指常规意义上的算法题，而包含了各种各样的实际问题。

再来看看文中的解答：

我们可以这样考虑这个问题：把图形随意放在网格中，如何移动网格使每个格点都在图形外面。

现在我们把给定的图形随意放在网格中。然后沿着网格线把包含有图形的网格切成1×1的小格子，从网格中拿出来。把它们重叠起来（不旋转），再想像这些格子是透明的，而图形是不透明的。从上往下看这一叠格子，你看到的会是这个图形的各部分重叠地放在一个格子中，仿佛一个沾有污渍的方块。很显然这些污渍不会布满整个方块（图形面积小于一个格子的面积），方块上总有一块干净的地方。现在我们用一颗针从一个干净的地方刺下去，把这些重起来的格子刺穿。把这些格子放回原来的网格中，你看到的会是每一个有图形的方格内都有一个针眼，这些针眼都不在图形内。现在可以把原来的网格擦掉了，这几个针眼可以看作是新网格的格点。按针眼的位置重画新的网格，那么这个图形内决不会有新网格的格点，此时，结论也就证到了。

怎么样，是不是很巧妙？由相对固定网格，去摆放图形；改为相对固定图形，去摆放网格。问题居然一下子就清晰起来。我们都知道要换个角度去认识和思考问题，但是真正遇到问题的时候，又有多少人能够做到这一点呢？

再来看一道我很喜欢问的面试题：

假如说有这样一个SNS网站，每一个注册用户都有自己的主页。而网站中有这样一套积分系统，对于用户的各种各样的行为，都会引起用户积分的微小变化，例如，用户登陆一次+1分，用户加一个好友+2分，用户发表一篇评论+1分，用户评论包含不良内容-3分等等。现在，注册用户的个人主页上需要展示用户的个人信息（例如用户姓名），以及用户的积分，同时，还要展示用户的积分在网站所有用户（大约两千万用户）中精确的排名。现在为了简化问题，我们假设用户信息和积分信息全部存放在内存中。如果你要设计这样一个网站，你会怎样设计内存中存储这些信息的数据结构，以便在访问用户主页的时候迅速展示用户的积分和积分排名信息，同时，在用户积分发生上述变更的时候能够使排名得到快速更新？

我很喜欢问这样的问题是因为这样的问题在可以考察数据结构等等基础知识的同时，非常明确地考察了解决实际问题的能力。这样的问题远远比分析一个字符串、处理一个表达式这样的传统意义上的纯算法题有实际意义得多。在实际应用中，我通常会把它拆成几问，以降低难度，而且可以增加区分度。这道问题没有所谓的标准答案，有很多人都给出了非常漂亮的解答。我在此举一例而已，您也不妨先思考一下再往下阅读。

几乎所有的人都会首先想到使用HashMap来存储用户信息，key为用户id（uid），value为用户信息的对象，这样的好处是访问用户首页时，理论上获取用户信息的的时间复杂度是常数阶的，非常快。可是很多聪明的人也会忽然意识到，存储积分容易，但是排名信息的更新呢？如果排名信息作为value的一部分存储在这个HashMap里，当分数发生变更的时候，有那么多的用户，我需要遍历所有的value，取出积分来重新排序，这样的时间复杂度是很难接受的。

如果只是把思路限制在“根据用户id去取得排名”，就很难得到最优的解决方案，比较好的同学也只是想出使用树等等可以让时间复杂度为log(n)的设计。但是，如果我们换个角度思考问题，变成“根据用户排名去取得用户信息”，问题说不定就豁然开朗了。“排名”有一个天然的优势是一定是从1开始的连续正整数列表，它的长度就等于所有用户的数量。当我提示到这一句话的时候，有些本来没有头绪的同学也能够自己把问题解答下去了——这样的数据结构形式，非常适合使用数组来表达，根据下标去访问元素，是非常快的。于是设计一个数组Array，下标表示用户排名，值表示用户信息对象（例如用户名、描述等等）：

 

1	Array[rank] = userInfo

 

这样的设计还有什么好处？当用户积分发生变更的时候，请注意题中的说明，每次变更都是“微小变化”，对于这样一个偌大的数组而言，每次积分变更引起的用户排名的调整往往非常小，例如用户积分为29876分，增加了3分，变成了29879分，那么引起变化的只有从29876到29879积分的用户排名，换言之，只需要在数组中向上游或者下游简单地寻溯遍历几个元素而已；而且，对于这样的调整来说，不需要锁住整个数组，而只需要锁住其中小小的一个区段而已。

别急，问题还没有解决，现在的问题变成了，给定用户uid的时候，我怎样能够快速取得用户的排名（rank）呢？因为有了排名我才能从刚才的数组里面去取得用户信息啊。回过头来看一看，原本的HashMap不是可以派上用场吗？设计这样的HashMap，让key为uid，value为用户的排名信息（rank），每次在用户需要获取排名信息的时候，先根据uid在HashMap中取得rank，再根据rank在Array中取得用户信息：

 

1	HashMap<uid, rank>

 

这样一来，rank变成了HashMap和Array的桥梁，在每次分数发生微小变更时要做的调整，以及每次根据uid来获取用户的积分和积分排名信息时要做的查询，全部都是常数阶的。这两个数据结构本身都很简单，但是在遇到实际问题的时候，将实际问题是用最合适的数学和工程模型来解决的能力，这本身应当是属于比传统意义上纯粹的算法问题更有考察价值的部分。

我还在《再谈大楼扔鸡蛋的问题》里面介绍了一个使用等差数列求和公式来解题的证明，其中的思路也是“换个角度思考问题”，把“给定大楼层总数情况下，思考最少要扔多少次鸡蛋来确定鸡蛋恰好破碎的临界层”，变成“给定扔鸡蛋的最多次数的情况下，思考最多可以在多少层高的大楼内确定鸡蛋破碎的临界层”。如果您感兴趣请移步。

也许我们都做过很多需要换个角度思考的题目，例如在物理中我们有时需要改变参考系，在数学中有时我们需要改变坐标系，但是要真正理解它却并不容易。前两天在解决一个并不复杂的几何问题的时候，一眼就看出问题可以通过解析几何的办法来解答，但是仅仅利用初等的三角形的性质，却觉得无从下手，最后费了好大劲才搞定。为什么一定要用那么强大的工具来解决简单的问题呢？“换个角度”的实质在于需要改变思考问题的切入点和方向，而当我们掌握了通用的解题思路以后，掌握了更强大的解决问题的技巧以后，为什么原本或开阔或自然的思路反而被压制了呢？

文章系本人原创，转载请保持完整性并注明出自《四火的唠叨》

评论

1 楼 huanglongje 2013-10-04  

  讲的很好