传说是小米家的一道面试题难倒了某Java程序员。扑克牌排序问题。

网上说的是有位网友在面试小米Java岗三次后,终于挺进了第三轮面试,结果还是败在了两道算法题上面。

1、写个读方法和写方法,实现读写锁

2、一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手机没牌,最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数

(来源:https://zhuanlan.zhihu.com/p/38850888)

第一个问题不重要,这里讨论第二个扑克牌排序的问题。

此题也没有写清楚,说“最后桌子上的牌是从1到n有序”,是从上到下还是从下到上数是1到n呢?我这里暂定为从上到下,因为两个方向的解题思路是一致的,不管哪个方向无所谓。且暂定牌面数值为1到无穷大,而不是A到K。

从上到下就是,初始,牌在手上,成某顺序排列。第一步,从手里牌顶取一张放到桌子上;第二步,从手里牌顶取一张放到手里牌底。就这两个动作一直重复,其中除了第一张,后续放到桌上的牌要叠在桌上牌的上面,也就是不能在桌上乱丢。直到手里牌全部放到了桌子上。其中当手里只剩一张牌,而上一步的动作是把倒数第二张牌从手牌顶移到了桌上,按规则此时应该把手牌顶的牌移到手牌底,而此时手牌顶和手牌底是同一张,所以此动作可以当作最后一张手牌不动,而下一步,又得将手牌顶(也即是手牌底,即是手中最后一张)移到桌上,至此,移动结束。最后要达到的状态就是桌上的牌,从上往下数,第一张是1,第二张是2,……直到n。

  我一开始看到这题,突然感觉好简单,因为牌的数量无所谓,5张排序和500张排序的算法是一样的。想了想,5张而已,多简单啊,这张先在上面,那张又在上面,这张又到下面,感觉逻辑过程很简单。

  但实际在代码实现的过程中就懵了,要对牌量无上限的牌堆做出这样的排序,使得无论牌多牌少,只需要一个算法,几行代码,统统不在话下,在不考虑时间复杂度的情况下。

  所以说计算机的思维过程跟人不一样啊……用计算机来做就是不如想象中那么简单。

  我的实现思路很傻瓜化,跟我以前解数学问题如出一辙,就是先举例子,比如取n等于2的情况,初始顺序(如无特殊说明,均指从上往下的顺序)很容易得到,[2,1],再看n=3,脑算一下就知道是[3,1,2],n=4则对应[4,2,3,1],具体如下:

以下为心算结果:
    #n=1,  [1]
    #n=2,  [2,1]
    #n=3,  [3,1,2]
    #n=4,  [4,2,3,1]
    #n=5,  [5,1,4,2,3]
    #n=6,  [6,3,5,1,4,2]
    #n=7,  [7,2,6,3,5,1,4]

  万变不离其宗啊,我忽然就看到了里面的规律。每个列表的第一个值肯定是n,不用多说;并且每个列表除去最后一个元素,剩下的跟下一个列表的尾部一模一样,比如n=4时候,除去最后一个1,为[4,2,3],而[4,2,3]恰恰是当n=5时候的尾巴;并且暂时除去的1跑到了这个尾巴的前一个位置,即第二位。第一位是n,第二位是前一个的最后一个元素1,剩下的是n=4时列表[4,2,3,1]除去1的[4,2,3]。然后我就笑了,心想这个算法也太sb了吧,像是照葫芦画瓢,没任何技术含量,并且我隐约感觉到此递归算法的时间复杂度是最高的。这很明显,每一个列表都可以通过前面一个推出来,跟斐波那契数列算法是一样的,可以用递归。

  试了一下,Python代码如下:

def cards_on_hand(n):
    if n<=0 or isinstance(n,int)==False:
        print('请输入正整数')
    if n==1:
        return [1]
    if n>1:
        previous=cards_on_hand(n-1)
        return [n, previous.pop(-1)]+previous

  此函数需引入参数n,即牌的数量。返回值为列表,即手上牌从上往下的顺序成列。

  用jupyter notebook测试结果显示,当n小于等于2965,可秒算,等于2966或更大时,程序报错,“RecursionError: maximum recursion depth exceeded in comparison”。意思大概是递归超出最大深度。当然实际的复杂度测算也是必须的,等下面跟网上其它算法比较的时候再用。

  其它算法,有一个,思想来源于自称“微软工程师”的大哥,有个网友用python初略实现了“巨硬哥”的算法,叫做“逆向法”。我只是感觉这个逆向的原理跟递归是一样的算法。具体如下:

#网友对逆向法的Python代码实现:(这位网友是把最终桌上的牌从下往上数的,也就是最下面是1,最上面是n。但这不影响)
def MiTest2(n):
    result=[]
    for i in range(n):
        result = result[-1:] + result[:-1]
        result = [(n-i)] + result
    return result

  其中的for循环不断改变result的值,直到循环到n,看起来这个逻辑过程跟递归一样一样的。

  也是用jupyter运行一下,看是不是到2965也算封顶了。

  结果令人很满意,我试到了50000,没错,就是五万,差不多n=50000时,花了20秒的时间。但不会报递归错误。

  由此我发现这个逆向法跟递归是有渊源的,其中逆向法的数学原理绝对是妙不可言的,我等一下再分析。

  先把这段网友代码,按从上往下数的顺序再改一下:

def hand_cards(n):
    if n<=0 or isinstance(n,int)==False:
        print('请输入正整数')
    result=[]
    for i in range(n):
        result = result[-1:] + result[:-1]
        result = [i+1] + result
    return result

改成这个顺序,那最终桌上的牌就是从上往下数,1到n,网友原代码的结果是,从上往下数,n到1。代码中关键就改了for循环中第二行,result = [(n-i)] + result改成了result = [i+1] + result。

很明显,这个“逆向法”(从上往下数)的步骤是,对于任意给定正整数n:

首先生成一个列表[1];

将其最后一位元素移到首位,变成[1],再将下一个2挤入首位,生成第二个列表[2,1];

将其最后一位元素移到首位,变成[1,2],再将下一个3挤入首位,生成[3,1,2];

将其最后一位元素移到首位,变成[2,3,1],再将下一个4挤入首位,生成[4,2,3,1];

重复这两个步骤,直到n。

  

上一篇:java io读书笔记(4)字符数据


下一篇:Windows Server 2003 激活码及激活方法