双周赛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

• 思路：

  寻找以$nums[l]$为左边第一个数，交替子数组最右边的位置$r$，那么此时交替子数组长度为$r-l+1$；然后再以$nums[r]$为第一个数，重复以上过程，取最长长度返回即可

  • 交替的过程：相邻两个元素交替+1-1
  • 使用变量count记录当前交替数组的长度，使用变量val记录当前变化量，那么当前判断元素为$l+count$，前一个元素为$l+count-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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(1)$

交替第一个元素和第一个元素+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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(1)$

判断是否能接在之前的元素后面

• 思路

  判断$nums[i]$能否与前面的元素组成交替元素，使用变量cur记录以前一个元素为末尾的交替数组的长度

  • 如果$cur$大于0，并且$nums[i]$能与$nums[i-1]$和$nums[i-2]$组成交替子数组，那么$cur++$
  • 如果$nums[i]$能与$nums[i-1]$组成交替子数组，那么$cur=2$
  • 如果都不行，那么$cur=-1$

• 实现

  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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{O}(1)$

重新放置石块【LC2766】

给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。

在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。

完成这些操作后，请你按升序返回所有 有 石块的位置。

注意：

• 如果一个位置至少有一个石块，我们称这个位置 有 石块。
• 一个位置可能会有多个石块。

• 思路

  将有石块的位置记录在哈希表，每次移动将$moveFrom[i]$从哈希表中移除，然后将$moveTo[i]$放入哈希表，最后将哈希表中的数据转化为list，排序后返回

• 实现

  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());}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n\log n)$，排序的时间复杂度
    • 空间复杂度：$\mathcal{O}(n)$

• 实现：可以直接使用TreeSet

  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 。

子字符串是一个字符串中一段连续的字符序列。

• 思路：dfs+记忆化

  定义$dfs(i)$为分割字符串$s[l,n-1]$为最美字符串的最少数目，那么$dfs(0)$即为答案

  • 递归过程：

    • 枚举分割点$r$，判断字符串$s[l,r]$是否为美丽字符串，如果是才可以分割，并求出分割$s[r+1,n-1]$的最少数目
    • 而字符串$s[r+1，n-1]$必须也能够分割为美丽字符串，才可以更新数目，否则记录为-1，表示不能分割为美丽字符串
    • 递推公式为

    $$dfs(l)=ma{x}_{r为合法分割点}(dfs(r+1)+1)$$

  • 递归边界：

    $l\ge n$时，返回0

  • 如何判断字符串$s[l,r]$是否为美丽字符串？

    • 打表预处理
    • 将二进制字符串转化为十进制，并判断是否是5的幂

• 实现

  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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n^2)$
    • 空间复杂度：$\mathcal{O}(n)$

黑格子的数目【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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(nC)$，C为4
    • 空间复杂度：$\mathcal{O}(n)$