大家好，我是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;
}
}
