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)
- 结果
点击获得更多编程练习题。欢迎Follow,感谢Star!!! 扫描关注微信公众号pythonfan,获取更多。
image image
网友评论