HackerRank挑战:找到植物死亡的总天数
问题陈述 花园里有N种植物。这些植物中的每一种都添加了一定量的杀虫剂。每天之后，如果任何一种植物比左边的植物含有更多的杀虫剂，比左边的植物弱，那么它就会死亡。您将得到每种植物中农药的初始值。打印没有植物死亡的天数，即没有比植物左边的植物含有更多农药的时间。 输入格式 输入由一个整数N组成，下一行由描述数组P的N个整数组成，其中Pi表示植物i中农药的数量。 约束 1≤N≤100000 0≤Pi≤109 输出格式 输出一个等于没有植物死亡的天数的单一值。 样本输入 6 5 8 4 7 10 9 样本输出 2 解释 起初，所有的植物都是活的。 植物= {(6,1)，(5,2)，(8,3)，(4,4)，(7,5)，(10,6)，(9,7)}。 Plantsk = ( i，j) => jth装置具有农药用量=I。 第1天后，有4株植物死亡，3株、5株和6株死亡。 植物= {(6,1)，(5,2)，(4,4)，(9,7)} 第2天后，3株植物在7株死亡后存活。 植物= {(6,1)，(5,2)，(4,4)}。 第3天后，3株植物存活，不再有植物死亡。 植物= {(6,1)，(5,2)，(4,4)}。 第二天之后，植物停止死亡。
挑战链接: HackerRank :有毒植物
My Submission : HackerRank提交链接
到目前为止我的代码:
total = int(raw_input())
plants = map(int,raw_input().split())
num_deaths = 1
day = 0
while num_deaths > 0:
num_deaths = 0
temp_plants = []
day += 1
for i in range(1, len(plants)):
if plants[i] > plants[i - 1]:
num_deaths += 1
continue
else:
temp_plants.append(plants[i])
plants = temp_plants
print(day - 1)它仍然失败了一些测试用例。有什么建议/建议吗？
回答 9
Stack Overflow用户
发布于 2015-08-03 09:01:44
查看您的Temp_plants数组，使用[]初始化它。但是，由于您正在从索引1中迭代，所以总是排除索引0中的工厂，所以您必须使用[plant[0]]初始化，因为最左边的工厂总是包括在内的。
例子:1 5 4 3 2
实际过程
- 1 5 4 3 2
- 1 4 3 2
- 1 3 2
- 1 2
- 1
Answer=4
您的代码
- 1 5 4 3 2
- 注:最左边的1不包括在内
Answer=1
这里有一个工作代码，它产生正确的输出，但速度相当慢。它是正确的，但是O(n^2)，它超时了一些测试案例。这基本上和你的algo一样。
n= input()
plant=map(int,raw_input().split())
count=0
# At each iteration the following loop updates the plant
# list by removing weak plants and count counts no. of steps
# temp temporarily stores surviving plants
while(True):
temp=[plant[0]]
for i in range(1,len(plant)):
if plant[i]<=plant[i-1]:
temp.append(plant[i])
# If temp and plants have same len, then no plant has
# been removed, so, the process ended.
if(len(temp)==len(plant)): break
plant=temp
count+=1
print count我正在考虑一种更快的动态方法，它应该可以工作，但还没有使它发挥作用。
Stack Overflow用户
发布于 2016-07-03 13:20:51
下面是O(n)复杂性的一种方法，这与发现问题的跨度非常相似：
class Stack():
def __init__(self):
self.items=[]
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def isEmpty(self):
return self.items==[]
def peek(self):
return self.items[-1]
def __str__(self):
return str(self.items)
if __name__=="__main__":
arr = [1, 3, 5, 2, 7, 6, 4, 2, 1]
l_a = len(arr)
stack = Stack()
e_span = [None]*l_a
for i in range(l_a):
elem = arr[i]
x = None
max_span = 0
while not stack.isEmpty() and elem<=arr[stack.peek()]:
x = stack.pop()
max_span = max(e_span[x], max_span)
if stack.isEmpty():
e_span[i]=0
elif x is None:
e_span[i]=1
else:
span = max_span+1
e_span[i]=span
stack.push(i)
print max(e_span)Stack Overflow用户
发布于 2016-12-07 04:24:32
通过python版本，基本上修改了@DarthSpeedious的代码，并添加了一些注释#在这里输入您的代码。从STDIN读取输入。打印输出到STDOUT
raw_input()
arr = map(int, raw_input().strip().split())
stack = []
days = [0 for i in range(len(arr))]
max_span = 0
for i in range(len(arr)):
x = None
max_span = 0 # max_span is only meaningful when the current element smaller than the stack top, so it will get reset for each element.
while stack != [] and arr[stack[-1]] >= arr[i]:
x = stack.pop()
max_span = max(max_span, days[x])
# if it is the first element, days[i] = 0
if not stack:
days[i] = 0
# if it is the element do not trigger any pop, which means it is greater than its own left(since each element will
# be pushed to the stack anyway), so the days[i] = 1
elif not x:
days[i] = 1
# if it triggered the pop, which means the arr[i] will wait all the poped element die, then it will die the next day, so days[i] should be the current max_span + 1
else:
days[i] = max_span + 1
stack.append(i)
print max(days)https://stackoverflow.com/questions/31778691
复制相似问题
腾讯云开发者
