Codility每周一课：L7 Stacks and Queue
7.png
P7.2 Fish
N voracious fish are moving along a river. Calculate how many fish are alive.
-
P7.2 鱼儿
鱼儿在河里觅食，最终有多少条鱼是活的
A和B均是由N个整数组成的两个非空数组，均表示N个在河流中觅食的鱼。鱼的编号从0到N-1，最开始每条鱼都有一个特定的位置。如果P和Q是两条鱼，并且P<Q，表示鱼P最初位于鱼Q的上游。
数组A表示鱼的大小，它的所有值都是唯一的。
数组B表示鱼游的方向，它只包含0和1，其中：
-
0表示向上游的鱼；
-
2. 1表示向下游的鱼；
如果两条鱼向相反的方向游动，并且它们之间没有其他（活的）鱼，它们最终会相遇。那么只有一条鱼可以存活，因为较大的鱼会吃掉较小的鱼。更准确地说，当P<Q，B[P]=1和B[Q]=0时，两条鱼P和Q之间没有活鱼，它们相遇后：
-
如果A[P]>A[Q]，则P吃Q，P仍将向下游动;
-
如果A[Q]>A[P]，则Q吃P，Q仍将向上游动;
假设所有的鱼都以相同的速度游动。也就是说，朝同一方向游动的鱼永远不会相遇。目标是计算将存活的鱼的数量。
例如，数组A和B，其中：
A[0]=4，A[1]=3，A[2]=2，A[3]=1，A[4]=5
B[0]=0，B[1]=1，B[2]=0，B[3]=0，B[4]=0
一开始，所有的鱼都是活的。除1号鱼外，所有的鱼都向上游移动。1号鱼遇到2号鱼并吃了它(A[1]>A[2])，然后它遇到3号鱼也吃了它(A[1]>A[3])。最后，它遇到4号鱼并被它吃掉(A[1]<A[4])。剩下的两条鱼，0号和4号，永远不会相遇，因此活着。
编写函数：
def solution(A, B)
给定两个由N个整数组成的非空数组A和B，则返回活鱼的数。
例如，给定上面所示的数组，函数应该返回2。
假定：
-
N是区间[1，100000]内的整数；
-
数组A的每个元素都是区间[0..100000000]中的整数；
-
数组B的每个元素为0或者1；
-
数组A的元素都是不同的；
- 解题思路
类似于括号匹配。从头开始遍历数组B，如果元素为0，并且存储向下游的鱼的列表为空，则此鱼肯定是活鱼。如果列表不为空，就进行吃鱼的判断。如果把列表中的鱼全部吃掉，则活鱼加1。如果元素为1，则添加到列表中。最后的活鱼数再加上列表的长度即可。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 7：Stacks and Queues
# P 7.2 Fish
def solution(A, B):
"""
相遇的鱼大鱼吃小鱼
:param A: A表示鱼的大小
:param B: 表示鱼游的方向
:return: 活鱼的数目
"""
alive_fish = 0
fish_down = [] # 存储向下游的鱼
for index, value in enumerate(B):
if value == 0:
if len(fish_down) == 0:
alive_fish += 1
else:
# 开始判断吃鱼
try:
while fish_down[-1] < A[index]:
fish_down.pop(-1)
except IndexError:
alive_fish += 1
else:
fish_down.append(A[index])
return alive_fish + len(fish_down)
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
