网站推广技巧和方法,企业网站建设方案论文,网站维护中怎么解决,南宁网红打卡景点题目列表
3046. 分割数组
3047. 求交集区域内的最大正方形面积
3048. 标记所有下标的最早秒数 I
3049. 标记所有下标的最早秒数 II
一、分割数组 这题简单的思维题#xff0c;要想将数组分为两个数组#xff0c;且分出的两个数组中数字不会重复#xff0c;很显然一个数…题目列表
3046. 分割数组
3047. 求交集区域内的最大正方形面积
3048. 标记所有下标的最早秒数 I
3049. 标记所有下标的最早秒数 II
一、分割数组 这题简单的思维题要想将数组分为两个数组且分出的两个数组中数字不会重复很显然一个数字出现次数最多两次代码如下
class Solution {
public:bool isPossibleToSplit(vectorint nums) {unordered_mapint,intmp;for(auto x:nums)if(mp[x]2)return false;return true;}
};
二、求交集区域内的最大正方形面积 直接暴力枚举出所有两个矩阵的交集的正方形面积求解出最大值代码如下
class Solution {
public:long long largestSquareArea(vectorvectorint bLeft, vectorvectorint tRight) {int nbLeft.size(),w0;for(int i1;in;i){for(int ji-1;j0;j--){//挑选四个直线围成交集区域int x_lmax(bLeft[i][0],bLeft[j][0]);int x_rmin(tRight[i][0],tRight[j][0]);int y_topmin(tRight[i][1],tRight[j][1]);int y_bottommax(bLeft[i][1],bLeft[j][1]);if(x_lx_ry_topy_bottom){//确保会有交集wmax(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来记录到目前为止有多少时间然后在到达某个最晚标记时间时如果cntnums[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(vectorint nums, vectorint changeIndices) {int nnums.size(),mchangeIndices.size();auto check[](int k)-bool{vectorintlast(n,-1); // 记录下标i的最晚标记时间即最晚考试时间for(int i0;ik;i)last[changeIndices[i]-1]i;for(auto x:last)if(x0) // 表示有的下标没有被标记的时间即有的课程没有考试return false;int cnt 0;for(int i0;ik;i){int idx changeIndices[i] - 1;if(last[idx]i){//表示下标idx到了最后的被标记的时间即课程到了考试的最后截止时间cnt-nums[idx];if(cnt0) return false;//没有足够的时间将nums[idx]置为0即没有足够的时间复习课程}else{cnt;}}return true;};int l1,rm;while(lr){int mid l(r-l)/2;if(check(mid)) rmid-1;else lmid1;}return lm?-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(vectorint nums, vectorint changeIndices) {int nnums.size(),mchangeIndices.size();long long total n;for(auto x:nums) total x; vectorintfirst_d(n,-1);for(int im-1;i0;i--)first_d[changeIndices[i]-1]i;auto check[](int k)-bool{priority_queueint,vectorint,greaterint q;int cnt 0;// 减一复习并考试的课程的所有时间long long slow total;//记录减一操作的nums[i]及其标记需要的时间一开始默认全用减一操作for(int ik-1;i0;i--){int idxchangeIndices[i]-1;if(nums[idx]1||i!first_d[idx]){cnt;continue;}if(cnt0){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 cntslow;};int l1,rm;while(lr){int midl(r-l)/2;if(check(mid)) rmid-1;else lmid1;}return lm?-1:l;}
};
