算法——贪心

「贪心的本质是选择每一阶段的局部最优，从而达到全局最优」

贪心无套路

1. 分发饼干

贪心策略：

（1）局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

（2）局部最优就是小饼干喂给胃口小的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

代码实现：

// 冒泡排序
void sort(int *a, int len) {
    int flag = 1;
    for (int i = len - 1; flag && i > 0; i--) {
        flag = 0;
        for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                flag = 1;
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp; 
            }
        }
    }
}
 
int findContentChildren(int *g, int gSize, int *s, int sSize) {
    sort(g, gSize);
    sort(s, sSize);
    int j = 0;
    int sum = 0;
    for (int i = 0; i < gSize; i++) {
        while (j < sSize && s[j] < g[i]) {
            j++;
        }
        if (j < sSize) {
            sum++;
            j++;
        }
    }
    return sum;
}

2. 摆动序列

贪心策略：

「局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值」

「整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列」

「实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）」

代码实现：

int wiggleMaxLength(int *nums, int numsSize) {
    if (numsSize <= 1) {
        return numsSize;
    }
    int now = 0; // 当前一对峰值
    int pre = 0; // 前一对峰值
    int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
    for (int i = 1; i < numsSize; i++) {
        now = nums[i] - nums[i - 1];
        // 出现峰值
        if ((now > 0 && pre <= 0) || (pre >= 0 && now < 0)) {
            result++;
            pre = now;
        }
    }
    return result;
}

3. 最大子数组和

暴力解法：超时

int maxSubArray(int *nums, int numsSize) {
    int result = INT32_MIN;
    int count = 0;
    for (int i = 0; i < numsSize; i++) { // 设置起始位置
        count = 0;
        for (int j = i; j < numsSize; j++) { // 每次从起始位置i开始遍历寻找最大值
            count += nums[j];
            result = count > result ? count : result;
        }
    }
    return result;
}

动规五步曲：

• 确定dp数组（dp table）以及下标的含义

dp[i]：以 i 结尾的最大连续子序列和为dp[i]

• 确定递推公式（容斥原理）

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和

• nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

#define max(a, b) ((a) > (b) ? (a) : (b))
 
int maxSubArray(int *nums, int numsSize) {
    if (numsSize == 0) { // 特殊情况
        return 0;
    }
    int dp[numsSize];
    dp[0] = nums[0];
    int result = dp[0];
    for (int i = 1; i < numsSize; i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移方程
        result = max(result, dp[i]); // result 保存dp[i]的最大值
    }
    return result;
}

贪心策略：

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小

全局最优：选取最大“连续和”

int maxSubArray(int *nums, int numsSize) {
    int result = INT32_MIN;
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        count += nums[i];
        if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            result = count;
        }
        if (count <= 0) {
            count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
    }
    return result;
}

4. 买卖股票的最佳时机||

贪心策略：

「局部最优：收集每天的正利润，全局最优：求得最大利润」

int maxProfit(int *prices, int pricesSize) {
    int minProfit = prices[0];
    int result = 0;
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] > minProfit) {
            result += prices[i] - minProfit;
            minProfit = prices[i];
        }
        if (prices[i] < minProfit) {
            minProfit = prices[i];
        }
    }
    return result;
}

5. 跳跃游戏

贪心策略：

「贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点」

bool canJump(int *nums, int numsSize) {
    int cover = 0;
    if (numsSize == 1) {
        return true;
    }
    for (int i = 0; i <= cover; i++) {
        cover = cover > i + nums[i] ? cover : i + nums[i];
        if (cover >= numsSize - 1) {
            return true;
        }
    }
    return false;
}

6. 跳跃游戏||

贪心策略：

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数

• 若当前覆盖最远距离下标不是是终点，步数就加一，还需要继续走。
• 若当前覆盖最远距离下标就是是终点，步数不用加一，结束循环返回结果

#define max(a, b) ((a) > (b) ? (a) : (b))
int jump(int* nums, int numsSize) {
    if (numsSize == 1) {
        return 0;
    }
    int curDistance = 0; // 当前覆盖最远距离下标
    int ans = 0; // 记录走的最大步数
    int nextDistance = 0; // 下一步覆盖最远距离下标
    for (int i = 0; i < numsSize; i++) {
        nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖最远距离下标
        if (i == curDistance) { // 遇到当前覆盖最远距离下标
            if (curDistance != numsSize - 1) { // 如果当前覆盖最远距离下标不是终点
                ans++; // 需要走下一步
                curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了）
                if (nextDistance >= numsSize - 1) { // 下一步的覆盖范围已经可以达到终点，结束循环
                    break;
                }
            } else { // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
                break;
            }
        }
    }
    return ans;
}

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

贪心策略：

        局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大

        如果将负数都转变为正数了，K依然大于0

        局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大，全局最优：整个 数组和 达到最大

int find_min(int *nums, int numsSize) {
    int min = nums[0];
    int ind = 0;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < min) {
            min = nums[i];
            ind = i;
        }
    }
    return ind;
}
 
int numsSum(int *nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    return sum;
}
 
int largestSumAfterKNegations(int *nums, int numsSize, int k) {
    while (k > 0) {
        int min_ind = find_min(nums, numsSize);
        if (nums[min_ind] >= 0) {
            break;
        }
        if (nums[min_ind] < 0) {
            nums[min_ind] = -nums[min_ind]; 
        }
        k--;
    }
    if (k != 0 && k % 2) {
        int min_ind = find_min(nums, numsSize);
        nums[min_ind] = -nums[min_ind];
    }
    int sum = numsSum(nums, numsSize);
    return sum;
}

8. 加油站

暴力解法：超时

int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
    for (int i = 0; i < costSize; i++) {
        int rest = gas[i] - cost[i]; // 记录剩余油量
        int index = (i + 1) % costSize;
        while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈
            rest += gas[index] - cost[index];
            index = (index + 1) % costSize;
        }
        // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
        if (rest >= 0 && index == i) {            
            return i;
        }
    }
    return -1;
}

贪心策略：

每个加油站的剩余量rest[i]为gas[i] - cost[i]

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum

局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置」

int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
    int curSum = 0;
    int totalSum = 0;
    int start = 0;
    for (int i = 0; i < gasSize; i++) {
        curSum += gas[i] - cost[i];
        totalSum += gas[i] - cost[i];
        if (curSum < 0) {
            start = i + 1; // 起始位置更新为i+1
            curSum = 0; // curSum从0开始
        }
    }
    if (totalSum < 0) { // 说明怎么走都不可能跑一圈
        return -1;
    }
    return start;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/284754