[Swift]LeetCode746.使用最小花费爬楼梯|MinCostClimbingStairs

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10525485.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

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

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 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。

注意：

cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

Runtime: 32 ms

Memory Usage: 18.9 MB

 1 class Solution {
 2     func minCostClimbingStairs(_ cost: [Int]) -> Int {
 3         var f: [Int] = []
 4         f.append(cost[0])
 5         for i in 1...(cost.count + 1) {
 6             var one = f[i - 1]
 7             var two = 0
 8             var now = 0
 9             if i - 2 < 0 {
10                 two = 0
11             } else {
12                 two = f[i - 2]
13             }
14             if i >= cost.count {
15                 now = 0
16             } else {
17                 now = cost[i]
18             }
19             f.append(min(one + now, two + now))
20         }
21         return min(f[cost.count], f[cost.count + 1])
22     }
23 }

32ms

 1 class Solution {
 2     func minCostClimbingStairs(_ cost: [Int]) -> Int {
 3         if cost.count == 1 {
 4             return cost[0]
 5         }
 6         if cost.count == 2 {
 7             return min(cost[0], cost[1])
 8         }
 9         
10         var result = Array(repeating: 0, count: cost.count+1)
11         result[0] = 0
12         result[1] = 0
13         for i in 2...cost.count {
14             result[i] = min(result[i-2] + cost[i-2], result[i-1] + cost[i-1])
15         }
16         return result[cost.count]
17     }
18 }

36ms

 1 class Solution {
 2     
 3     func minCostClimbingStairs(_ cost: [Int]) -> Int {
 4         var result1 = cost[0]
 5         var result2 = cost[1]
 6         
 7         for i in 2 ..< cost.count {
 8             var base = min(result1, result2)
 9             result1 = result2
10             result2 = cost[i] + base
11         }
12         
13         return min(result1, result2)        
14     }
15 }

40ms

 1 class Solution {
 2     func minCostClimbingStairs(_ cost: [Int]) -> Int {
 3         var step1 = 0, step2 = 0
 4         for i in cost.indices.dropFirst(2) {
 5             let step3 = min(step1 + cost[i - 2], step2 + cost[i - 1])
 6             step1 = step2
 7             step2 = step3
 8         }
 9         return min(step1 + cost.dropLast().last!, step2 + cost.last!)
10     }
11 }

48ms

 1 class Solution {
 2     func minCostClimbingStairs(_ cost: [Int]) -> Int {
 3         var minCost = cost
 4         for i in 2 ..< cost.count{
 5             minCost[i] += min(minCost[i-1], minCost[i-2])
 6         }
 7         
 8         return min(minCost[cost.count-1], minCost[cost.count-2])
 9     }
10 }

64ms

 1 class Solution {
 2     func minCostClimbingStairs(_ cost: [Int]) -> Int {
 3         let n = cost.count
 4         var value1 = cost[0]
 5         var value2 = cost[1]
 6         for i in 2..<n {
 7             (value2, value1) = (min(value2, value1) + cost[i], value2)
 8         }
 9         return min(value1, value2)
10     }
11 }