Commit 91ea572
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -1,5 +1,5 @@ | |||
| 1 | 1 | /* | |
| 2 | - 997.词典中最长的单词 | ||
| 2 | + 720.词典中最长的单词 | ||
| 3 | 3 | 给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词， | |
| 4 | 4 | 该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案， | |
| 5 | 5 | 则返回答案中字典序最小的单词。 | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,36 @@ | |||
| 1 | + /* | ||
| 2 | + 746. 使用最小花费爬楼梯 | ||
| 3 | + 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。 | ||
| 4 | + 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。 | ||
| 5 | + 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。 | ||
| 6 | + | ||
| 7 | + 示例: | ||
| 8 | + | ||
| 9 | + 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] | ||
| 10 | + 输出: 6 | ||
| 11 | + 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。 | ||
| 12 | + | ||
| 13 | + */ | ||
| 14 | + /* | ||
| 15 | + 思路： | ||
| 16 | + 到达低i阶楼梯有两种情况，第一种是由第i - 2阶楼梯跨两步直接到达第i阶，第二种是有第i - 1阶楼梯跨一步 | ||
| 17 | + 到达第i阶楼梯。所以最后走完所有楼梯，可以由第costSize - 2阶跨两步到达顶端，也可以由第costSize - 1 | ||
| 18 | + 阶跨一步到达顶端。取两者的较小代价即可。 | ||
| 19 | + */ | ||
| 20 | + class Solution { | ||
| 21 | + public: | ||
| 22 | + int minCostClimbingStairs(vector<int>& cost) { | ||
| 23 | + int costSize = cost.size(); | ||
| 24 | + //分别代表到达第index - 2、index - 1需要的代价 | ||
| 25 | + int firstRes = cost[0], secondRes = cost[1]; | ||
| 26 | + for(int index = 2; index < costSize; ++index) | ||
| 27 | + { | ||
| 28 | + //到达第index所需要的代价 == min（到达index - 2代价，到达index - 1代价）+ 跨上第index需要的代价 | ||
| 29 | + int tempRes = min(firstRes, secondRes) + cost[index]; | ||
| 30 | + firstRes = secondRes; | ||
| 31 | + secondRes = tempRes; | ||
| 32 | + } | ||
| 33 | + //第costSize - 2阶跨两步到达顶端，也可以由第costSize - 1阶跨一步到达顶端。取两者的较小代价即可。 | ||
| 34 | + return min(firstRes, secondRes); | ||
| 35 | + } | ||
| 36 | + }; | ||
0 commit comments