鱼C论坛

 找回密码
 立即注册
查看: 1684|回复: 41

[已解决]Python:每日一题 373

[复制链接]
发表于 2020-4-11 18:58:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
今天的题目:


假设你正在爬楼梯。给定数组 cost,数组的每个索引做为一个阶梯,第 n 个阶梯对应着一个非负数的体力值 cost[n]。

每当爬上一个阶梯都要花费对应的体力值,然后你可以选择继续爬一个阶梯或者两个。

找到达到楼层顶部的最低体力花费。

在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入:cost = [10, 15, 20]
输出:15
解释:从 cost[1] 开始,走两步即可到阶梯顶,一共花费 15 点体力值。
示例 2:

输入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出:6
解释:从 cost[0] 开始,逐个经过那些 1(跳过 cost[3]),一共花费 6 点体力值。


欢迎大家一起答题!
最佳答案
2020-4-11 20:06:38
本帖最后由 TJBEST 于 2020-4-11 22:08 编辑

最简单的方法,利用递推式进行循环迭代,比dp快
  1. def fun373(cost):
  2.     #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
  3.     M = len(cost)
  4.     if M == 1:
  5.         return cost[0]
  6.     elif M == 2:
  7.         return min(cost[0],cost[1])
  8.     a = cost[-2]
  9.     b = cost[-1]
  10.     for index in range(M - 3,-1,-1):
  11.         a,b = min(a,b)+cost[index],a
  12.     return  min(a,b)
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-4-11 19:04:59 From FishC Mobile | 显示全部楼层
依然不懂……
或者说多举一点例子
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-11 19:08:34 | 显示全部楼层
_2_ 发表于 2020-4-11 19:04
依然不懂……
或者说多举一点例子

输入:cost = [2, 3, 4, 5, 6]
输出:8

2, 3, 4, 5, 6, 阶梯顶部
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 19:09:54 From FishC Mobile | 显示全部楼层
zltzlt 发表于 2020-4-11 19:08
输入:cost = [2, 3, 4, 5, 6]
输出:8



最小?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 19:10:28 From FishC Mobile | 显示全部楼层
zltzlt 发表于 2020-4-11 19:08
输入:cost = [2, 3, 4, 5, 6]
输出:8


OK我明白了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 19:48:12 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2020-4-11 21:31 编辑

瞎写了个,竟然过了……
  1. class Solution:
  2.     def minCostClimbingStairs(self, cost: List[int]) -> int:
  3.         cost=cost.__iter__()
  4.         a=cost.__next__()
  5.         b=cost.__next__()

  6.         for i in cost:
  7.             a,b=b,min(a,b)+i

  8.         return min(a,b)
复制代码

整体思路就是动态规划,因为一次只能上一节或两节,所以只和前面的两个值有关,用两个变量就可以了。

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 20:06:38 | 显示全部楼层    本楼为最佳答案   
本帖最后由 TJBEST 于 2020-4-11 22:08 编辑

最简单的方法,利用递推式进行循环迭代,比dp快
  1. def fun373(cost):
  2.     #思想 倒序 f(n) = min(f(n+1),f(n+2))+a(n)
  3.     M = len(cost)
  4.     if M == 1:
  5.         return cost[0]
  6.     elif M == 2:
  7.         return min(cost[0],cost[1])
  8.     a = cost[-2]
  9.     b = cost[-1]
  10.     for index in range(M - 3,-1,-1):
  11.         a,b = min(a,b)+cost[index],a
  12.     return  min(a,b)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-11 20:07:39 | 显示全部楼层
TJBEST 发表于 2020-4-11 20:06
前排占座,另372题先别封还在做@zltzlt

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 20:36:01 | 显示全部楼层
  1. def f373(cost):
  2.     l=len(cost)
  3.     t=[0]*(l+1)
  4.     for i in range(2,l+1):
  5.         t[i]=min(t[i-1]+cost[i-1],t[i-2]+cost[i-2])
  6.     return t[l]
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 22:15:12 | 显示全部楼层
  1. def f(cost):
  2.     if len(cost)<=2:
  3.         return min(cost)
  4.     elif len(cost) == 3:
  5.         if cost[1] < cost[0]+cost[2]:
  6.             return cost[1]
  7.         else:
  8.             return cost[0]+cost[2]
  9.     else:
  10.         return min(cost[len(cost)-1]+f(cost[:len(cost)-1]),cost[len(cost)-2]+f(cost[:len(cost)-2]))
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 22:30:33 From FishC Mobile | 显示全部楼层
本帖最后由 kinkon 于 2020-4-12 12:45 编辑

