Leetcode - 周赛386

本文主要是介绍Leetcode - 周赛386，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一，3046. 分割数组

二，3047. 求交集区域内的最大正方形面积

三，3048. 标记所有下标的最早秒数 I

四，3049. 标记所有下标的最早秒数 II

---

一，3046. 分割数组

将题目给的数组nums分成两个数组，且这两个数组中没有相同的元素，求是否存在这两个数组，即求nums数组中有没有一个元素的出现次数 > 2，如果大于2，说明不论怎么分配总有一个数组含有相同的元素，返回 false，否则返回 true

代码如下：

class Solution {public boolean isPossibleToSplit(int[] nums) {int mx = 0;Map<Integer,Integer> map = new HashMap<>();for(int x : nums){map.put(x, map.getOrDefault(x,0)+1);mx = Math.max(mx, map.get(x));}return mx <= 2;}
}

二，3047. 求交集区域内的最大正方形面积

本题求两个矩阵的交集区域中最大正方形的面积，关键在于求出相交区域的矩阵的长和高：

• 左下角的横坐标（x轴）：两个矩阵左下角最大的横坐标
• 左下角的纵坐标（y轴）：两个矩阵左下角最大的纵坐标
• 右上角的横坐标（x轴）：两个矩阵右上角最小的横坐标
• 右上角的纵坐标（y轴）：两个矩阵右上角最小的横坐标

代码如下：

class Solution {public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {long ans = 0;int n = bottomLeft.length;for(int i=0; i<n; i++){int[] b1 = bottomLeft[i];int[] t1 = topRight[i];for(int j=i+1; j<n; j++){int[] b2 = bottomLeft[j];int[] t2 = topRight[j];int LMx = Math.min(t1[0], t2[0]);int LMn = Math.max(b1[0], b2[0]);int RMn = Math.max(b1[1], b2[1]);int RMx = Math.min(t1[1], t2[1]);int x = Math.min(LMx-LMn, RMx-RMn);if(x > 0)ans = Math.max(ans,(long)x*x);}}return ans;}
}

三，3048. 标记所有下标的最早秒数 I

二分 + 贪心

本题的题目可以转换成一个更加简单易懂的说法 —— 学校考试：

距离学期结束还有 m 天，要复习 n 门课程，第 i 门课程的复习时间是nums[i]，并且每一门课程的考试时间是固定的，由changeIndices数组决定（changIndices[i] 表示可以在第 i 天考第 changIndices[i] 门课程），问要将 n 门课程复习完+考完（考试当天只能用来考试），最少要花费多少时间？

通过读题，会发现直接求答案是非常困难的，那么是否可以通过枚举最终所需的天数来判断它是否够用，如果够用，那么缩减天数，如果不够用，那么增加天数，想到这，自然就会想到二分答案，但是使用二分还有一个前提：要具有单调性，那么本题是否有单调性呢？当然是有的：给的时间越多，复习的时间越充裕，越能够通过考试。

二分是可以的，那么接下来就是判断二分的这个答案是否成立（即如何判断所给的天数是否充足），有两种思考方式，一种从前往后思考，一种从后往前思考，这里只讲第一种思路：

通过上面的分析，我们知道考试的时间越靠后，复习的时间就越多，就越能够通过考试，所以我们需要求出每一门课程的最后一天考试时间，从前往后遍历：

• 如果第 i 天不是某一门课程的最后一天考试天数，那么我们将这一天存起来（即cnt++），cnt 用作之后考试课程的复习天数
• 如果第 i 天是某一门课程的最后一天考试天数，那么先判断我们是否有足够的时间cnt去复习这门课程，如果有，cnt 减去需要复习的天数，如果没有返回 false
• 遍历结束返回 true

画个图理解一下：

 代码如下：

