LeetCode hot100---贪心算法专题(C++语言)

贪心算法

当前取最优，最终完成全局最优

1、买卖股票的最佳时机

（1）题目描述以及输入输出

(1)题目描述:
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

 
(2)输入输出描述：
输入：[7,1,5,3,6,4]
输出：5

关键思路：
遍历价格
取当前价格和最低价格的最小值
当前价格-最低价格，取最大

（2）代码块

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int cost = INT_MAX; // 取当前价格和最低价格的最小值
        int profit = 0;     // 当前价格-最低价格，取最大

        for(int price:prices)
        {
            cost = min(cost,price);
            profit = max(profit,price-cost);
        }
        return profit;
    }
};

2、跳跃游戏

（1）题目描述以及输入输出

(1)题目描述:
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

(2)输入输出描述：
输入：nums = [2,3,1,1,4]
输出：true

关键思路：
遍历数组
当前距离超过最大可达距离，不合理
计算从当前可达的最大距离

（2）代码块

class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        int max_jump = 0;
        for(int i = 0;i<nums.size();++i)
        {
            if(i>max_jump)return false;     // 当前距离超过最大可达距离，不合理
            max_jump = (max_jump,i+nums[i]);// 计算从当前可达的最大距离
        }
        return true;
    }
};

3、跳跃游戏||

（1）题目描述以及输入输出

(1)题目描述:
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

(2)输入输出描述：
输入: nums = [2,3,1,1,4]
输出: 2

关键思路：
遍历数组
计算从当前可达的最大距离
到达上次最远可达距离时更新接下来的最大可达距离并且更新跳跃步数

（2）代码块

class Solution {
public:
    int jump(vector<int>& nums) 
    {
        int maxpos = 0;         // 记录当前最远可达位置
        int end = 0;            // 记录上次跳跃末端
        int num = 0;            // 记录跳跃步数
        for(int i = 0;i<nums.size()-1;++i)
        {
            maxpos = max(maxpos,nums[i]+i); // 当前走过的最大可达距离
            if(i == end)        // 到达上次跳跃的最远距离，需要下次跳跃
            {
                end = maxpos;
                num++;
            }
        }
        return num;
    }
};

4、划分字母区间

（1）题目描述以及输入输出

(1)题目描述:
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

(2)输入输出描述：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]

关键思路：
定义哈希数组记录元素最远出现位置
遍历字符，在哈希表中查找字符出现的最远位置，假如到最远位置

（2）代码块

class Solution {
public:
    vector<int> partitionLabels(string s) 
    {
        vector<int> result;
        int record[26] = {0};
        for(int i = 0;i<s.size();i++)
        {
            record[s[i]-'a'] = i;          // 记录该字母出现的最后位置
        }
        int left = 0,right = 0;
        for(int i = 0;i<s.size();++i)
        {
            right = max(right,record[s[i] - 'a']);	// 更新当前遍历的最远可达距离
            if(i == right)          // 到达当前位置的最右边界
            {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    } 
};