leetcode weekly contes 350

第四题是个好题目，可以转换为背包问题，确实比较少见的思维题目。

6901. 总行驶距离

卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。

该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。

返回卡车可以行驶的最大距离。

注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。

示例 1：

输入：mainTank = 5, additionalTank = 10
输出：60
解释：
在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。
在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。
总行驶距离为 60km 。

示例 2：

输入：mainTank = 1, additionalTank = 2
输出：10
解释：
在用掉 1 升燃料后，主油箱变为空。
总行驶距离为 10km 。

提示：

1 <= mainTank, additionalTank <= 100

地址

https://leetcode.cn/contest/weekly-contest-350/problems/total-distance-traveled/

题意

模拟

思路

简单做法直接模拟即可，直接按照题意模拟，每次减少 $5$ 就增加 $1$，感觉有点类似于换酒瓶的游戏，每此喝掉 $3$ 瓶就可以换 $1$ 瓶，问最多可以喝多少瓶。
数学解法：感觉就是小学奥数经典的喝汽水换瓶的问题，每消耗$5$ 升油就奖励一瓶，等价于 $4$ 升油可以换 $1$ 升油，但最多可以换 $additionalTank$ 次，但是最后一次不能再换，因为此时 $additionalTank$ 已经为 $0$。但在换瓶子游戏中，最后一次还可以换。
复杂度分析：

时间复杂度：$O(\min(n,m))$，$n,m$ 分别表示给定的元素。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int distanceTraveled(int mainTank, int additionalTank) {
        int res = 0;
        while (mainTank > 0) {
            if (mainTank >= 5) {
                res += 50;
                mainTank -= 5;
                if (additionalTank > 0) {
                    additionalTank--;
                    mainTank++;
                }
            } else {
                res += mainTank * 10;
                mainTank = 0;
            }
        }
        return res;
    }
};

class Solution {
public:
    int distanceTraveled(int mainTank, int additionalTank) {
        return (mainTank + min(additionalTank, (mainTank - 1) / 4)) * 10;
    }
};

6890. 找出分区值

给你一个正整数数组 nums 。

将 nums 分成两个数组：nums1 和 nums2 ，并满足下述条件：

数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。
两个数组都非空。
分区值最小。

分区值的计算方法是 |max(nums1) - min(nums2)| 。

其中，max(nums1) 表示数组 nums1 中的最大元素，min(nums2) 表示数组 nums2 中的最小元素。

返回表示分区值的整数。

示例 1：

输入：nums = [1,3,2,4]
输出：1
解释：可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4] 。
- 数组 nums1 的最大值等于 2 。
- 数组 nums2 的最小值等于 3 。
分区值等于 |2 - 3| = 1 。
可以证明 1 是所有分区方案的最小值。

示例 2：

输入：nums = [100,1,10]
输出：9
解释：可以将数组 nums 分成 nums1 = [10] 和 nums2 = [100,1] 。 
- 数组 nums1 的最大值等于 10 。 
- 数组 nums2 的最小值等于 1 。 
分区值等于 |10 - 1| = 9 。 
可以证明 9 是所有分区方案的最小值。

提示：

2 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-350/problems/find-the-value-of-the-partition/

题意

排序

思路

我们注意到分为两个序列，且分别取出序列中的最大值与最小值，对数组按照从小到大排序，对于任意的 $nums[i], num[i+1]$ 我们总可以按照如下划分：
- $nums[0\cdots i]$ 划分为一个子数组；
- $nums[i+1\cdots n-1]$ 划分为一个子数组；
- 上述数组的分区值的得分为 $nums[i+1] - nums[i]$;
根据上述推论可以知道，我们可以知道区分值的最小值可能为任意相邻元素的最小值
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(\log n)$。

代码

class Solution {
public:
    int findValueOfPartition(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = nums.back();
        for (int i = 1; i < nums.size(); i++) {
            res = min(res, nums[i] - nums[i - 1]);
        }
        return res;
    }
};

