2739. 总行驶距离
题目描述
描述：卡车有两个油箱。给你两个整数，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
解题思路
难度：简单。
思路：最直观的想法是，使用distance表示可以行驶的最大距离，当主油箱油量小于5时，直接返回mainTank*10，反之当主油箱油量大于等于5时，将distance加以50，再判断副油箱油量，如果副油箱油量大于等于1，则将副油箱油量减去1，同时将主油箱油量减去5再加上1，反之当副油箱油量小于1，则将主油箱油量减去5，最后退出循环后，还需要将distance加上剩余主油箱油量乘以10。
class Solution {
public:
int distanceTraveled(int mainTank, int additionalTank) {
int distance=0;
if(mainTank<5)
return mainTank*10;
while(mainTank>=5)
{
distance+=50;
//有余量
if(additionalTank>=1)
{
additionalTank-=1;
mainTank-=4;
}
//无余量
else
mainTank-=5;
}
distance+=mainTank*10;
return distance;
}
};
总结：模拟，最主要的是注意边界条件。
2740. 找出分区值
题目描述
描述：给你一个 正 整数数组 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
解题思路
难度：中等。
思路：最直观的想法是，找出差值最小的两个数。首先将数组排序，然后遍历一遍求最小差值。
class Solution {
public:
int findValueOfPartition(vector<int>& nums) {
//先排序
sort(nums.begin(),nums.end());
//再找中间两个
int n=nums.size();
int diff=INT_MAX;
for(int i=n-1;i>0;i--)
{
diff=min(diff,nums[i]-nums[i-1]);
}
return diff;
}
};
总结：有时候，题目思路很简单，但是会对题目进行很强的包装，从而产生迷惑性，故此时需要好好分析题目的本质是什么。
2741. 特别的排列
题目描述
描述：给你一个下标从 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
解题思路
难度：中等。
特别的排列：最直观的想法是，状态压缩DP+记忆化搜索。由于包含n个互不相同的整数，故此时数值下标即唯一代表数值，那么我们可以只记录下标，而不用记录具体的数值。由于是全排列，故每一个元素要么为选要么为不选，对于可选的集合，我们可以将集合映射到二进制位运算中进行计算，比如0、2、3对应数值1101。全集为(1<<n)-1，总个数为(1<<n)，将元素从集合中删除是left^(1<<i)，判断集合中是否包含该元素则为(left>>i)&1。即从头到尾遍历数组，并将当前元素从可选集合中删除，然后统计在可选集合中且上一个数是i的可选方案，该统计方法即再次遍历数组，选择当前未被使用的且满足要求的元素。(整体思想回溯)文章来源：https://www.toymoban.com/news/detail-490808.html
const int MOD=1e9+7;
int specialPerm(vector<int>& nums)
{
//只需要记录下标而不需要记录数字
int n=nums.size();
//将集合对应成二进制数字 left表示可选择的集合 初始为全集 1表示可选择
int left=(1<<n)-1;
//1<<n表示一共0~(1<<n)-1个大小的数组 第一维度代表的是数字组合 第二维度代表的是当前元素下标
int memo[1<<n][n];
//记忆化搜索 -1代表未记录过
memset(memo,-1,sizeof(memo));
//返回值是int类型 两个参数是int类型
function<int(int,int)> dfs=[&](int left,int i)->int
{
//递归出口 没有元素可选 即枚举完了 该排列符合
if(left==0)
return 1;
//有记录则直接返回
if(memo[left][i]!=-1)
return memo[left][i];
int ans=0;
//枚举数组下标
for(int j=0;j<n;j++)
{
//(left>>j)&1判断当前位是否是1 即枚举该下标是否用过
if(((left>>j)&1)&&(nums[j]%nums[i]==0||nums[i]%nums[j]==0))
//在left中删除j并继续计算后续
ans=(ans+dfs(left^(1<<j),j))%MOD;
}
memo[left][i]=ans;
return ans;
};
int res=0;
for(int i=0;i<n;i++)
res=(res+dfs(left^(1<<i),i))%MOD;
return res;
}
总结：注意，一般对于集合的元素选择，均可以转换为二进制位运算。文章来源地址https://www.toymoban.com/news/detail-490808.html
到了这里，关于【力扣周赛】第350场周赛的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[LeetCode周赛复盘] 第 348场周赛20230604](https://imgs.yssmx.com/Uploads/2024/02/475012-1.png)
![[LeetCode周赛复盘] 第 359 场周赛20230820](https://imgs.yssmx.com/Uploads/2024/02/671399-1.png)
![[LeetCode周赛复盘] 第 353 场周赛20230709](https://imgs.yssmx.com/Uploads/2024/02/551667-1.png)
