11-周赛337总结

第三题没有想到是子集问题，只记得做过类似的题，思路还是原来错误的思路，然后就直接去做第四题了，战绩3道，练练子集回溯，加深印象

奇偶位数

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

返回整数数组 answer ，其中 answer = [even, odd] 。

• 思路

  从最低位开始判断，如果该位为0，那么将其对应的计数加1

• 实现

  class Solution {public int[] evenOddBit(int n) {int[] res = new int[2];int index = 0;while (n > 0){if ((n & 1) == 1){res[index % 2]++;}n = (n >> 1);  index++;}return res;}
  }
  

  • 复杂度
    • 时间复杂度：O(logn)O(logn)O(logn)
    • 空间复杂度：O(1)O(1)O(1)

检查骑士巡视方案【LC】

骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

• 思路：

  将每个单元格位置和值组成的三元组放入小顶堆中，保证按顺序移动。

  • 首先需要判断起点是否位于左上角，否则直接返回false【因为这个WA了】
  • 然后判断能否移动至下一个位置，根据横纵坐标的差值判断，差值的可能性有八种，如果符合任意一种则移动至下一个位置，否则返回false
  • 如果可以移动至最后一个节点，那么返回true

• 实现

  class Solution {public boolean checkValidGrid(int[][] grid) {int n = grid.length;// 存储三元组PriorityQueue pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){pq.add(new int[]{i, j, grid[i][j]});}}// 判断起点int[] pre = pq.poll();if (pre[0] != 0 || pre[1] != 0) return false;while (!pq.isEmpty()){int[] next = pq.poll();int[] move = {next[0] - pre[0], next[1] - pre[1]};// 判断能否移动至下一个位置if (!isCorrect(move)){return false;}pre = next;}return true;}public boolean isCorrect(int[] move){int[] d1 = {2, -2};int[] d2 = {1, -1};for (int i = 0; i < 2; i++){for (int j = 0; j < 2;j++){if (move[0] == d1[i] && move[1] == d2[j]){return true;}if (move[0] == d2[i] && move[1] == d1[j]){return true;}}}return false;}
  }
  

  • 复杂度
    • 时间复杂度：O(n2)O(n^2)O(n2)
    • 空间复杂度：O(n2)O(n^2)O(n2)

*美丽子集的数目

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

• 思路：

  回溯枚举每一种美丽的子集，统计其数目。使用哈希表统计当前子集出现的数字及对应的次数，然后回溯搜索放nums[i]或者不放nums[i]对应的子集数目，注意只有当前子集中不存在nums[i]−knums[i] - knums[i]−k和k−nums[i]k-nums[i]k−nums[i]时，才可以将nums[i]放入该子集中

• 回溯三部曲

  • 回溯函数模板返回值以及参数

    • 返回值：int 存储子集数目
    • nums，k，i（记录本层递归中选择的数字）
    • 全局变量：path（当前子集的数字及对应的次数）

  • 回溯函数终止条件

    • 当搜索到数组的末尾时返回，如果不为空集则返回1

  • 回溯搜索的遍历过程：分两种情况考虑

    • 不选择单词nums[i]，直接递归到下一个数字
    • 选择单词nums[i]，不存在相减为kkk的数时，才能将该数字放入子集中，递归结束后需要回溯

  class Solution {Map path;public int beautifulSubsets(int[] nums, int k) {path = new HashMap<>();return backtracking(nums, k, 0);}public int backtracking(int[] nums, int k, int i){if (i == nums.length ) return path.size() > 0 ? 1 : 0;// 如果哈希表中， 不存在nums[i]-k和k + nums[i],才可以选nums[i]int res = 0;if (!path.containsKey(nums[i] - k) && !path.containsKey(k + nums[i])){path.put(nums[i], path.getOrDefault(nums[i], 0) + 1);res += backtracking(nums, k, i + 1);path.put(nums[i], path.getOrDefault(nums[i], 0) - 1);if (path.get(nums[i]) <= 0){path.remove(nums[i]);}}// 不选nums[i]res += backtracking(nums, k, i + 1);return res;}
  }
  

  • 复杂度
    • 时间复杂度：O(2n)O(2^n)O(2n)，nnn为nums的长度
    • 空间复杂度：O(n)O(n)O(n)

执行操作后的最大 MEX【LC】

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

先超时了一次，然后改代码思路不够清晰WA了几次

• 思路

  将每个数的数值转化为[0,value−1][0,value-1][0,value−1]中的某个数，使用哈希表记录每个数值对应的次数，然后按照[0,value−1][0,value-1][0,value−1]的顺序访问哈希表，每次将对应的次数减1，碰到次数为0的值时终止访问，此时的访问次数即为nums的最大MEX

  • 贪心的思想：我们需要尽可能的将每个值填充，然后再将值增大，使MXE最大
  • 每访问[0,value−1][0,value-1][0,value−1]一遍，相当于整体的值加了value

• 实现

  class Solution {public int findSmallestInteger(int[] nums, int value) {int n = nums.length;HashMap map = new HashMap<>();for (int i = 0; i < n; i++){if (nums[i] < 0){int count = Math.abs(nums[i]) / value + (Math.abs(nums[i]) % value == 0 ? 0 : 1);nums[i] += value * count ;}            while (nums[i] >= value){int count = nums[i] / value ;nums[i] -= value * count;}  map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);}int cur = 0;while (map.containsKey(cur % value) && map.get(cur % value) > 0){map.put(cur % value, map.get(cur % value) - 1);cur++;}return cur;}
  }
  

  • 复杂度
    • 时间复杂度：O(2n)O(2^n)O(2n)，nnn为nums的长度
    • 空间复杂度：O(n)O(n)O(n)