题目列表

3095. 或值至少 K 的最短子数组 I

3096. 得到更多分数的最少关卡数目

3097. 或值至少为 K 的最短子数组 II

3098. 求出所有子序列的能量和

一、或值至少k的最短子数组I&II

暴力的做法大家都会，这里就不说了，下面我们来看看如何进行优化

其实看到题目，我们就差不多有一个优化的思路：子数组+区间性质 => 滑动窗口，我们需要维护一个或值至少为k的区间（或运算满足数字越多，结果越大的单调性，所以用滑动窗口是可以的）

滑动窗口三个步骤：进窗口，判断是否出窗口以及何时更新答案

进窗口时维护区间或值很简单，只要或上当前元素就行，但是我们如何在元素出窗口时，维护区间的或值呢？或运算的本质就是看bit位上是否有1，我们只要维护一个数据用来记录每个bit位上1出现的次数，就能很快的得出当前区间的或值

代码如下

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = n + 1, or_ = 0;
        int cnt[32] = { 0 };
        for(int l = 0, r = 0; r < n; r++){
            or_ |= nums[r];
            for(int i = 0; i < 32; i++)
                cnt[i] += (nums[r]>>i)&1;
            while(or_ >= k && l <= r){ // 这里一般是不用加l<=r这个条件的，这里是因为k=0会导致越界问题
                ans = min(ans, r-l+1);
                for(int i = 0; i < 32; i++){
                    if((nums[l]>>i)&1){
                        if(--cnt[i]==0)
                            or_ &= (~(1<<i));
                    }
                }
                l++;
            }
        }
        return ans==n+1?-1:ans;
    }
};

这里在提供一种方法(or通用模板)，如下

代码如下

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = INT_MAX;
        vector<pair<int,int>> v;
        for(int i = 0; i < n; i++){
            v.emplace_back(0,i); // 以i位左端点，or_ = 0，后面会让它|nums[i]
            int j = 0;
            for(auto& p:v){
                auto&[or_,left] = p;
                or_ |= nums[i]; // 区间为[left,i]
                if(or_ >= k)
                    ans = min(ans,i-left+1);
                if(v[j].first == or_) // 当or_相等时，保留最靠右的左端点下标
                    v[j].second = left;
                else
                    v[++j]=p;
            }
            v.resize(j+1); // 去重
        }
        return ans == INT_MAX?-1:ans;
    }
};

二、得到更多分数的最少关卡数目

题目说的很复杂，其实很简单，就是模拟，我们只要将数组分为左右两个部分，要求左边部分的得分大于右边部分的得分，问左边部分的最少关卡数(注意：题目要求每个玩家至少要完成一个关卡)代码如下

class Solution {
public:
    int minimumLevels(vector<int>& possible) {
        int s = 0;
        for(auto x:possible)
            s += 2*x-1;
        int n = possible.size();
        for(int i = 0,pre = 0; i < n-1; i++){
            pre += 2*possible[i]-1;
            if(pre > s - pre)
                return i + 1;
        }
        return -1;
    }
};

三、求出所有子序列的能量和

子序列问题一般和顺序无关，这题也一样，我们先给数组排序。问子序列的能量(最小差值)，只可能是相邻元素间的差才可能是子序列的能量(排完序后)，显然该问题是个经典的相邻相关的子序列问题，即需要记录它的上一个数字是多少，再结合选或不选的思想，我们很容易得到下面这样一个递归函数定义

设 dfs(i，j，pre，mn) 表示 从nums[0]~nums[i]中再选j个充当子序列中的元素，其中pre表示上一个选择的元素，mn记录nums[i+1]~nums[n-1]中选出的k-j个数之间的最小差值，返回值表示已选出的数字组成的子序列的能量

递归入口： 

dfs(n-1，k，INT_MAX/2，INT_MAX/2)

递归出口：

• j==0时，返回mn --- 表示当前子序列的能量为mn
• j>i+1时，返回0 --- 剩余元素个数不足j个，不能构成符合要求的子序列，不贡献能量，返回0

递归转移方程：

• 不选当前元素作为子序列元素：dfs(i-1，j，pre，mn) 
• 选当前元素作为子序列元素：dfs(i-1，j-1，nums[i]，min(mn，pre-nums[i]))

dfs(i，j，pre，mn) = dfs(i-1，j，pre，mn) + dfs(i-1，j-1，nums[i]，min(mn，pre-nums[i]))

代码如下

class Solution {
public:
    int sumOfPowers(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        const int MOD = 1e9+7;
        unordered_map<int,unordered_map<int,unordered_map<int,unordered_map<int,int>>>> mp;
        function<int(int,int,int,int)>dfs=[&](int i,int j,int pre,int mn)->int{
            if(j==0) return mn;
            if(j>i+1) return 0;
            if(mp.count(i)&&mp[i].count(j)&&mp[i][j].count(pre)&&mp[i][j][pre].count(mn))
                return mp[i][j][pre][mn];
            int res1 = dfs(i-1,j,pre,mn); // 不选
            int res2 = dfs(i-1,j-1,nums[i],min(mn,pre-nums[i])); // 选
            return mp[i][j][pre][mn]=(res1+res2)%MOD;
        };
        return dfs(n-1,k,INT_MAX/2,INT_MAX/2);
    }
};