题目列表
3010. 将数组分成最小总代价的子数组 I
3011. 判断一个数组是否可以变为有序
3012. 通过操作使数组长度最小
3013. 将数组分成最小总代价的子数组 II
一、将数组分成最小总代价的子数组I
这道题纯纯阅读理解题，关键在于理解题意。注意：第一个元素作为第一个子数组的代价是必选的！！！我们只要选后面的两个子数组的代价即可。也就是找出两个元素让它们的元素和最小，即找到剩余元素的两个最小值
代码如下
class Solution {
public:
int minimumCost(vector<int>& nums) {
int n=nums.size();
int mn_1=INT_MAX,mn_2=INT_MAX;
for(int i=1;i<n;i++){
if(nums[i]<mn_1) mn_2=mn_1,mn_1=nums[i];
else if(nums[i]<mn_2) mn_2=nums[i];
}
return nums[0]+mn_1+mn_2;
}
};二、判断一个数组是否可以变成有序
这题只要按照题目要求模拟即可，用分组循环的技巧，将数组分为一段段可以交换的区间，然后排序即可，然后判断整个数组是否有序，当然也可以不排序，只要维护每个区间的最大值和最小值即可，然后看前后区间的最大值和最小值是否满足有序。题目说的有序是升序
代码如下
class Solution {
public:
bool canSortArray(vector<int>& nums) {
int n=nums.size();
//分组循环
int i=0;
while(i<n){
int j=i++;
int x=__builtin_popcount(nums[j]);
while(i<n&&x==__builtin_popcount(nums[i]))
i++;
//得到满足条件的区间[j,i)
//排序
sort(nums.begin()+j,nums.begin()+i);
}
for(int i=0;i<n-1;i++)
if(nums[i]>nums[i+1])
return false;
return true;
}
};
//用最大值和最小值维护有序
class Solution {
public:
bool canSortArray(vector<int>& nums) {
int n=nums.size();
//分组循环
int i=0;
int pre_mx=INT_MIN;
while(i<n){
int j=i++;
int x=__builtin_popcount(nums[j]);
int mn=nums[j],mx=nums[j];
while(i<n&&x==__builtin_popcount(nums[i])){
mn=min(mn,nums[i]);
mx=max(mx,nums[i]);
i++;
}
//得到满足条件的区间[j,i)
if(pre_mx>mn) return false;
pre_mx=mx;
}
return true;
}
};
三、通过操作使得数组长度最小
这题说难不难，说简单不简单，关键在于你能否想到"点子"上。
如何去思考？首先这题和数组顺序无关(或者说数组顺序不影响结果)，我们先将数组排序，然后再去结合示例去模拟，看能不能发现什么性质/规律。明确一点1是答案的最小值
我们知道取模运算只会让数字越来越小，那么是用大数%小数好，还是小数%大树好？
(1) 如果小数%大数，必然得到小数，也就是能保证去掉一个元素
=> 1、 如果只有一个最小元素，我们就可以拿它和其他数字依次组合，直到只剩下它，答案为1
=> 2、如果有n个最小元素，我们可以拿其中一个将其他元素删除，然后再进行两两操作，答案为(n+1)/2，在不考虑大数%小数出现更小的非零数的情况下，这个答案必然是最优的(因为我们这样的操作剔除了其他数的干扰，而其他的数只有在出现取模操作出现更小的值的时候才会使得答案为1，其他情况答案就只会变大/不变)。
(2) 如果大数%小数，得到的数字必然比小数小，但是也有可能是0
=> 1、如果得到的结果为0，即有倍数关系，那么长度就必然会加1，我们不希望这样做
=> 2、如果得到的结果不为1，那么得到的数就有可能是最小的数字，就有可能得到最小答案1，即在用(1)得到答案之前，我们还要先判断是否能通过大数%小数得到一个最小数
如何判断？根据取模运算只会让数字越来越小的特性，我们选择让大于最小值的数都%最小值，如果其中一个取模结果大于零，则得到的数必然小于最小值，答案为1，不然答案就是(n+1)/2。
或许你会觉得，我们这样好像不能概括所有大数%小数的情况，即可以出现其他的大数%不是最小值的一个小数得到最小值的情况。
关于这一点，我们来想想我们的做法的本质是什么？就是看数组中的数是否全是最小值的倍数。即我们将数组中出现的情况分为两种：
1、全是最小值的倍数，那么我们无论如何操作，都不可能得到比最小值还小的数，那么我们最优方案就是(1)中的第二种情况，答案为(n+1)/2
2、不全是最小值的倍数，那么我们必然能得到一个比最小值还小的数，答案就是1
代码如下
class Solution {
public:
int minimumArrayLength(vector<int>& nums) {
int n=nums.size();
if(n<=2) return 1;
sort(nums.begin(),nums.end());
for(int i=n-1;i>=1;i--){
if(nums[i]%nums[0])
return 1;
}
int cnt=count(nums.begin(),nums.end(),nums[0]);
return (cnt+1)/2;
}
};四、将数组分成最小总代价的子数组II
这题相较于第一题，除了数据范围变大以外，还多了几个条件，本质就是让我们维护一个长度为dist的滑窗中的最小的k-1个数的和，求最小值即可
注意：第一个元素作为第一个子数组的代价是必选的，我们只要选后面的k-1个子数组的代价即可
这题思路起始很简单，滑窗+维护滑窗中k-1个最小值， 关键在于如何去维护滑窗中k-1个最小值？需要用到对顶堆这个数据结构，简单来说就是用两个堆，一个大堆存放k-1个最小值，一个小堆存放滑窗中其他的数字，然后动态的维护这两个堆就行。
具体代码实现如下
class Solution {
typedef long long LL;
public:
long long minimumCost(vector<int>& nums, int k, int dist) {
k--;
//维护k-1个最小元素的和
LL sum=accumulate(nums.begin()+1,nums.begin()+dist+2,0LL);
//L为大堆，R为小堆，用muiltset模拟实现
multiset<int>L(nums.begin()+1,nums.begin()+dist+2),R;
auto RtoL=[&](){//将R中的元素交给L
int x=*R.begin();
sum+=x;
R.erase(R.find(x));
L.insert(x);
};
auto LtoR=[&](){//将L中的元素交给R
int x=*L.rbegin();
sum-=x;
L.erase(L.find(x));
R.insert(x);
};
while(L.size()>k)
LtoR();
LL ans=sum;
for(int i=dist+2;i<nums.size();i++){
int left=nums[i-dist-1];
auto it=L.find(left);
if(it==L.end()) R.erase(R.find(left));
else {
sum-=left;
L.erase(it);
}
int right=nums[i];
if(right<*L.rbegin()){
L.insert(right);
sum+=right;
}else{
R.insert(right);
}
if (L.size() == k - 1) {
RtoL();
} else if (L.size() == k + 1) {
LtoR();
}
ans=min(ans,sum);
}
return ans+nums[0];
}
};当然也可以用priority_queue来实现对顶堆，这里简单说一下思路：由于我们无法判断优先级队列中的元素，所以当我们要删除一个元素的时候，我们只能记录被删除的元素，直到我们pop堆顶元素时，随便看接下来的数字是否已经被删除，如果被删除我们就继续pop，否则就停止。