6893. 特别的排列

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余后返回。

示例 1：

输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。

示例 2：

输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。

提示：

2 <= nums.length <= 14
1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-350/problems/special-permutations/

题意

状态压缩 +动态规划

思路

力扣中类似的题目非常多，找到类似动态规划题目，通过枚举二进制状态压缩即可得到当前状态下的最优解
设 $dp[mask][i]$ 表示以$mask$ 构成的子数组，且以 $i$ 为结尾子序列的数目，则此时可以得到递推公式如下：
$$
dp[mask][i] = dp[mask][i] + dp[mask\oplus2^j][j] \quad if i, j \in mask
$$
复杂度分析：

时间复杂度：$O(2^n \times n^2)$，其中 $n$ 为给定的数组的长度；
空间复杂度：$O(n)$，其中 $n$ 为数组的长度；

代码

class Solution {
public:
    int specialPerm(vector<int>& nums) {
        long long mod = 1e9 + 7;
        long long res = 0;
        int n = nums.size();
        vector<vector<int>> dp(1 << n, vector<int>(n));
        vector<vector<int>> cnt(n);
        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    if (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0) {
                        cnt[i].emplace_back(j);
                    }
                }
            }
        }
        for (int i = 1; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    for (int k : cnt[j]) {
                        if (i & (1 << k)) {
                            dp[i][j] = (dp[i][j] + dp[i ^ (1 << j)][k]) % mod;
                        }
                    }
                }
            }
        }
        return accumulate(dp[(1 << n) - 1].begin(), dp[(1 << n) - 1].end(), 0LL) % mod;
    }
};

2742. 给墙壁刷油漆

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

一位需要付费的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位免费的油漆匠，刷任意一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠工作时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。

示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。

提示：

1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 106
1 <= time[i] <= 500

地址

https://leetcode.cn/contest/weekly-contest-350/problems/painting-the-walls/

题意

背包问题

思路

背包问题，设每个背包的体积为 $time[i] + 1$, 选择代价最少的背包使得体积大于等于 $n$ 且使得代价最小；
- 按照标准的 $0,1$ 背包做法即可；
设 $f[i][j]$ 表示从前 $i$ 个房间中，花费时间为 $j$ 的最小代价，
- 当第 $i$ 个房间被付费工匠粉刷时的时间为 $time[i]$;
- 当第 $i$ 个房间被免费工匠粉刷时的耗费的时间为 $-1$;
- 这样定义后，耗费的时间可能为 $[-n,n]$, 此时可以得到如下递推公式：
  - $f[i][j-1] = \min(f[i][j-1] ,f[i-1][j])$;
  - $f[i][j + time[i]] = \min(f[i][j + time[i]],f[i-1][j] + cost[i])$
利用上述变换即可。
复杂度分析：

时间复杂度：$O(n^2)$，其中 $n$ 表示给定数组的长度；
空间复杂度：$O(n^2)$，其中 $n$ 表示给定数组的长度；

代码

class Solution {
public:
    constexpr static int INF = 0x3f3f3f3f;
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        vector<int> dp(n + 1, INF);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = n; j >= 0; j--) {
                dp[j] = min(dp[j], dp[max(j - time[i] - 1, 0)] + cost[i]);
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        vector<vector<int>> f(n + 1, vector<int>(2 * n + 1, INT_MAX));
        
        f[0][n] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 2 * n; j++) {
                if (f[i - 1][j] == INT_MAX) continue;
                if (j > 0) {
                    f[i][j - 1] = min(f[i][j - 1], f[i - 1][j]);
                }
                int x = min(2 * n, j + time[i - 1]);
                f[i][x] = min(f[i][x], f[i - 1][j] + cost[i - 1]);
            }
        }
        return *min_element(f[n].begin() + n, f[n].end());
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← 【CMU 15-445/645】lec1 leetcode weekly contes 348 →

扫描二维码，分享此文章