数组刷题总结
数组刷题总结
1.1 二分答案
当题目要求最大化某最小、最小化某最大，考虑使用二分查找。遍历所有可能得key，然后送入check函数进行题目判断
1760. 袋子里最少数目的球
给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次：
选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
class Solution {
public:
bool check(int cost,vector<int>& nums, int maxOperations){
int count=0;
for(int i=0;i<nums.size();i++){
if(nums[i]%cost==0) count+= nums[i]/cost-1;
else count += nums[i]/cost;
}
if(count<=maxOperations) return true;
return false;
}
int minimumSize(vector<int>& nums, int maxOperations) {
int left =1;
int right = 1e9;
while(left<right){
int mid = left+(right-left)/2;
if(check(mid,nums,maxOperations)){
right = mid;
}
else{
left = mid+1;
}
}
return left;
}
};
在本题目中，需要最小化，拆分后剩余的最大值。所以在check函数中，由于除法得到的余数肯定小于被除数，所以直接用数组值除以遍历得到的最大值，得到需要划分的次数，并进行判断。
1552. 两球之间的磁力
在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
class Solution {
public:
bool check(vector<int>& position, int m,int work){
int j =0;
int n = position.size();
int count=0;
for(int i =0;i<n;i++){
if((position[i]-position[j])>=work){
count++;
j = i;
}
}
if(count>=(m-1)) return true;
return false;
}
int maxDistance(vector<int>& position, int m) {
sort(position.begin(),position.end());
int n = position.size();
int left =1;
int right = 1e9;
while(left<right){
int mid = left+(right-left)/2;
if(check(position,m,mid)){
left = mid+1;
}
else{
right = mid;
}
}
return left-1;
}
};
在这道题中，讲题目抽象为，求最大均分长度，在check中判断均分长度最大能分成多少段
1011 D天内运船
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
class Solution {
public:
bool check(vector<int>& weights, int days,int mid){
int n = 0;
int sum=0;
int n1=0;
for(auto c:weights){
sum+=c;
if(mid<c) return false;
if(mid<sum){
n++;
sum=c;
}
}
if(sum<mid) n++;
return n<=days;
}
int shipWithinDays(vector<int>& weights, int days) {
int l = 1;
int r = 1e9;
while(l<r){
int mid = l+(r-l)/2;
if(check(weights,days,mid)){
r = mid;
}
else l = mid+1;
}
return l;
}
};
在这道题目中，主要难点在于check函数中，计算运载天数时，如果船满载，则需要放弃当前货物，下次再运。且船的运载能力不能小于货物大小。
410 分割数组最大值的个数最小
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
class Solution {
public:
bool check(vector<int>& nums, int k,int mid){
int sum1=0;
int n = 1;
for(auto c:nums){
sum1+=c;
if(sum1>mid){
sum1 = c;
n++;
}
}
return n<=k;
}
int splitArray(vector<int>& nums, int k) {
int maxc = 0;
int all =0;
for(auto c:nums){
maxc = max(maxc,c);
all+=c;
}
int l = maxc;
int r = all;
while(l<r){
int mid = l+(r-l)/2;
if(check(nums,k,mid)){
r = mid;
}
else l = mid+1;
}
return l;
}
};
由于这道题要求最大连续字数组和，所以先猜一个数字。在check函数中，求所有值和小于等于这个值的数组数，最后再加上一个大于这个值的数组，就是当前猜的值可以划分的数组数。如果这个数小于要求的k，说明猜的和大了，需要r = mid。
并且由于check函数中包含了等于条件，所以在r=mid中包含了正确答案。
2.1 差分
1094. 拼车
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> bus(1000,0);
for(auto c:trips){
bus[c[1]]+=c[0];
if(c[2]<1000) bus[c[2]]-=c[0];
}
for(int i=0;i<bus.size();i++){
if(i>0) bus[i]+=bus[i-1];
if(bus[i]>capacity) return false;
}
return true;
}
};
通过差分的思想，维护一个差分数组，使得多次对数组内容增删操作可以在数组遍历外部一次实现。从n*m的复杂度变为n+m
1、服务器能耗统计
服务器有三种运行状态:空载、单任务、多任务，每个时间片的能耗的分别为1、3、4;
每个任务由起始时间片和结束时间片定义运行时间:
如果一个时间片只有一个任务需要执行，则服务器处于单任务状态；
如果一个时间片有多个任务需要执行，则服务器处于多任务状态；
给定一个任务列表，请计算出从第一个任务开始，到所有任务结束，服务器的总能耗。
#include<bits/stdc++.h>
using namespace std;
int N = 1e7;
vector<int>vec(N,0);
int n;
int main(){
cin>>n;
int max=0;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
max = max<b? b:max;
vec[a]+=1;
if(b<N) vec[b+1]-=1;
}
for(int i=1;i<vec.size();i++){
vec[i]+=vec[i-1];
}
int ans=0;
int start=0;
for(int i=0;i<=max;i++){
int c = vec[i];
if(vec[i]!=0) start=1;
if(start==1){
if(c==0) ans+=1;
else if(c==1) ans+=3;
else if(c>1) ans+=4;
}
}
cout<<ans;
return 0;
}
在这道题中，每一个时间片段，通过差分加1.。然后再输入数据的过程中，得到工作的最大时长。
3.1 前缀和
3.1.1 连续子数组的和
1031. 两个非重叠子数组的最大和
给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。
长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
子数组是数组的一个 连续 部分。
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
vector<int>pre(nums.size()+1,0);
for(int i=1;i<=nums.size();i++){
pre[i]=pre[i-1]+nums[i-1];
}
int n = nums.size();
int ans=0;
for(int i=0;i+firstLen-1<n;i++){
int fir_sum=0;
int se_sum=0;
int path=0;
int fir_end = i+firstLen-1;
fir_sum = pre[fir_end+1]-pre[i];
for(int j=0;j+secondLen-1<i;j++){
int se_end = j+secondLen-1;
se_sum = pre[se_end+1]-pre[j];
path=fir_sum+se_sum;
ans = ans<path? path:ans;
}
for(int j=fir_end+1;j+secondLen-1<n;j++){
int se_end = j+secondLen-1;
se_sum = pre[se_end+1]-pre[j];
path=fir_sum+se_sum;
ans = ans<path? path:ans;
}
}
return ans;
}
};
思路为通过前缀和，免去相加的循环部分，然后用n2的复杂度爆搜。
2106. 摘水果
在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。
返回你可以摘到水果的 最大总数 。
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int N = 2e5;
int n = fruits.size();
if(n==1&&k!=0) return fruits[0][1];
vector<int>dist(N+1,0);
for(int i=0;i<n;i++){
vector<int> tmp = fruits[i];
int a = tmp[0];
int b = tmp[1];
dist[a] = b;
}
vector<int> presum(N+2,0);
for(int i=1;i<=N+1;i++){
presum[i]+=presum[i-1]+dist[i-1];
}
if(k==0) return dist[startPos];
int ans=0;
for(int x=k;x>=0;x--){
int y = (k - x) / 2;
int l, r;
// x + 2y = k
l = startPos - x, r = startPos + y;
if(l>=0&&r<=N) ans = max(ans, presum[r+1] - presum[l]);
// 2y + x = k
l = startPos - y, r = startPos + x;
if(l>=0&&r<=N) ans = max(ans, presum[r+1] - presum[l]);
}
return ans;
}
};
先求出无限数组的前缀和，然后通过二分法遍历每一种可能得步法。