LeetCode刷题笔记(一): 贪心

贪心算法的核心思想：局部最优以实现全局最优。

一、分配问题

题目：分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

解答：

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = n - 1; i > 0; --i) {
            if (ratings[i] < ratings[i - 1]) {
                candies[i - 1] = max(candies[i - 1], candies[i] + 1);
            }
        }
        return accumulate(candies.begin(), candies.end(), 0);
    }
 };

提示：两次遍历，每次只用关注相邻的一边即可。

二、区间问题

题目：无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。
注意：只在一点上接触的区间是不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

解答：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b)
             { return a[1] < b[1]; });
        int prev = intervals[0][1];
        int count = 0;
        for (vector<int> interval : intervals) {
            if (interval[0] < prev)
                count++;
            else
                prev = interval[1];
        }
        return count - 1;
    }
};

提示：要做到尽量互不重叠即需要保留end越小越好。

三、练习

题目一：买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润。

解答：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        int prev = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] < prev) {
                prev = prices[i];
                continue;
            }
            sum += (prices[i] - prev);
            prev = prices[i];
        }
        return sum;
    }
};

提示：动态规划 is always right。

题目二：划分字母区间
给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串”ababcc”能够被分为[“abab”, “cc”]，但类似[“aba”, “bcc”] 或[“ab”, “ab”, “cc”]的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是s。
返回一个表示每个字符串片段的长度的列表。

解答：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> hash1(26, -1);
        vector<int> hash2(26, -1);
        vector<vector<int>> intervals;
        intervals.reserve(52);
        int length = s.length();
        for (int i = length - 1; i >= 0; i--) {
            if (hash1[s[i] - 'a'] == -1)
                hash1[s[i] - 'a'] = i;
        }
        for (int i = 0; i < length; i ++) {
            if (hash2[s[i] - 'a'] == -1) {
                hash2[s[i] - 'a'] = i;
                vector<int> interval = {hash2[s[i] - 'a'], hash1[s[i] - 'a']};
                intervals.push_back(interval);
            }
        }
        vector<int> res;
        res.reserve(length);
        int start = intervals[0][0];
        int prev = intervals[0][1];
        for (int i = 1; i < intervals.size(); i ++) {
            if (intervals[i][0] < prev) 
                prev = prev > intervals[i][1] ? prev : intervals[i][1];
            else {
                res.push_back(prev - start + 1);
                start = intervals[i][0];
                prev = intervals[i][1];
            }
        }
        res.push_back(prev - start + 1);
        return res;
    }
};

提示：记录开始和结束位置转化为区间问题。