Leetcode-121&746

发表于 | 分类于

前言

  由于之前算法相关的题目刷的比较少，但是算法题目是目前评价程序员的指标之一，所以接下来要好好练习算法的题目。并且为了熟悉java，因此之后一段时间会用java来写。

Leetcode 121

题目

  原题描述如下如下：

  • Say you have an array for which the ith element is the price of a given stock on day i.
    If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
  • Example 1:
    Input: [7, 1, 5, 3, 6, 4]
    Output: 5
    max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
  • Example 2:
    Input: [7, 6, 4, 3, 1]
    Output: 0
    In this case, no transaction is done, i.e. max profit = 0.

分析

  这道题目我一开始的思路错误。错误的思路的是先遍历一遍找到最小值，然后在最小值之后的点中找到最大值，两者做差为最大利润。错误的原因在于最大利润可能出现在最小值点之前，例如当cost为[2,3,7,1,2]时，最大利润为(7-2)，在“1”之前。

求解

  实现参考“Solution”的思路。分别记录当前的最小价格值和最大利润值。先进行最小价格值的记录，然后进行最大利润值的记录，这样在更新最下价格值之后仍然记录了之前的最大利润值，只有当在当前最小价格之后出现更大的利润之后才能更新。
  代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }
}

  Complexity Analysis：
   Time complexity : $O(n)$
   Space complexity : $O(1)$

Leetcode 746

题目

  原题描述如下：

  • 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].

求解

  求解思路参考“Solution”。这是一个动态规划问题。既然是动态规划问题，应该考虑的是发现它的重叠子问题，并且寻找状态以及状态转移方程。在参考解决代码之后，还原其求解思路如下：
  以Example 2为例，数组为[1,100,1,1,1,100,1,1,100,1],从反向来考虑，要解决这个问题，其最小子问题是只有最后一位的情况，即[1],然后是只有最后两位的情况[100,1]，以此类推。问题的状态就是到第i步时最小的值，只不过是从后向前进行的，而新的问题最小值f[i]是在f[i+1]和f[i+2]已知的情况下要求求解的，所以有f[i] = cost[i] + min(f[i+1],f[i+2])，这样就得到了状态转移方程。
  实现的时候定义f1和f2分别记录f[i+1]和f[i+2],然后用f0作为每轮更新的f[i]，之后只需要三者逐次更替即可。
  代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int f1 = 0, f2 = 0;
        for (int i = cost.length - 1; i >= 0; --i) {
            int f0 = cost[i] + Math.min(f1, f2);
            f2 = f1;
            f1 = f0;
        }
        return Math.min(f1, f2);
    }
}

  Complexity Analysis：
   Time complexity : $O(n)$
   Space complexity : $O(1)$

小结

  121和746是Array中两个easy的题目，但是做起来还是有点困难，看来练习是很必要的。