6913. Longest Alternating Subarray
给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个交替子序列：
- m 大于 1 。
- s1 = s0 + 1 。
- 下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m-1) % 2] 一样。也就是说，s1 - s0 = 1 ，s2 - s1 = -1 ，s3 - s2 = 1 ，s4 - s3 = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)^m 。
请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 -1 。
子数组是一个数组中一段连续 非空 的元素序列。
测试样例
输入：nums = [2,3,4,3,4]
输出：4
解释：交替子数组有 [3,4] ，[3,4,3] 和 [3,4,3,4] 。最长的子数组为 [3,4,3,4] ，长度为4 。
解答：这道题目搜索空间很小nums.length <= 100, 直接暴力枚举所有可能的连续子串.
class Solution {
public int alternatingSubarray(int[] nums) {
int res = -1;
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (isAlter(nums, i, j)) {
res = Math.max(res, j - i + 1);
}
}
}
return res;
}
private boolean isAlter(int[] nums, int x, int y) {
for (int i = x; i <= y; ++i) {
if ((i - x) % 2 == 0) {
if (nums[i] != nums[x]) return false;
} else {
if (nums[i] != nums[x] + 1) return false;
}
}
return true;
}
}6469. Relocate Marbles
给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。
在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。
完成这些操作后，请你按升序返回所有 有 石块的位置。
注意：
- 如果一个位置至少有一个石块，我们称这个位置 有 石块。
- 一个位置可能会有多个石块。
测试样例：
输入：nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
输出：[5,6,8,9]
解释：
一开始，石块在位置 1,6,7,8 。
- 第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，位置 2,6,7,8 有石块。
- 第 i = 1 步操作中，我们将位置 7 处的石块移到位置 9 处，位置 2,6,8,9 有石块。
- 第 i = 2 步操作中，我们将位置 2 处的石块移到位置 5 处，位置 5,6,8,9 有石块。
最后，至少有一个石块的位置为 [5,6,8,9]
解答: 这道题目有一个条件：测试数据保证在进行第 i 步操作时，moveFrom[i] 处至少有一个石块。那就直接利用HashSet记录distinct的石子位置，然后按照要求移动就能得到结果。最后别忘记，题目要求升序返回所有石子位置。
class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
HashSet<Integer> set = new HashSet<>();
for (int n : nums) {
set.add(n);
}
for (int i = 0; i < moveFrom.length; ++i) {
set.remove(moveFrom[i]);
set.add(moveTo[i]);
}
List<Integer> res = new ArrayList<>(set);
Collections.sort(res);
return res;
}
}
6923. Partition String Into Minimum Beautiful Substrings
给你一个二进制字符串 s ，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。
如果一个字符串满足以下条件，我们称它是 美丽 的：
- 它不包含前导 0 。
- 它是 5 的幂的 二进制 表示。
请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串，请你返回 -1 。
子字符串是一个字符串中一段连续的字符序列。
测试样例：
输入：s = "1011"
2
解释：
我们可以将输入字符串分成 ["101", "1"] 。
- 字符串 "101" 不包含前导 0 ，且它是整数 51 = 5 的二进制表示。
- 字符串 "1" 不包含前导 0 ，且它是整数 50 = 1 的二进制表示。
最少可以将 s 分成 2 个美丽子字符串。
解答: 这道题目的范围实在过小：1 <= s.length <= 15。估计暴力也能获取结果。稍微优化一下，可以增加一个动态规划，记录当前位置切分之后，之后的美丽字符串最佳切割情况。
class Solution {
public int minimumBeautifulSubstrings(String s) {
int len = s.length();
Integer[] mem = new Integer[s.length()];
return helper(0, s, mem);
}
private int helper(int pos, String s, Integer[] mem) {
if (pos == s.length()) {
return 0;
} else if (mem[pos] == null) {
int res = Integer.MAX_VALUE, cur = 0;
if (s.charAt(pos) != '0') {
for (int i = pos; i < s.length(); ++i) {
cur = cur * 2 + s.charAt(i) - '0';
if (isMul(cur) && helper(i + 1, s, mem) != -1) {
res = Math.min(res, 1 + helper(i + 1, s, mem));
}
}
}
mem[pos] = res == Integer.MAX_VALUE ? -1 : res;
}
return mem[pos];
}
private boolean isMul(int n) {
while (n != 1) {
if (n % 5 != 0) {
return false;
}
n /= 5;
}
return true;
}
}6928. Number of Black Blocks
给你两个整数 m 和 n ，表示一个下标从 0 开始的 m x n 的网格图。
给你一个下标从 0 开始的二维整数矩阵 coordinates ，其中 coordinates[i] = [x, y] 表示坐标为 [x, y] 的格子是 黑色的 ，所有没出现在 coordinates 中的格子都是 白色的。
一个块定义为网格图中 2 x 2 的一个子矩阵。更正式的，对于左上角格子为 [x, y] 的块，其中 0 <= x < m - 1 且 0 <= y < n - 1 ，包含坐标为 [x, y] ，[x + 1, y] ，[x, y + 1] 和 [x + 1, y + 1] 的格子。
请你返回一个下标从 0 开始长度为 5 的整数数组 arr ，arr[i] 表示恰好包含 i 个 黑色 格子的块的数目。
测试样例：
输入：m = 3, n = 3, coordinates = [[0,0]]
输出：[3,1,0,0,0]
只有 1 个块有一个黑色格子，这个块是左上角为 [0,0] 的块。
其他 3 个左上角分别为 [0,1] ，[1,0] 和 [1,1] 的块都有 0 个黑格子。
所以我们返回 [3,1,0,0,0] 。
解答: 这道题目难度还是很低的。因为m，n的范围其实很大，如果遍历整个集合肯定会超时。但是这道题目有一个好处，每个黑色的方块最多属于4个子矩阵。既然有这个条件，我们可以遍历coordinates这个数组，计算所有与黑色块有关的子矩阵统计结果。剩余没有统计到的子矩阵就都是属于0了。
class Solution {
private static final int[][] block = {{0,0},{-1,0},{0,-1},{-1,-1}};
public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
long total = (m - 1L) * (n - 1L);
HashMap<Long, Integer> map = new HashMap<>();
long mul = n;
for (int[] c : coordinates) {
for (int[] b : block) {
int xt = c[0] + b[0], yt = c[1] + b[1];
if (xt >= 0 && xt < m - 1 && yt >= 0 && yt < n - 1) {
long key = xt * mul + yt;
map.put(key, map.getOrDefault(key, 0) + 1);
}
}
}
long[] res = new long[5];
for (Map.Entry<Long, Integer> kv : map.entrySet()) {
res[kv.getValue()] += 1;
}
res[0] = total - map.size();
return res;
}
}