虽然测试用例是对的,但是总感觉哪里有问题
  1. def f373(cost):
  2.     if len(cost) <= 2:
  3.         return min(cost)
  4.     cost.append(0)
  5.     left = 2
  6.     while left < len(cost):
  7.         cost[left] = min(cost[left-1], cost[left-2]) + cost[left]
  8.         left = left+1
  9.     return cost[-1]
复制代码

空间换时间
  1. def p373(cost):
  2.     if len(cost) <=2:
  3.         return min(cost)
  4.     cost.append(0)
  5.     dp = [0]*len(cost)
  6.     dp[0],dp[1]=cost[0],cost[1]
  7.     for c in range(2, len(cost)):
  8.         dp[c] = min(dp[c-2],dp[c-1])+cost[c]
  9.     return dp[c]
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-11 23:26:54 | 显示全部楼层
  1. def f373(cost):
  2.     dp = [0]*(len(cost))
  3.     dp[0] =cost[0]
  4.     dp[1] = cost[1]
  5.     stairs = len(cost)
  6.     for i in range(2,stairs):
  7.         dp[i] = min(dp[i-1]+cost[i],dp[i-2]+cost[i])
  8.     return min(dp[-2],dp[-1])
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 00:20:10 From FishC Mobile | 显示全部楼层
[ 本帖最后由 山岂乎不在高 于 2020-4-13 00:10 编辑 ]\n\ndef p373(a):
    s=0
    a=[0]+a+[0]
    while True:
        if sum(a)==0:
            return s
        i=a.index(max(a))
        s+=a[i+1]+a[i-1]
        a[i]=a[i-1]=a[i+1]=0

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 00:58:36 | 显示全部楼层
  1. d=[]
  2. def f373(cost):
  3.     d=[]
  4.     for i in range(int('1'*len(cost),2)+1):
  5.         b=0
  6.         c=[]
  7.         a=bin(i).replace('0b','').zfill(len(cost))
  8.         for j in str(a):
  9.             b+=int(j)+1
  10.             if b>len(cost):break
  11.             else:c.append(cost[b-1])
  12.         n=0
  13.         for j in c:
  14.             n+=j
  15.         d.append(n)
  16.     print(min(d))
复制代码

评分

参与人数 1荣誉 +4 鱼币 +4 收起 理由
zltzlt + 4 + 4

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 02:22:11 | 显示全部楼层
本帖最后由 阴阳神万物主 于 2020-4-12 02:44 编辑

难度评级:简单
要素分析:贪心
代码:
  1. def solve(cost:'list of int >=0')->int:
  2.     i,u = -1,0
  3.     while i < len(cost)-4:#结束循环后最多只剩3级台阶要上
  4.         a,b = i+1,i+2
  5.         i = a if cost[a]<cost[b] else b
  6.         u += cost[i]
  7.     return u+min(sum(cost[i+1::+2]),sum(cost[i+2::+2]))

  8. if __name__ == '__main__':
  9.     print('示例1 输出:',solve([10, 15, 20]))
  10.     print('示例2 输出:',solve([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
  11.     print('自测 输出:',solve([1,1]))
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 04:10:12 From FishC Mobile | 显示全部楼层
怎么越想越难呢???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 18:57:33 | 显示全部楼层
每天只能刷到前一天的我也是不懂
  1. # 动态规划
  2. # dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
复制代码
  1. def daily373_1(cost: list) -> int:
  2.     length = len(cost)
  3.     dp = [0 for _ in range(length)]
  4.     dp[0], dp[1] = cost[0], cost[1]
  5.     for i in range(2, length):
  6.         dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
  7.     return min(dp[length - 1], dp[length - 2])
复制代码

发现只与前两个有关,可以只用两个变量记录而不用数组
  1. def daily373_2(cost: list) -> int:
  2.     pre, ppre = 0, 0
  3.     for i in range(len(cost)):
  4.         pre, ppre = min(pre, ppre) + cost[i], pre
  5.     return min(pre, ppre)
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 21:34:20 | 显示全部楼层
我还是小白,还不懂...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 22:47:35 | 显示全部楼层
def func373(cost):
    n = len(cost)
    for i in range(2,n):
        cost[i] += min(cost[i-1],cost[i-2])
    return min(cost[-1],cost[-2])

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-12 23:13:35 | 显示全部楼层
观摩大佬们的解答
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 22:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表