爬梯子&&卖卖股份的最佳时期(跑路人笔记)

简介: 爬梯子&&卖卖股份的最佳时期(跑路人笔记)

爬梯子

70. 爬楼梯 - 力扣(LeetCode)

image.png

刚开始我准备使用递归来解决问题,因为这个其实就是一个斐波那契数列.


代码如下


class Solution {
public:
    int climbStairs(int n) 
    {
        if(n == 1)
            return 1;
        if(n == 2)
        {
            return 2;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

但是不行


image.png


滚动数组

所以我们就可以用现在的滚动数组来解决问题


代码如下:


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

买卖股票的最佳时机

买卖股票的最佳时机 - 力扣(LeetCode)

image.png



题目意思是给你一个数组, 只能用后面的值减去前面的数组值,返回最大值即可.


暴力法

直接使用时间复杂度为O(n2)的方法代码如下.但是超时.


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int ret = 0;
        int tmp = 0;
        for(int i = 0;i<prices.size();i++)
        {
            for(int j = i+1;j<prices.size();j++)
            {
                tmp = prices[j] - prices[i];
                ret = ret>tmp?ret:tmp;
            }
        }
        return ret;
    }
};



image.png


只遍历一遍

我们先将minprices赋值给105因为prices[i]的最大值是104


image.png


class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int minprices = 1e5;//最大值为1*10^5^
        int ret = 0;
        for(int i =0;i<prices.size();i++)
        {
            minprices = min(minprices,prices[i]);//记录每个节点的最低值
            ret = max(ret,prices[i]-minprices);//用于记录每个节点和前面最低值相减的最大值.
        }
        return ret;
    }
};



我们这个只需要遍历一次因为我们每走过一个节点都会判断他是否比前面的值要小,如果小就记录下来.


这样后面我们在相减的时候就可以直接用当前位置减去前面的最小值而且这样的时候我们赚的是最多的.


再和之前记录的我们能赚的最大值进行比较通过一次遍历我们就可以得到我们想要的最大值了.


相关文章
|
6月前
|
JSON API 数据格式
自造微博轮子,再爬姐姐和奶奶殿下
自造微博轮子,再爬姐姐和奶奶殿下
|
定位技术
国庆七天乐,要猛! ——经典迷宫问题
国庆七天乐,要猛! ——经典迷宫问题
83 0
|
Web App开发 小程序 机器人
霸榜日本热搜一周!这个应用让涂鸦从纸上活过来,还能喂吃的,网友玩儿疯了
霸榜日本热搜一周!这个应用让涂鸦从纸上活过来,还能喂吃的,网友玩儿疯了
295 0
|
编解码 架构师 Java
程序人生 | 春风得意马蹄疾,一日看尽长安花
来自一个大龄程序员的坎坷职业生涯:作者万字自述
673 0
程序人生 | 春风得意马蹄疾,一日看尽长安花
|
算法 搜索推荐
【技术小火车】万万没想到!原来你是这样的算法君?!
据说算法正在统治世界?吓得我瓜子都掉了......
5793 0
|
机器学习/深度学习 人工智能 TensorFlow