第 122 场双周赛
将数组分成最小总代价的子数组 I
暴力模拟
class Solution {
public:
int minimumCost(vector<int>& nums) {
int ans = nums[0] , n = nums.size();
int res = 1e9;
for(int i = 1 ; i < n ; i ++){
for(int j = i + 1 ; j < n ; j ++){
res = min(res , nums[i] + nums[j]);
}
}
return ans + res;
}
};
判断一个数组是否可以变为有序
把1数目相同的分组排序在判断
class Solution {
public:
bool canSortArray(vector<int>& nums) {
auto f = [&](int x) -> int{
int sum = 0;
for(int i = 0 ; i< 10 ; i ++){
if(x >> i & 1)sum ++;
}
return sum;
};
int n = nums.size();
vector<vector<int>>v;
vector<int> s;
for(int i = 0; i < n ; i ++){
if(i != 0 && f(nums[i]) != f(nums[i - 1])){
sort(s.begin() , s.end());
v.push_back(s);
s.clear();
}
s.push_back(nums[i]);
}
sort(s.begin() , s.end());
v.push_back(s);
int last = -1;
for(int i = 0 ; i < v.size() ; i ++){
auto x = v[i];
// for(auto xx : x)cout << xx << " ";
// cout << endl;
int fir = x[0] , end = x[x.size() - 1];
if(i == 0){
last = end;
}else{
// cout << fir << "---" << end << "---" << last;
// cout << endl;
if(fir < last)return false;
last = end;
}
}
return true;
}
};
最多 K 个重复元素的最长子数组
贪心，等于找最小的合并
class Solution {
public:
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int minimumArrayLength(vector<int>& nums) {
int c = 0;
for(auto x: nums){
c = gcd(c , x);
}
int cnt = count(nums.begin() , nums.end() , c);
if(cnt != 0){
if(cnt % 2)return cnt / 2 + 1;
return cnt / 2;
}
return 1;
}
};
将数组分成最小总代价的子数组 II
实质为求滑动窗口中的前 k 小值，模板
// 两个 multiset 维护滑动窗口中的前 K 小值
struct Magic {
int K;
// st1 保存前 K 小值，st2 保存其它值
multiset<long long> st1, st2;
// sm 表示 st1 中所有数的和
long long sm;
Magic(int K): K(K), sm(0) {
}
// 调整 st1 和 st2 的大小，保证调整后 st1 保存前 K 小值
void adjust() {
while (st1.size() < K && st2.size() > 0) {
long long t = *(st2.begin());
st1.insert(t);
sm += t;
st2.erase(st2.begin());
}
while (st1.size() > K) {
long long t = *prev(st1.end());
st2.insert(t);
st1.erase(prev(st1.end()));
sm -= t;
}
}
// 插入元素 x
void add(long long x) {
if (!st2.empty() && x >= *(st2.begin())) st2.insert(x);
else st1.insert(x), sm += x;
adjust();
}
// 删除元素 x
void del(long long x) {
auto it = st1.find(x);
if (it != st1.end()) st1.erase(it), sm -= x;
else st2.erase(st2.find(x));
adjust();
}
};
class Solution {
public:
long long minimumCost(vector<int>& nums, int K, int dist) {
int n = nums.size();
// 滑动窗口初始化
Magic magic(K - 2);
for (int i = 1; i < K - 1; i++) magic.add(nums[i]);
long long ans = magic.sm + nums[K - 1];
// 枚举最后一个数组的开头
for (int i = K; i < n; i++) {
int t = i - dist - 1;
if (t > 0) magic.del(nums[t]);
magic.add(nums[i - 1]);
ans = min(ans, magic.sm + nums[i]);
}
return ans + nums[0];
}
};
–
