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; } }
检查骑士巡视方案【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<int[]> 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; } }
*美丽子集的数目
给你一个由正整数组成的数组
nums和一个 正 整数k。如果
nums的子集中，任意两个整数的绝对差均不等于k，则认为该子数组是一个 美丽 子集。
返回数组 nums 中 非空 且 美丽 的子集数目。
nums的子集定义为：可以经由nums删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。
- 思路：
class Solution { Map<Integer, Integer> 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; } }
执行操作后的最大 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了几次
- 思路
实现
class Solution { public int findSmallestInteger(int[] nums, int value) { int n = nums.length; HashMap<Integer, Integer> 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; } }
