贪心5

贪心5

45. 跳跃游戏 II

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int jump(vector<int> &nums) {
        int n = nums.size();
        // 当前步以内能到达的最右位置
        int right = 0;
        // 当前步再跳一步，能到达的最右位置
        int next = 0;
        // 总共需要跳的次数
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (right < i) {
                // 如果当前位置 i 已经超出了当前步能到的范围，说明需要跳一步了
                res++;      // 增加跳跃次数
                right = next; // 更新当前能到的最远位置
            }
            // 更新下一步能跳到的最远位置
            next = max(next, i + nums[i]);
        }
        return res;
    }
};

1326. 灌溉花园的最少水龙头数目

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minTaps(int n, vector<int> &ranges) {
        // right[i] 表示所有左边界 <= i 的水龙头能灌溉到的最远右边界
        vector<int> right(n + 1, 0);
        for (int i = 0; i <= n; ++i) {
            int start = max(0, i - ranges[i]);
            int end = i + ranges[i];
            right[start] = max(right[start], end);
        }

        // 当前已打开的水龙头能灌溉到的最远位置
        int cur = 0;
        // 再打开一个水龙头能扩展到的最远位置
        int next = 0;
        // 打开的水龙头数量
        int res = 0;

        for (int i = 0; i < n; ++i) {
            // 更新下一步可达到的最远位置
            next = max(next, right[i]);
            // 如果当前水龙头灌溉范围到不了 i+1，就必须开启新水龙头
            if (i == cur) {
                if (next > i) {
                    cur = next;
                    res++;
                } else {
                    return -1; // 无法继续灌溉
                }
            }
        }
        return res;
    }
};

字符串转化

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

// 字符串转化
// 给出两个长度相同的字符串str1和str2
// 请你帮忙判断字符串str1能不能在 零次 或 多次 转化后变成字符串str2
// 每一次转化时，你可以将str1中出现的所有相同字母变成其他任何小写英文字母
// 只有在字符串str1能够通过上述方式顺利转化为字符串str2时才能返回true

using namespace std;

class Solution {
public:
    // 判断 str1 是否可以通过若干次规则转换变为 str2
    // 每次转换可以将 str1 中所有相同字母转换成任意小写字母
    bool canConvert(string str1, string str2) {
        if (str1 == str2) return true;

        // 统计 str2 中不同字符的种类数
        vector<int> map(26, 0);
        int kinds = 0;
        for (char c: str2)
            if (map[c - 'a']++ == 0)
                kinds++;

        // 如果 str2 用满了所有 26 个字母，且 str1 != str2，则必然无法转换
        if (kinds == 26) return false;

        // 在 str1 中，一个字符出现的所有位置，在 str2 中的这些位置的字符必须也是相同
        // 检查 str1 中的每个字符是否映射一致地转换为 str2 中对应字符
        fill(map.begin(), map.end(), -1);  // map[x] 表示字符 x 上次在 str1 出现的位置
        for (int i = 0; i < str1.size(); ++i) {
            // str1 中当前位置的字符，map[cur] 表示当前字符上次在 str1 出现的位置
            // 也就是说str1 中当前 i 位置与 map[cur] 位置是相同字符
            int cur = str1[i] - 'a';
            // 那么 str2 中的这两个位置的字符也必须是相同的，否则返回 false
            if (map[cur] != -1 && str2[map[cur]] != str2[i]) return false;
            map[cur] = i;
        }

        return true;
    }
};

int main() {
    Solution sol;
    string str1 = "aabcc";
    string str2 = "ccdee";
    cout << (sol.canConvert(str1, str2) ? "true" : "false") << endl;  // 输出 true
    return 0;
}

P1809 过河问题

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100001;

int nums[MAXN]; // 存储每个人的过河时间
int dp[MAXN];   // dp[i] 表示前 i+1 个最少用时
int n;

// 返回最小的过河总时间
int minCost() {
    // 按过河时间升序排列
    sort(nums, nums + n);

    // 只有一个人，直接过河
    if (n >= 1) dp[0] = nums[0];
    // 两个人，一起过河，耗时较慢者
    if (n >= 2) dp[1] = nums[1];
    // 三个人：先 1 和 2 过去，1 返回，1 和 3 过去
    if (n >= 3) dp[2] = nums[0] + nums[1] + nums[2];

    for (int i = 3; i < n; ++i) {
        // 两种策略：
        // 1. 最快的人送当前人：dp[i-1] + nums[i] + nums[0]
        // 2. 两个最慢的一起过，对岸最快的返回送：dp[i-2] + nums[0] + 2 * nums[1] + nums[i]
        dp[i] = min(dp[i - 1] + nums[i] + nums[0],
                    dp[i - 2] + nums[0] + 2 * nums[1] + nums[i]);
    }

    return dp[n - 1];
}

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];
        }
        cout << minCost() << '\n';
    }

    return 0;
}

517. 超级洗衣机

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findMinMoves(vector<int> &machines) {
        int n = machines.size();
        int sum = 0;
        for (int x: machines) sum += x;
        // 无法平均分配，直接返回 -1
        if (sum % n != 0) return -1;

        int avg = sum / n;      // 每台洗衣机最终的目标值
        int leftSum = 0;        // 左侧衣物数量总和
        int leftNeed = 0;       // 左侧需要的衣物数量
        int rightNeed = 0;      // 右侧需要的衣物数量
        int bottleNeck = 0;     // 当前点操作的瓶颈值
        int res = 0;            // 最终所需的最少操作次数

        for (int i = 0; i < n; ++i) {
            leftNeed = i * avg - leftSum;
            rightNeed = (n - i - 1) * avg - (sum - leftSum - machines[i]);
            if (leftNeed > 0 && rightNeed > 0) {
                // 两边都需要从当前位置获得衣物
                bottleNeck = leftNeed + rightNeed;
            } else {
                // 只需要满足一边，或者多出来了，取最大绝对值
                bottleNeck = max(abs(leftNeed), abs(rightNeed));
            }
            res = max(res, bottleNeck);
            leftSum += machines[i];
        }

        return res;
    }
};