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

题目源自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