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

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

爬梯子

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 数据格式
自造微博轮子,再爬姐姐和奶奶殿下
自造微博轮子,再爬姐姐和奶奶殿下
|
算法 C++
【每日算法Day 65】你能顺利救出地下城里的公主吗?
【每日算法Day 65】你能顺利救出地下城里的公主吗?
|
机器学习/深度学习 弹性计算 算法
|
Web App开发 小程序 机器人
霸榜日本热搜一周!这个应用让涂鸦从纸上活过来,还能喂吃的,网友玩儿疯了
霸榜日本热搜一周!这个应用让涂鸦从纸上活过来,还能喂吃的,网友玩儿疯了
296 0
|
人工智能 机器人
“机甲战士”外卖小哥现身上海!负重一百斤一口气爬五楼,饿了么回应:落地时间未知
“机甲战士”外卖小哥现身上海!负重一百斤一口气爬五楼,饿了么回应:落地时间未知
211 0
解救被困传销女演员 助人减肥找老婆 蚂蚁森林又现神功能
近日,一篇《女演员被传销组织拘禁30多天 竟因蚂蚁森林幸运逃离》的报道引发了全网热议。网友纷纷表示:蚂蚁森林功能强大,不仅能帮人减肥、找老婆,还能在关键时刻保命!
5437 0