class Solution {public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {int n = nums.length;int m = changeIndices.length;int[] last_test = new int[n];int l = n, r = m;while(l <= r){int mid = (l + r) / 2;if(check(nums, changeIndices, last_test, mid)){r = mid - 1;}else{l = mid + 1;}}return r+1 > m ? -1 : r+1;}boolean check(int[] nums, int[] changeIndices, int[] last_test, int lastDay){Arrays.fill(last_test, -1);for(int i=0; i<lastDay; i++){//求每一门考试在规定时间(lastDay)内的最后的考试时间last_test[changeIndices[i]-1] = i;}for(int x : last_test){//在规定时间内没有该课程的考试机会if(x < 0) return false;}int cnt = 0;for(int i=0; i<lastDay; i++){int idx = changeIndices[i]-1;//第i天的可以考试的课程if(last_test[idx]==i){if(cnt < nums[idx])return false;cnt -= nums[idx];}else{cnt++;}}return true;}
}

简单讲一下后往前遍历的思路：和第一个思路一样，只不过这里是透支复习的时间，也就是先考试，复习的天数先欠着，之后再还。（个人认为第一种更好理解，这种看不懂也没事）

代码如下：

class Solution {public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {int n = nums.length;int m = changeIndices.length;if (n > m) return -1;int[] done = new int[n]; // 避免反复创建和初始化数组int left = n - 1, right = m + 1;while (left + 1 < right) {int mid = (left + right) / 2;if (check(nums, changeIndices, done, mid)) {right = mid;} else {left = mid;}}return right > m ? -1 : right;}private boolean check(int[] nums, int[] changeIndices, int[] done, int mx) {int exam = nums.length;int study = 0;for (int i = mx - 1; i >= 0 && study <= i + 1; i--) { // 确保剩余的天数>要复习的天数int idx = changeIndices[i] - 1;if (done[idx] != mx) {//判断是否考过试done[idx] = mx;exam--; // 考试study += nums[idx]; // 需要复习的天数} else if (study > 0) {study--; // 复习}}return exam == 0 && study == 0; // 考完了并且复习完了}
}

四，3049. 标记所有下标的最早秒数 II

二分 + 反悔贪心

该题和上一题有两个不一样的地方：

1）可以在第 i 天，一天就复习完 changIndices[i] 这门课程（快速复习）

2）可以在任意一天考任意一门课程

这里有一个需要注意的点：快速复习和慢速复习（一天一天复习，复习nums[i]天）是冲突的，会造成浪费，也就是说，一门课程要么使用快速复习，要么使用慢速复习，可以使用反证法证明，当一门课程即使用快速复习，又使用慢速复习，就会浪费慢速复习的时间。

还有一个问题，快速复习的时间是越早越好还是越晚越好？这点可以从贪心的思路去想，复习完的时间越早，就有更加充足的时间去考试，所以答案是越早越好。统计所有课程最早的快速复习时间。

根据上一题来看，这道题是否也可以使用二分答案去做呢？这也是可以的，因为它的单调性还与上道题一样：给的时间越多，复习的时间越充裕，越能够通过考试。

如何判断所给的天数是否充足，这道题只能从后往前遍历，因为从前往后遍历的话，无法知道是否有足够的时间用来考试。

从后往前遍历：

• 当天不是一门课程快速复习的最早时间，cnt += 1
• 当天是一门课程快速复习的最早时间：

1. cnt>0，即有时间去考试，那么消耗一天去考试，cnt-=1
2. nums[i]=0，即不需要时间复习，cnt+=1
3. nums[i]=1，可以通过慢速复习，cnt+=1
4. cnt=0，即没有时间去考试，但是不意味着该门课程一定是慢速复习，可以通过反悔贪心，去看看有没有原本使用快速复习，且nums[i]最小的课程，如果有，反悔这门课（快速复习一天+考试一天），多出来的这两天，用来做当天这门课的快速复习+考试

最后看看剩下的使用慢速复习+考试的天数是否大于实际上的慢速复习+考试的天数

代码如下：

class Solution {public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {int n = nums.length;int m = changeIndices.length;if(n > m) return -1;long slow = n;for(int x : nums) slow += x;//统计慢速复习+考试需要多长时间int[] firstT = new int[n];//快速复习越早越好，这样就可以留更多的时间去考试Arrays.fill(firstT, -1);for(int i=m-1; i>=0; i--)firstT[changeIndices[i]-1] = i;PriorityQueue<Integer> que = new PriorityQueue<>((a,b)->a-b);int l = n, r = m;while(l <= r){que.clear();int mid = (l+r)/2;if(check(nums, changeIndices, firstT, que, slow, mid)){r = mid - 1;}else{l = mid + 1;}}return r+1>m ? -1 : r+1;}boolean check(int[] nums, int[] changeIndices, int[] firstT, PriorityQueue<Integer> que, long slow, int lastDay){int cnt = 0;//表示有多少时间可以用来慢速复习+考试for(int i=lastDay-1; i>=0; i--){//从后向前遍历int idx = changeIndices[i]-1;//当天可以快速复习的课程下标int x = nums[idx];//该课程需要几天复习if(x <= 1 || i != firstT[idx]){//复习1天 || 不是最早的快速复习时间 -> 可以使用慢速复习搞定cnt++;//当天可以用来慢速复习/考试continue;}if(cnt == 0){//复习>1天 && 是最早的快速复习时间没有慢速复习 && 没有时间用来考试 -> 看看有没有更节省的方式if(que.isEmpty() || x<=que.peek()){cnt++;//当天可以用来慢速复习/考试 即 该课程只能使用慢速复习continue;}slow += que.poll() + 1;//否则可以使que.poll()课程慢速复习+一天考试cnt += 2;//可以返还que.poll()课程所需的 1天快速复习 + 1天考试}slow -= x + 1;//减去当前课程复习天数+考试所需的一天cnt--;//当天快速复习 + 后面一天考试que.offer(x);}return cnt >= slow;//剩余留给慢速复习+考试的时间 > 实际所需慢速复习+考试的时间}
}

这篇关于Leetcode - 周赛386的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---