双周赛108
题目不是特别难，但是也许是十多天只做了每日一题，感觉不是很熟练。
T1、T2各WA一次，T2没有看到排序，T4没有从黑格子出发TLE了
这周继续努力呀
最长交替子序列【LC2765】
给你一个下标从 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。子数组是一个数组中一段连续 非空 的元素序列。
交替+1-1
- 思路：
实现
class Solution { public int alternatingSubarray(int[] nums) { int res = -1, n = nums.length; int l = 0; while (l < n){ int r = l; int val = 1; while (r + 1 < n && nums[r] + val == nums[r + 1]){ r++; val *= -1; } if (r == l){// 不能组成交替数组 l++; }else{ res = Math.max(res, r - l + 1); l = r; } } return res; } }
交替第一个元素和第一个元素+1
- 实现
- 交替的过程，元素标号从0开始
- 第偶数个元素为第一个元素
- 第奇数个元素为第一个元素+1
class Solution { public int alternatingSubarray(int[] nums) { int res = -1, n = nums.length; int l = 0; while (l < n){ int r = l; int val = 1; while (r + 1 < n && nums[r + 1] == nums[l] + (r + 1 - l) % 2){ r++; val *= -1; } if (r == l){// 不能组成交替数组 l++; }else{ res = Math.max(res, r - l + 1); l = r; } } return res; } }
class Solution { public int alternatingSubarray(int[] nums) { int ans = -1; int length = -1; for (int i = 1; i < nums.length; i++) { if (length > 0 && nums[i] - nums[i - 1] == nums [i - 2] - nums[i - 1]) { length++; } else if (nums[i] - nums[i - 1] == 1) { length = 2; } else { length = -1; } ans = Math.max(ans, length); } return ans; } }
重新放置石块【LC2766】
给你一个下标从 0 开始的整数数组
nums，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组moveFrom和moveTo。
在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。
完成这些操作后，请你按升序返回所有 有 石块的位置。
注意：
- 如果一个位置至少有一个石块，我们称这个位置 有 石块。
- 一个位置可能会有多个石块。
class Solution { public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) { Set<Integer> set = new HashSet<>(); for (int num : nums){ set.add(num); } // Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet()); int n = moveFrom.length; for (int i = 0; i < n; i++){ set.remove(moveFrom[i]); set.add(moveTo[i]); } return set.stream().sorted().collect(Collectors.toList()); } }
class Solution { public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) { TreeSet<Integer> set = new TreeSet<>(); for (int num : nums) { set.add(num); } for (int i = 0; i < moveFrom.length; i++) { if (set.remove(moveFrom[i])) { set.add(moveTo[i]); } } return List.copyOf(set); } }
将字符串分割为最少的美丽子字符串【LC2767】
给你一个二进制字符串
s，你需要将字符串分割成一个或者多个 子字符串 ，使每个子字符串都是 美丽 的。如果一个字符串满足以下条件，我们称它是 美丽 的：
- 它不包含前导 0 。
- 它是
5的幂的 二进制 表示。请你返回分割后的子字符串的 最少 数目。如果无法将字符串
s分割成美丽子字符串，请你返回-1。子字符串是一个字符串中一段连续的字符序列。
class Solution { String s; int[] memo; int n; public int minimumBeautifulSubstrings(String s) { this.s = s; this.n = s.length(); this.memo = new int[n + 1]; // for (int i = 0; i < n; i++){ // Arrays.fill(memo[i], n + 1); // } Arrays.fill(memo, n + 1); return dfs(0); } // 分割字符串s[l, n - 1]为最美字符串的最少数目，如果为-1表示无法进行分割 public int dfs(int l){ if (l >= n) return 0; if (memo[l] != n + 1) return memo[l]; // 枚举分割点 int res = n + 1; if (s.charAt(l) == '1'){ for (int i = l; i < n; i++){ if (check(s.substring(l, i + 1))){// 可以分割 int val = dfs(i + 1); if (val != -1){ res = Math.min(res, val + 1); } } } } if (res == n + 1){ res = -1; } memo[l] = res; return res; } public boolean check(String s){ int val = Integer.parseInt(s, 2); while (val % 5 == 0){ val /= 5; } return val == 1; } }
黑格子的数目【LC2768】
给你两个整数
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 个 黑色 格子的块的数目。
- 思路【TLE】
先使用哈希表记录每个黑色格子的位置，再枚举所有子矩阵，判断每个子矩阵中有多少个黑色格子，记录并返回结果 - 思路
- 从黑色格子出发，不枚举所有子矩阵，使用哈希表记录每个子矩阵含有黑色格子的数目，遍历所有黑色格子，将包含其的子矩阵个数+1，最后再遍历哈希表，记录结果，不包含黑色格子的子矩阵数目为总数-其他有黑方格的子矩阵的总数。
- 实现
class Solution { public long[] countBlackBlocks(int m, int n, int[][] coordinates) { // 二维化一维 ：x * n + y // 方法1:对于(x, y)判断其及相邻的四个格子有几个黑格子 m * n * 4 -> x * n + y, x* n + y + 1,(x + 1) * n + y,(x + 1) * n + y + 1【超时】 // 方法2 // 对于每个黑格子(x, y)通过哈希表记录包含其的子矩阵的影响 // 通过子矩阵左上角位置标号标记每个子矩阵 // 最后遍历哈希表记录结果，不包含黑色格子的子矩阵数目为总数-其他有黑方格的子矩阵的总数 long[] res = new long[5]; Map<Integer, Integer> map = new HashMap<>(); int[][] dirs = {{0, 0}, {0, -1}, {-1, 0}, {-1, -1}}; for (int[] coor : coordinates){ int x = coor[0], y = coor[1]; for (int i = 0; i < 4; i++){ int newX = x + dirs[i][0], newY = y + dirs[i][1]; if (newX >= 0 && newX < m - 1&& newY >= 0 && newY < n - 1){ int index = newX * n + newY; map.put(index, map.getOrDefault(index, 0) + 1); } } } for (Integer val : map.values()){ res[val]++; } res[0] = (long)(m - 1) * (n - 1) - map.size(); return res; } }
