6362. Find the Longest Balanced Substring of a Binary String
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
测试样例
输入：s = "01000111"
输出：6
解答：这道题目范围很小，直接暴力枚举就行了
class Solution {
public int findTheLongestBalancedSubstring(String s) {
int res = 0;
for (int i = 0; i < s.length(); ++i) {
for (int j = i + 1; j < s.length(); j = j + 2) {
if (isValid(s, i, j)) {
res = Math.max(res, j - i + 1);
}
}
}
return res;
}
private boolean isValid(String s, int st, int ed) {
int zeroCount = 0, oneCount = 0;
boolean isZeroOver = false;
for (int i = st; i <= ed; ++i) {
if (s.charAt(i) == '0') {
if (isZeroOver) return false;
++zeroCount;
} else {
isZeroOver = true;
++oneCount;
}
}
return oneCount == zeroCount;
}
}6363. Convert an Array Into a 2D Array With Conditions
给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：
- 二维数组应该 只 包含数组 nums 中的元素。
- 二维数组中的每一行都包含 不同 的整数。
- 二维数组的行数应尽可能 少 。
返回结果数组。如果存在多种答案，则返回其中任何一种。
请注意，二维数组的每一行上可以存在不同数量的元素。
测试样例：
输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。可以证明无法创建少于三行且符合题目要求的二维数组。
解答: 哈希表去重
class Solution {
public List<List<Integer>> findMatrix(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
List<List<Integer>> res = new ArrayList<>();
for (int n : nums) {
int m = map.getOrDefault(n, -1) + 1;
if (m == res.size()) {
res.add(new ArrayList<>());
}
res.get(m).add(n);
map.put(n, m);
}
return res;
}
}6357. Minimum Operations to Make All Array Elements Equal
有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：
- 如果第一只老鼠吃掉，则得分为 reward1[i] 。
- 如果第二只老鼠吃掉，则得分为 reward2[i] 。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。
测试样例
输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：
这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。总得分为 4 + 4 + 3 + 4 = 15 。15 是最高得分。
解答：这道题目本质是排序
class Solution {
public int miceAndCheese(int[] reward1, int[] reward2, int k) {
int len = reward2.length;
Integer[] sort = new Integer[len];
for (int i = 0; i < len; ++i) {
sort[i] = i;
}
Arrays.sort(sort, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int d1 = reward1[o1] - reward2[o1];
int d2 = reward1[o2] - reward2[o2];
return d2 - d1;
}
});
int res = 0;
for (int i = 0; i < len; ++i) {
if (i < k) {
res += reward1[sort[i]];
} else {
res += reward2[sort[i]];
}
}
return res;
}
}6365. Minimum Reverse Operations
给你一个整数 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] 相互之间独立计算。
- 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。
测试样例
输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：
k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。
解答：周赛的时候想到了这道题目其实牵涉到了奇偶性，但是脑子没转过来，它其实还有连续性。
奇偶性指下一个节点与当前的节点的奇偶性和k有关。这里连续性有点特殊，指在会是一段连续的等差数列，且差值为2。
确定这2个条件之后，每次我们寻找到当前点能到达的最小点，然后不断搜索奇偶性一致，且连续的未使用位置就能解决这题。
class Solution {
public int[] minReverseOperations(int n, int p, int[] banned, int k) {
int[] result = new int[n];
TreeSet<Integer>[] set = new TreeSet[] { new TreeSet<>(), new TreeSet<>() };
for (int i = 0; i < n; ++i) {
set[i % 2].add(i);
result[i] = i == p ? 0 : -1;
}
set[p % 2].remove(p);
for (int i : banned) {
set[i % 2].remove(i);
}
for (ArrayDeque<Integer> deque = new ArrayDeque<>(Arrays.asList(p)); !deque.isEmpty();) {
for (Integer poll = deque.poll(), i = Math.abs(poll - k + 1), j = set[i % 2].ceiling(i); j != null
&& j < n - Math.abs(n - poll - k); j = set[i % 2].higher(j)) {
deque.offer(j);
result[j] = result[poll] + 1;
set[i % 2].remove(j);
}
}
return result;
}
}最近的周赛第四题也太难了。。。