首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >HackerRank挑战:找到植物死亡的总天数

HackerRank挑战:找到植物死亡的总天数
EN

Stack Overflow用户
提问于 2015-08-03 02:38:48
回答 9查看 9.3K关注 0票数 2

问题陈述 花园里有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提交链接

失败测试用例1 : 输入 输出

失败测试用例2 : 输入 输出

到目前为止我的代码:

代码语言:javascript
运行
复制
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)

它仍然失败了一些测试用例。有什么建议/建议吗?

EN

回答 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一样。

代码语言:javascript
运行
复制
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

我正在考虑一种更快的动态方法,它应该可以工作,但还没有使它发挥作用。

票数 1
EN

Stack Overflow用户

发布于 2016-07-03 13:20:51

下面是O(n)复杂性的一种方法,这与发现问题的跨度非常相似:

代码语言:javascript
运行
复制
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)
票数 1
EN

Stack Overflow用户

发布于 2016-12-07 04:24:32

通过python版本,基本上修改了@DarthSpeedious的代码,并添加了一些注释#在这里输入您的代码。从STDIN读取输入。打印输出到STDOUT

代码语言:javascript
运行
复制
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)
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31778691

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档