Python冒泡排序解决“New Year Chaos”

>>最全面的Java面试大纲及答案解析(建议收藏)  

题目源自hackerrank

问题描述

在新年里,有一群人要去玩过山车,他们依次排好了队,但是由于是新年夜,所以这个队伍发生了混乱。每个人都可以通过贿赂往前面一位的人来使自己更快玩到过山车,不过每个人最多只能贿赂两次。例如1,2,3,4,5,如果5想要排到前面去,他可以贿赂4,再贿赂3,要记住最多只能贿赂两次,最后这个队伍变成了1,2,5,3,4
现在我们要写一个函数,他接收一个由整数构成的列表作为参数,并返回这个队伍里总的最少贿赂次数,如果有某个元素贿赂了超过两次,就返回Too chaotic
例如:

  • 2,1,5,3,4,很显然,5贿赂了4,接着又贿赂了3,而2则贿赂了1,没有人违反规定,所以返回3,代表整个队伍中的人一共贿赂了3次。

  • 2,5,1,3,4,这个例子里显然最少贿赂次数超过了3,因此只能“Too chaotic”了。

代码:

def NewYearChaos(queue):
    lastIndex = len(queue) - 1
    swaps = 0
    swaped = False

    # check if the queue is too chaotic
    for i, v in enumerate(queue):
        if (v - 1) - i > 2:
            return "Too chaotic"
    # bubble sorting to find the answer
    for i in range(0, lastIndex):
        for j in range(0, lastIndex):
            if queue[j] > queue[j+1]:
                queue[j], queue[j+1] = queue[j+1], queue[j]
                swaps += 1
                swaped = True

        if swaped:
            swaped = False
        else:
            break
    return swaps

简单解释

  • enumerate()这个函数可以生成一个可迭代对象的索引序列,例如给他一个列表,将返回一个包含列表索引和元素的结构。常用于for循环中。判断一个队列是否太过混乱,可以看其中某个元素,例如2,1,5,3,4中的5,相比原序列1,2,3,4,5,5变到了第2位上(别忘了是从0开始计数的),所以这里使用if (v - 1) - i > 2来判断。如果移位大于2,就可以返回Too chaotic了。

  • 接着使用冒泡排序,并使用swaps变量来记录最少的贿赂次数。在Python中交换两个变量的值写起来非常简单:a, b = b, a


欢迎扫描下面的二维码关注公众号:

Python冒泡排序解决“New Year Chaos”


原文始发于微信公众号(公子政的宅日常):Python冒泡排序解决“New Year Chaos”