题目列表
3046. 分割数组
3047. 求交集区域内的最大正方形面积
3048. 标记所有下标的最早秒数 I
3049. 标记所有下标的最早秒数 II
一、分割数组
这题简单的思维题,要想将数组分为两个数组,且分出的两个数组中数字不会重复,很显然一个数字出现次数最多两次,代码如下
class Solution {
public:bool isPossibleToSplit(vector<int>& nums) {unordered_map<int,int>mp;for(auto x:nums)if(++mp[x]>2)return false;return true;}
};
二、求交集区域内的最大正方形面积
直接暴力枚举出所有两个矩阵的交集的正方形面积,求解出最大值,代码如下
class Solution {
public:long long largestSquareArea(vector<vector<int>>& bLeft, vector<vector<int>>& tRight) {int n=bLeft.size(),w=0;for(int i=1;i<n;i++){for(int j=i-1;j>=0;j--){//挑选四个直线,围成交集区域int x_l=max(bLeft[i][0],bLeft[j][0]);int x_r=min(tRight[i][0],tRight[j][0]);int y_top=min(tRight[i][1],tRight[j][1]);int y_bottom=max(bLeft[i][1],bLeft[j][1]);if(x_l<x_r&&y_top>y_bottom){//确保会有交集w=max(w,min(x_r-x_l,y_top-y_bottom));}} }return 1LL*w*w;}
};
三、标记所有下标的最早秒数I
题目问最早秒数,我们正常来说都会想到贪心 / 从小到大枚举验证,其中贪心,大家可以去试着想想,因为需要从左往右遍历时间,而我们不知道后面changeIndices[]的情况,所以就不能去决定这一步去做什么操作会比较好,也就很难去贪心。
那么我们来看看枚举验证行不行?一旦数据不好,估计得验证O(n)次,大概率会超时,所以我们要降低时间复杂度,怎么做?--- 二分
1、是否满足二分条件,即单调性?
根据题目所给的条件,我们知道时间越多,我们越有可能将nums[i]减为零,越有可能标记所有下标,即秒数越多越能满足条件,符合单调性,可以二分
2、如何验证是否能在k秒内标记所有下标,即bool check(int k)函数如何写?(如果下面的内容不理解,可以先看看下面加粗的内容)
首先,由于changeIndices[]是不可预知的,即标记操作是不可控的,所以我们优先考虑什么时候标记下标的问题,根据贪心,我们肯定是越晚标记下标越好,这样会有更多的时间将nums[i]减为零,所以我们要知道每个下标的最晚标记时间
然后在来考虑是否能在下标 i 的最晚标记时间之前,将nums[i]减为零,这个就很简单了,我们只要维护一个cnt来记录到目前为止有多少时间,然后在到达某个最晚标记时间时,如果cnt>=nums[i],cnt = cnt - nums[i],否则直接返回false,如果所有下标都能被标记就返回true (很显然check函数的时间复杂度为O(n),所以暴力枚举会超时,需要二分)
如果大家不是很理解,可以将这题转换成考试来看,即一共有n门课程,nums[i]表示第 i 门课程的复习天数,changeIndices[i]表示第 i 天进行考试的课程,问复习完并考完所有课程的最少天数是多少?相信经历了这么多年考试的你们,会更容易理解复习和考试的关系(doge)
代码如下
/*
将问题转换成一共有n门课程,第i门课程的复习时间为nums[i]天
changeIndices[i]课程的考试时间为第i天
复习并考完所有课程的最小时间由于考试时间是固定的,我们需要优先考虑考试时间
=> 考试时间越靠后,就会有更加充分的时间用来复习
=> 具有单调性
=> 可以二分check函数如何去判断是否能复习考完所有的考试?
1、贪心,我们把每门课程的考试时间尽可能往后拖延 last[]记录每门课程的最迟考试时间
2、如果考试数目<=课程数,return false; // 可以优化的点否则我们从前往后遍历天数,优先复习考试时间近的科目,看能否在考试之前完成复习
*/class Solution {
public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();auto check=[&](int k)->bool{vector<int>last(n,-1); // 记录下标i的最晚标记时间,即最晚考试时间for(int i=0;i<k;i++)last[changeIndices[i]-1]=i;for(auto x:last)if(x<0) // 表示有的下标没有被标记的时间,即有的课程没有考试return false;int cnt = 0;for(int i=0;i<k;i++){int idx = changeIndices[i] - 1;if(last[idx]==i){//表示下标idx到了最后的被标记的时间,即课程到了考试的最后截止时间cnt-=nums[idx];if(cnt<0) return false;//没有足够的时间将nums[idx]置为0,即没有足够的时间复习课程}else{cnt++;}}return true;};int l=1,r=m;while(l<=r){int mid = l+(r-l)/2;if(check(mid)) r=mid-1;else l=mid+1;}return l>m?-1:l;}
};
四、标记所有下标的最早秒数II
有情提醒一下: 该题和第三题的题目并不一样。
在这题中,操作变得更加复杂了,但其实我们还是可以借鉴第三题的思路:
首先,这题依旧能够二分,因为时间越多,越有可能标记所有下标,但是check函数的思路不一样了,我们要优先考虑清零操作,因为它是不可控的(为了方便描述,这里将题目中的几个操作分别称为减一、清零、标记)。
【如果下面的内容看不太明白,依旧可以带入上一题说的考试模型,帮助你理解---减一操作:花费一天复习一门课,清空操作:花费一天速通一门课,标记:选择一天用来考试】
1)这里就要讨论一下:清零操作和减一操作什么时候用比较合适?
1、如果nums[i]用过减一操作,还需要用清零操作吗?没必要,因为如果能清零,就没必要在花多余的时间进行减一,可以将多出的时间给其他的nums[j]
2、如果nums[i]用过清零操作,也就不需要在进行减一操作了
结论:对于nums[i]要么执行清零操作,要么就执行减一操作,不能混用
2)根据贪心:我们肯定是能清零就尽量的去执行清零,让被清零的nums[i]有更多的时间被减为0
1、清零操作是越早越好还是越晚越好?肯定是越早越好,因为我们还需要有多余的时间去标记,所以我们需要从后往前遍历,去看是否有多余的时间去标记下标,所以我们要记录每个下标的最早清零时间
2、什么时候不需要用清零操作?
- nums[i]==0时,不需要
- nums[i]==1时,也不需要,因为减一操作也能做到清零,且可以在任意时间执行
除了上面的两种情况,还有一种特殊的情况,即用完清零操作之后就没时间进行标记了,这里我们不是只能进行对 i 下标进行nums[i]次减一操作,而是可以看之前进行清空操作的下标中nums[j]的最小值 是否 比nums[i]小,如果小,那么显然我们可以对 j 下标进行nums[j]次减一操作,同时nums[i]就会有时间进行清零和标记,这样的方案显然会更优----反悔贪心
我们从后往前遍历,同时维护用来标记/减一的时间cnt 和 需要减一和标记的总时间sum(都不包含进行清零操作的下标的标记时间)具体如何维护看下面的代码。
class Solution {
public:int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {int n=nums.size(),m=changeIndices.size();long long total = n;for(auto x:nums) total += x; vector<int>first_d(n,-1);for(int i=m-1;i>=0;i--)first_d[changeIndices[i]-1]=i;auto check=[&](int k)->bool{priority_queue<int,vector<int>,greater<int>> q;int cnt = 0;// 减一复习并考试的课程的所有时间long long slow = total;//记录减一操作的nums[i]及其标记需要的时间,一开始默认全用减一操作for(int i=k-1;i>=0;i--){int idx=changeIndices[i]-1;if(nums[idx]<=1||i!=first_d[idx]){cnt++;continue;}if(cnt==0){if(q.empty()||nums[idx]<=q.top()){//只能进行减一操作cnt++;continue;}slow += q.top()+1;q.pop();cnt += 2;}slow -= nums[idx]+1;cnt--;q.push(nums[idx]);}return cnt>=slow;};int l=1,r=m;while(l<=r){int mid=l+(r-l)/2;if(check(mid)) r=mid-1;else l=mid+1;}return l>m?-1:l;}
};