程序员代码面试指南&剑指offer 刷题总结

1 递归

10 斐波那契数列 JZ7

跳台阶 JZ8

矩形覆盖 JZ10

2 贪心策略

变态跳台阶 JZ9

45 把数组排成最小的数 JZ32

14 剪绳子 JZ67

分金条的最小花费CD51

做项目的最大收益问题CD50

3 动态规划

4 图&回溯法

12 矩阵中的路径 JZ65

13 机器人的运动范围 JZ66

补充题目

63 买股票的最佳时机

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if (prices.empty() || prices.size() < 2)
            return 0;
        int min_price = prices[0];  
        int max_profit = prices[1] - min_price;
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] > min_price)
            {
                if (prices[i] - min_price > max_profit)
                {
                    max_profit = prices[i] - min_price;
                }      
            }    
            if (prices[i] < min_price)
                min_price = prices[i];
        }
        return max_profit>0?max_profit:0; //如果是递减数列，则小于0
    }
};