贪心算法

455. 分发饼干

力扣题目链接(opens new window)

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

我的思路是小饼干优先满足小胃口，还有一种是大饼干优先满足大胃口。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0;
        int cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (g[child] <= s[cookie]) {
                child++;
                cookie++;
            } else {
                cookie++;
            }
        }
        return child;
    }
};

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        if (nums.size() == 1) {
            return 1;
        }
        bool hasDiff = false;
        int last = 0;   // -1 0 1
        int length = 1;
        for (int i = 1; i < nums.size(); i++) {
            int currDiff = nums[i] - nums[i - 1];
            if (!hasDiff && currDiff != 0) {
                hasDiff = true;
            }
            int curr = currDiff == 0 ? 0 :
                        (currDiff > 0 ? 1 : -1);
            if (curr != 0 && curr != last) {
                length++;
            }
            last = curr != 0 ? curr : last;
        }
        return length;
    }
};

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

试着用了 DP，貌似还有 $O(\log{n})$ 的解法？

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> sums(nums.size(), 0);
        sums[0] = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            sums[i] = max(sums[i - 1] + nums[i], nums[i]);
            if (sums[i] > maxSum) {
                maxSum = sums[i];
            }
        }
        return maxSum;
    }
};

122. 买卖股票的最佳时机 II

力扣题目链接(opens new window)

给定一个数组，它的第  i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

好多事情，暂时先用 DP 糊了

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<pair<int, int>> dp(prices.size());
        dp[0] = {0, -prices[0]};
        for (int i = 1; i < prices.size(); i++) {
            dp[i].second = max(dp[i - 1].second, dp[i - 1].first - prices[i]);
            dp[i].first = max(dp[i - 1].first, dp[i - 1].second + prices[i]);
        }
        return max(dp[prices.size() - 1].first, dp[prices.size() - 1].second);
    }
};

55. 跳跃游戏

力扣题目链接(opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

我想的是从后往前数，时间复杂度应该是 $O(N)$，还可以用覆盖范围

class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool result = true;
        int i = nums.size() - 2;
        while (i >= 0) {
            if (nums[i] == 0) {
                result = false;
                int j = i - 1;
                while (j >= 0) {
                    if (nums[j] > i - j) {
                        result = true;
                        i = j;
                        break;
                    }
                    j--;
                }
                if (!result) {
                    return false;
                }
            }
            i--;
        }
        return result;
    }
};

45. 跳跃游戏 II

力扣题目链接(opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

class Solution {
public:
    int jump(vector<int>& nums) {
        int currIndex = 0;
        int range = 0;
        int ans = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            range = max(range, i + nums[i]);
            if (i == currIndex) {
                currIndex = range;
                ans++;
            }
        }
        return ans;
    }
};

1005. K 次取反后最大化的数组和

力扣题目链接(opens new window)

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i  并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

以这种方式修改数组后，返回数组可能的最大和。

温习了一下 Lamda 应该怎么写

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b){return a < b;});
        int minAbs = INT_MAX;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            minAbs = min(minAbs, abs(nums[i]));
            if (k > 0 && nums[i] < 0) {
                ans += -nums[i];
                k--;
            } else {
                ans += nums[i];
            }
        }
        if (k % 2 != 0) {
            ans -= 2 * minAbs;
        }
        return ans;
    }
};

134. 加油站

力扣题目链接

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int currLeft = 0;
        int totalLeft = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            totalLeft += gas[i] - cost[i];
            currLeft += gas[i] - cost[i];
            if (currLeft < 0) {
                start = i + 1;
                currLeft = 0;
            }
        }
        if (totalLeft < 0) {
            return -1;
        }
        return start;
    }
};

135. 分发糖果

力扣题目链接(opens new window)

老师想给孩子们分发糖果，有 N  个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

我只想到对于 [2,2] 这样的情况，可以以此为边界划分子问题，答案好精妙

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> vec(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                vec[i] = vec[i  - 1] + 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                vec[i] = max(vec[i], vec[i + 1] + 1);
            }
        }
        int result = 0;
        for (int i = 0; i < vec.size(); i++) {
            result += vec[i];
        }
        return result;
    }
};

860. 柠檬水找零

力扣题目链接(opens new window)

在柠檬水摊上，每一杯柠檬水的售价为  5  美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回  true ，否则返回 false 。

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int fiveCount = 0;
        int tenCount = 0;
        int twentyCount = 0;
        for (int bill : bills) {
            if (bill == 5) {
                fiveCount++;
            } else if (bill == 10) {
                if (fiveCount > 0) {
                    fiveCount--;
                    tenCount++;
                } else {
                    return false;
                }
            } else if (bill == 20) {
                // 10 + 5
                if (tenCount > 0 && fiveCount > 0) {
                    tenCount--;
                    fiveCount--;
                    twentyCount++;
                } else if (fiveCount >= 3) {
                    fiveCount -= 3;
                    twentyCount++;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

406. 根据身高重建队列

没想出来，贪心感觉没有统一的套路，多多练习

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b){
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        list<vector<int>> que;
        for (const vector<int>& p : people) {
            auto it = que.begin();
            int dis = p[1];
            while (dis--) {
                it++;
            }
            que.insert(it, p);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

452. 用最少数量的箭引爆气球

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b){
            return a[1] == b[1] ? a[0] < b[0]: a[1] > b[1];
        });
        int left = INT_MAX, right = INT_MIN, count = 0;
        for (const auto point : points) {
            if (point[0] > right || point[1] < left || left > right) {
                count++;
                left = point[0];
                right = point[1];
            } else {
                left = max(left, point[0]);
                right = min(right, point[1]);
            }
        }
        return count;
    }
};

435. 无重叠区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            return a[0] < b[0];
        });
        if (intervals.empty()) {
            return 0;
        }
        int right = intervals[0][1];
        int count = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < right) {
                count++;
                right = min(intervals[i][1], right);
 } else {
                right = intervals[i][1];
            }
        }
        return count;
    }
};

763. 划分字母区间

力扣题目链接(opens new window)

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int end[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            end[s[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.size(); i++) {
            right = max(right, end[s[i] - 'a']);
            if (i == right) {
                result.push_back(right - left + 1);
                left = right + 1;
            }
        }
        return result;
    }
};

56. 合并区间

力扣题目链接(opens new window)

给出一个区间的集合，请合并所有重叠的区间。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
      sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];
      });
      vector<vector<int>> result;
      if (intervals.empty()) {
        return result;
      }
      result.push_back(intervals[0]);
      for (int i = 1; i < intervals.size(); i++) {
        if (result.back()[1] >= intervals[i][0]) {
          result.back()[1] = max(result.back()[1], intervals[i][1]);
        } else {
          result.push_back(intervals[i]);
        }
      }
      return result;
    }
};

738. 单调递增的数字

力扣题目链接(opens new window)

给定一个非负整数  N，找出小于或等于  N  的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
      string str = to_string(n);
      int index = str.size();
      for (int i = str.size() - 1; i > 0; i--) {
        if (str[i - 1] > str[i]) {
          str[i - 1]--;
          index = i;
        }
      }
      for (int i = index; i < str.size(); i++) {
        str[i] = '9';
      }
      return stoi(str);
    }
};

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

class Solution {
public:
    int result;
    // 0: none; 1: camera; 2: covered
    int traversal(TreeNode* root) {
        if (!root) {
            return 2;
        }
        int left = traversal(root->left);
        int right = traversal(root->right);
        if (left == 2 && right == 2) {
            return 0;
        }
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return 0;
    }
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) {
            result++;
        }
        return result;
    }
};