代码随想录算法训练营day31

题目：455_分发饼干（看了题解）

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

对每个孩子 i，都有一个胃口值  g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例  1:

• 输入: g = [1,2,3], s = [1,1]
• 输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

示例  2:

• 输入: g = [1,2], s = [1,2,3]
• 输出: 2
• 解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.

提示：

• 1 <= g.length <= 3 * 10^4
• 0 <= s.length <= 3 * 10^4
• 1 <= g[i], s[j] <= 2^31 - 1

#

算法思想：

贪心算法。每次用最大的饼干s满足胃口最大的小孩g。

给s 和g 排序。

每次选用最大的饼干满足最大的小孩，相当于双指针，i指向小孩g的下标，index 指向 小孩s 的下标。i 用for 循环持续--，index 在满足条件的情况下，动态--。

代码：

class Solution {
public:
    void bubbleSort(vector<int>& vec) {
        for (int i = 0; i < vec.size(); i++) { //进行 n-1 轮排序
            bool flag = false;
            for (int j = 0; j < vec.size() - i - 1;
                 j++) {                    //每躺排序比较 n-i-1 次
                if (vec[j] > vec[j + 1]) { //逆序交换
                    flag = true;           //修改标记位
                    int temp = vec[j + 1];
                    vec[j + 1] = vec[j];
                    vec[j] = temp;
                }
            }
            if (flag == false)
                break;
        }
    }
 
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // g 和 s 递增排序，每次用最大的 s 取满足最大的 g，这时能满足的 g 最多
        bubbleSort(g); // 递增排序
        bubbleSort(s);
 
        //或者直接使用sort 函数排序
        //sort(g.begin(),g.end());
 
        int count = 0; // 记录输出结果
        int index = s.size() - 1;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                count++;
                index--;
            }
        }
        return count;
    }
 };

注意：

1、冒泡排序背下来

2、双指针，一个for循环静态减小，一个满足条件动态减小

题目：53_最大子数组和（看题解了ti'jie）

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

示例:

• 输入: [-2,1,-3,4,-1,2,1,-5,4]
• 输出: 6
• 解释:  连续子数组  [4,-1,2,1] 的和最大，为  6。

#

算法思想：

负数只会拉低总和，因此当连续和结果为负数时，则直接抛弃，从下个元素重新计算连续和。用 result 记录最大值。

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //如果 子串和sum 为负数，抛弃。用 result 记录最大sum
        int sum = 0;
        int result = INT32_MIN; //保存最大子串和
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum >
                result) //这个if
                        //要写在下面的if前面，否则，当序列里全为负数时会出错
                result = sum;
 
            if (sum < 0) //子串和为负数，抛弃，相当于重置起始位置
                sum = 0;
        }
        return result;
    }
};