关于leetcode个人解题总结:golangleetcode初级爬楼梯买卖股票的最佳时机

第一题 爬楼梯

题目信息

解题思路

对于 n 阶台阶
每次的抉择为一阶或者两阶
残余的台阶数别离为 n - 1 和 n -2
咱们只须要别离求出 n - 1 和 n - 2 别离有多少种计划
再将其相加，便失去了 n 阶台阶的计划

然而很惋惜

运行的工夫太长了，通过不了

思考一下这个思路
咱们会发现
在求 n 阶的计划时，咱们须要别离求 n - 1 和 n - 2 的计划
求 n - 1 的计划时，咱们需要求 n - 2 和 n - 3 的计划
如此
除了求 n 阶计划之外，每个计划都求了两遍以上
咱们能够很显著的留神到
这个数列的实质理论为斐波那契数列
咱们能够将其从递归调用转换为循环叠加
这样，
咱们就失去了官解的第一种解法

代码

func climbStairs(n int) int {
    p, q, r := 0, 0, 1
    for i := 1; i <= n; i++ {
        p = q
        q = r
        r = p + q
    }
    return r
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

复杂度剖析

工夫复杂度：循环执行 n 次，每次破费常数的工夫代价，故渐进工夫复杂度为 O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

优化

第二题 交易股票的最佳时机

题目信息

解题思路

代码

func maxProfit(prices []int) int {
        minPrice :=10000
        maxProfit :=0
        for  i:= 0; i < len(prices); i++ {if prices[i] < minPrice {minPrice = prices[i]
            }else if (prices[i] - minPrice) > maxProfit {maxProfit = prices[i] - minPrice
            }
        }
        return maxProfit
    }