链接:LeetCode
[Leetcode]2609. 最长平衡子字符串
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量,则认为 s 的这个子字符串是平衡子字符串。请注意,空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
模拟遍历即可。
class Solution {
public int findTheLongestBalancedSubstring(String s) {
int zero = 0, one = 0;
int res = 0, result = 0;
for(char ch: s.toCharArray()) {
if(ch == '0') {
if(one!=0) {
one = 0;
zero = 1;
} else {
zero ++;
}
}
else {
one ++;
result = Math.min(zero, one);
res = Math.max(res, result);
}
}
return 2 * res;
}
}
[Leetcode]2610. 转换二维数组
给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组:
二维数组应该 只 包含数组 nums 中的元素。
二维数组中的每一行都包含 不同 的整数。
二维数组的行数应尽可能 少 。
返回结果数组。如果存在多种答案,则返回其中任何一种。
请注意,二维数组的每一行上可以存在不同数量的元素。
哈希。
class Solution {
public List<List<Integer>> findMatrix(int[] nums) {
HashMap<Integer, Integer> hash = new HashMap<>();
for(int num: nums) {
hash.put(num, hash.getOrDefault(num, 0) + 1);
}
List<List<Integer>> res = new ArrayList<>();
int length = 1;
for(var key: hash.keySet()) {
length = Math.max(length, hash.get(key));
}
for(int i=0;i<length;++i) res.add(new ArrayList<Integer>());
for(int key: hash.keySet()) {
int value = hash.get(key);
for(int i=0;i<value;++i) res.get(i).add(key);
}
return res;
}
}
[Leetcode]2611. 老鼠和奶酪
有两只老鼠和 n 块不同类型的奶酪,每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为:
如果第一只老鼠吃掉,则得分为 reward1[i] 。
如果第二只老鼠吃掉,则得分为 reward2[i] 。
给你一个正整数数组 reward1 ,一个正整数数组 reward2 ,和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下,最大得分为多少。
排序+贪心。为了使最终得分最大,应该让每只老鼠吃到尽可能大的奶酪。由于两只老鼠吃的奶酪是互斥关系,因此我们可以先假设所有奶酪被第一只老鼠食得,然后再挑选 n - k 个奶酪还给第二只老鼠。
那么,对于每个位置 i,将奶酪从第一只老鼠还给第二只老鼠存在差值 diff = reward2[i] - reward1[i],表示得分的差值为 diff。差值为正得分变大,差值为负得分降低,显然降低越少越好。
因此,我们的算法是对 diff 排序,将得分降低越大的位置保留给第一只老鼠,其他还给第二只老鼠。
class Solution {
public int miceAndCheese(int[] reward1, int[] reward2, int k) {
List<List<Integer>> diff = new ArrayList<>();
int length = reward1.length;
for(int i=0;i<length;++i) {
diff.add(new ArrayList<Integer>());
diff.get(i).add(i);
diff.get(i).add(reward2[i]- reward1[i]);
}
Collections.sort(diff, (n1, n2) -> n1.get(1)-n2.get(1));
int res = 0;
for(int i=0;i<k;++i) {
res += reward1[diff.get(i).get(0)];
}
for(int i=k;i<length;++i) {
res += reward2[diff.get(i).get(0)];
}
return res;
}
}
[Leetcode]2612. 最少翻转操作数
给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ,它们表示一个长度为 n 且下标从 0 开始的数组 arr ,数组中除了下标为 p 处是 1 以外,其他所有数都是 0 。
同时给你一个整数数组 banned ,它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ,题目保证 banned[i] != p 。
你可以对 arr 进行 若干次 操作。一次操作中,你选择大小为 k 的一个 子数组 ,并将它 翻转 。在任何一次翻转操作后,你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说,arr[banned[i]] 始终 保持 0 。
请你返回一个数组 ans ,对于 [0, n - 1] 之间的任意下标 i ,ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数,如果无法放到位置 i 处,此数为 -1 。
- 子数组 指的是一个数组里一段连续 非空 的元素序列。
- 对于所有的 i ,ans[i] 相互之间独立计算。
- 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序
BFS 模拟。
class Solution {
public int[] minReverseOperations(int n, int p, int[] banned, int k) {
var ban = new boolean[n];
ban[p] = true;
for (int i : banned) ban[i] = true;
TreeSet<Integer>[] sets = new TreeSet[2];
sets[0] = new TreeSet<>();
sets[1] = new TreeSet<>();
for (int i = 0; i < n; i++)
if (!ban[i])
sets[i % 2].add(i);
sets[0].add(n);
sets[1].add(n); // 哨兵
var ans = new int[n];
Arrays.fill(ans, -1);
var q = new ArrayList<Integer>();
q.add(p);
for (int step = 0; !q.isEmpty(); ++step) {
var tmp = q;
q = new ArrayList<>();
for (int i : tmp) {
ans[i] = step;
// 从 mn 到 mx 的所有位置都可以翻转到
int mn = Math.max(i - k + 1, k - i - 1);
int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
var s = sets[mn % 2];
for (var j = s.ceiling(mn); j <= mx; j = s.ceiling(mn)) {
q.add(j);
s.remove(j);
}
}
}
return ans;
}
}
参考:LeetCode
- Leetcode Contest Weekly 339leetcode contest weekly 339 leetcode contest weekly 361 leetcode contest weekly 355 leetcode contest weekly 365 leetcode contest weekly 367 leetcode contest weekly 368 leetcode contest weekly 350 leetcode contest weekly 351 leetcode contest weekly 364 leetcode contest weekly 359