【力扣周赛】第350场周赛

这篇具有很好参考价值的文章主要介绍了【力扣周赛】第350场周赛。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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的可选方案，该统计方法即再次遍历数组，选择当前未被使用的且满足要求的元素。(整体思想回溯)

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模板网！