蓝桥杯30天真题冲刺|题解报告|第三十天

大家好，我是snippet，今天是我们这次蓝桥省赛前一起刷题的最后一天了，今天打了一场力扣周赛，前面3个题都是有思路的，第三个题只过了一半的案例，后面看完大佬们的题解彻悟，下面是我今天的题解

目录

 一、最长平衡子字符串

题目链接：6362. 最长平衡子字符串 - 力扣（Leetcode）

题目内容：

解题思路：

代码：

二、转换二维数组

题目链接：6363. 转换二维数组 - 力扣（Leetcode）

题目内容：

解题思路：

代码：

三、老鼠和奶酪

题目链接：6364. 老鼠和奶酪 - 力扣（Leetcode）

题目内容：

解题思路：

代码：

---

 一、最长平衡子字符串

题目链接：6362. 最长平衡子字符串 - 力扣（Leetcode）

题目内容：

给你一个仅由 0 和 1 组成的二进制字符串 s 。  

如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。 

返回  s 中最长的平衡子字符串长度。

子字符串是字符串中的一个连续字符序列。

示例 1：

输入：s = "01000111"
输出：6
解释：最长的平衡子字符串是 "000111" ，长度为 6 。

示例 2：

输入：s = "00111"
输出：4
解释：最长的平衡子字符串是 "0011" ，长度为  4 。

示例 3：

输入：s = "111"
输出：0
解释：除了空子字符串之外不存在其他平衡子字符串，所以答案为 0 。

提示：

1 <= s.length <= 50

'0' <= s[i] <= '1'

解题思路：

因为平衡字符串需要满足0和1的个数相同，并且0和1都是连续的，0必须在1的前面，当我们碰到0时，有两种情况：

1.前面没有1，0的数量++；

2.前面有1，重新计数；

当我们碰到1的时候有2种情况：

1.前面没有0，直接countinue跳转到下一个字符进行计算

2.前面有0，前面有0的话，需要计算0和1的个数，ans = Math.min(cnt0,cnt1)*2；

代码：

package 蓝桥杯30天真题冲刺.Day30.力扣第339场周赛;import java.io.*;/*** @author snippet* @data 2023-04-02* 力扣第399场周赛-最长平衡子字符串*/
public class T1_最长平衡子字符串 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static void main(String[] args) throws IOException {pw.flush();br.close();}public int findTheLongestBalancedSubstring(String s) {if (s == "") return 1;int ans = 0;int cnt0 = 0;int cnt1 = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '0') {if (cnt1 != 0) {cnt1 = 0;cnt0 = 1;} else {cnt0++;}} else {if (cnt0 == 0) continue;cnt1++;ans = Math.max(ans, Math.min(cnt0, cnt1)*2);}}return ans;}
}

二、转换二维数组

题目链接：6363. 转换二维数组 - 力扣（Leetcode）

题目内容：

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

1.二维数组应该 只 包含数组 nums 中的元素。

2.二维数组中的每一行都包含 不同 的整数。

3.二维数组的行数应尽可能 少 。

返回结果数组。如果存在多种答案，则返回其中任何一种。

请注意，二维数组的每一行上可以存在不同数量的元素。

示例 1：

输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。

示例 2：

输入：nums = [1,2,3,4]
输出：[[4,3,2,1]]
解释：nums 中的所有元素都不同，所以我们可以将其全部保存在二维数组中的第一行。

提示：

1 <= nums.length <= 200

1 <= nums[i] <= nums.length

解题思路：

我们用map存到数组里面的所有数据，然后对map进行多次遍历，再把数据依次放入，并且满足每行里面的数据在这行里面都是唯一的

代码：

package 蓝桥杯30天真题冲刺.Day30.力扣第339场周赛;import java.io.*;
import java.util.*;/*** @author snippet* @data 2023-04-02* 力扣第399场周赛-转换二维数组*/
public class T2_转换二维数组 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static void main(String[] args) throws IOException {pw.flush();br.close();}public List<List<Integer>> findMatrix(int[] nums) {Map<Integer, Integer> map = new HashMap<>();List<List<Integer>> list = new ArrayList<>();int len = nums.length;int max = 0;for (int i = 0; i < len; i++) {list.add(new ArrayList<>());}for (int i = 0; i < len; i++) {max = Math.max(nums[i], max);map.put(nums[i], map.getOrDefault(nums[i], 0)+1);}for (List<Integer> temp : list) {for (int i = 1; i <= max; i++) {if (map.containsKey(i) && map.get(i) != 0) {temp.add(i);map.put(i, map.get(i)-1);}}}List<List<Integer>> ans = new ArrayList<>();for (List<Integer> temp : list) {if (temp.size() != 0) {ans.add(new ArrayList<>(temp));}}return ans;}
}

三、老鼠和奶酪

题目链接：6364. 老鼠和奶酪 - 力扣（Leetcode）

题目内容：

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

1.如果第一只老鼠吃掉，则得分为 reward1[i] 。

2.如果第二只老鼠吃掉，则得分为 reward2[i] 。

给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

示例 1：

输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。

示例 2：

输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。

提示：

1 <= n == reward1.length == reward2.length <= 10^5

1 <= reward1[i], reward2[i] <= 1000

0 <= k <= n

解题思路：

这个题是求吃奶酪的最高得分，那我们就可以使用贪心，那我们可以先把第一只老鼠吃所有奶酪的得分用sum1记录下来，同时记录吃同一份奶酪时，第一只老鼠和第二只老鼠的得分差值（arr[i]  = reward1[i] - reward2[i]），因为第一只老鼠只可以吃k份奶酪（就表示第二只老鼠可以吃len-k份奶酪），sum1记录的是第一只老鼠吃所有奶酪的得分，那我们需要份len-k份给第二只老鼠，对求得的得分差值arr进行排序（升序），我们把前len-k份奶酪分给第二只老鼠吃，也就是sum -= arr[i]，这样子就可以让我们的得分达到最大值

代码：

package 蓝桥杯30天真题冲刺.Day30.力扣第339场周赛;import java.io.*;
import java.util.*;/*** @author snippet* @data 2023-04-02* 力扣第399场周赛-老鼠和奶酪*/
// 贪心
public class T3_老鼠和奶酪 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static void main(String[] args) throws IOException {int[] a = {1,4,4,6,4};int[] b = {6,5,3,6,1};System.out.println(miceAndCheese(a,b,1));pw.flush();br.close();}static public int miceAndCheese(int[] reward1, int[] reward2, int k) {int sum = 0;Integer[] arr = new Integer[reward1.length];for (int i = 0; i < reward1.length; i++) {arr[i] = reward1[i] - reward2[i];sum += reward1[i];}Arrays.sort(arr);for (int i = 0; i <reward1.length- k; i++) {sum -= arr[i];}return sum;}
}