Leetcode 周赛题解 216

5605. 检查两个字符串数组是否相等

「题意」

给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。

数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。

示例1：

输入：word1 = ["ab", "c"], word2 = ["a", "bc"]

输出：true

解释：

word1 表示的字符串为 "ab" + "c" -> "abc"

word2 表示的字符串为 "a" + "bc" -> "abc"

两个字符串相同，返回 true

「提示：」

• 1 <= word1.length, word2.length <= 1000
• 1 <= word1[i].length, word2[i].length <= 1000
• 1 <= sum(word1[i].length), sum(word2[i].length) <= 1000
• word1[i] 和 word2[i] 由小写字母组成

「思路」

按照题意把两个字符串数组里的字符串拼接起来比较是否相同即可。

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        string a, b;
        for(string x: word1) a += x;
        for(string x: word2) b += x;
        return a == b;
    }
};

5606. 具有给定数值的最小字符串

「题意」

小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

x 是 y 的一个前缀；

如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

示例 1：

输入：n = 3, k = 27

输出："aay"

解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

「提示：」

• 1 <= n <= 100000
• n <= k <= 26 * n

「思路」

我们知道要得到字典序最小的解，最前面的字符一定要是最小的才行，后面在这个前提满足的情况再考虑。那么思路就很明确了，我们一位位确定答案。第

位的答案是在后面全选

的情况下能选择的最小值，注意不能选的比

还小。

class Solution {
public:
    string getSmallestString(int n, int k) {
        string ans;
        for(int i = 0; i < n; ++i) {
            char c = 'a' + max(1, k - (n - 1 - i) * 26) - 1;
            ans += c;
            k -= c - 'a' + 1;
        }
        return ans;
    }
};

5607. 生成平衡数组的方案数

「题意」

给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

• 选择删除下标1，剩下的数组为nums = [6,7,4,1]。
• 选择删除下标2，剩下的数组为nums = [6,1,4,1]。
• 选择删除下标4，剩下的数组为nums = [6,1,7,4]。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个平衡数组。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

示例 1：

输入：nums = [2,1,6,4]

输出：1

解释：

删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。

删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。

删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。

删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。

只有一种让剩余数组成为平衡数组的方案。

「提示：」

• 1 <= nums.length <= 100000
• 1 <= nums[i] <= 10000

「思路」

既然只能删除一位数的话，我们就枚举删除哪一位数有可能产生平衡数组。

首先预处理出奇数项前缀和和偶数项前缀和。只要删除第

为后的新数组奇数项前缀和等于偶数项前缀和即可。删除第

为之后，后面的奇偶状态其实互换了。所以只要第

位前的奇数项之和加上第

位后的偶数项之和等于第

位前的偶数项之和加上第

位后的奇数项之和即可。

class Solution {
public:
    vector<int> odd;
    vector<int> even;
    int waysToMakeFair(vector<int>& nums) {
        int n = nums.size();
        if(n <= 2) return n == 1;
        odd.resize(n), even.resize(n);
        odd[1] = nums[1];
        even[0] = even[1] = nums[0];
        for(int i = 2; i < n; ++i) {
            odd[i] = odd[i - 1], even[i] = even[i - 1];
            if(i % 2 == 0) even[i] += nums[i];
            else odd[i] += nums[i];
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            if(((i != 0?odd[i - 1]:0) + even[n - 1] - even[i]) == ((i != 0?even[i - 1]:0) + odd[n - 1] - odd[i])) {
                ++ ans;
            }
        }
        return ans;
    }
};

5608. 完成所有任务的最少初始能量

「题意」

给你一个任务数组 tasks ，其中 tasks[i] = [actual[i], minimum[i]] ：

• actual[i]是完成第i个任务 需要耗费 的实际能量。
• minimum[i]是开始第i个任务前需要达到的最低能量。

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]

输出：8

解释：

一开始有 8 能量，我们按照如下顺序完成任务：

完成第 3 个任务，剩余能量为 8 - 4 = 4 。

完成第 2 个任务，剩余能量为 4 - 2 = 2 。

完成第 1 个任务，剩余能量为 2 - 1 = 1 。

注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

「提示：」

• 1 <= tasks.length <= 100000
• 1 <= actuali <= minimumi <= 10000

「思路」

首先我们只考虑有两个元素

的情况，只要分别考虑

先选和

先选哪种更优即可。

如果

更优的话，我们就把放在前面。这样的话，其实任意两个任务我们都有一种新的优先级关系。定义

为先完成任务

比先完成任务

有更优秀。然后在新的优先级下把所有任务排个序，再按顺序完成即可，这就是最优解。

class Solution {
public:
    pair<int,int> vs[100001];
    int minimumEffort(vector<vector<int>>& tasks) {
        auto cmp = [&](const pair<int,int> &a, const pair<int,int> &b) {
            return max(a.second, a.first + b.second) < max(b.second, b.first + a.second);
        };
        int i = 0, n = tasks.size();
        for(vector<int> item: tasks) {
            vs[i ++] = make_pair(item[0], item[1]);
        }
        sort(vs, vs + n, cmp);
        int ans = 0, res = 0;
        for(int i = 0; i < n; ++i) {
            pair<int,int> x = vs[i];
            if(res < x.second) {
                ans += x.second - res;
                res = x.second;
            }
            res -= x.first;
        }
        return ans;
    }
};