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
欢迎扫描下面的二维码关注公众号:
原文始发于微信公众号(公子政的宅日常):Python冒泡排序解决“New Year Chaos”