本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。
大家好，我是小彭。
上周末是 LeetCode 第 337 场周赛，你加入了吗？这场周赛第三题有点放水，如果依照题目的数据量来说最多算 Easy 题，但如果依照动静布局来做能够算 Hard 题。
小彭的技术交换群 02 群来了，公众号回复“加群”退出咱们~
周赛概览
2595. 奇偶位数（Easy）
- 题解一：模仿 $O(lgn)$
- 题解二：位掩码 + bitCount $O(1)$
2596. 查看骑士巡视计划（Medium）
- 题解一：模仿 $O(n^2)$
2597. 漂亮子集的数目（Medium）
- 题解一：回溯 $O(2^n)$
- 题解二：同余分组 + 动静布局 / 打家劫舍 $O(nlgn)$
2598. 执行操作后的最大 MEX（Medium）
- 题解一：同余分组 + 贪婪 $O(n)$
2595. 奇偶位数（Easy）
题目地址
https://leetcode.cn/problems/number-of-even-and-odd-bits/
题目形容
给你一个 正 整数 n。
用 even 示意在 n 的二进制模式（下标从 0 开始）中值为 1 的偶数下标的个数。
用 odd 示意在 n 的二进制模式（下标从 0 开始）中值为 1 的奇数下标的个数。
返回整数数组 answer，其中 answer = [even, odd]。
题解一（模仿）
简略模拟题。
写法 1：枚举二进制位
class Solution {fun evenOddBit(n: Int): IntArray {val ret = intArrayOf(0, 0)
for (index in 0..30) {if (n and (1 shl index) != 0) {ret[index % 2]++
}
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(U)$ 其中 $U$ 是整数二进制位长度；
- 空间复杂度：$O(1)$ 仅应用常量级别空间。
写法 2：一直取最低位，而后右移 n，当 n 为 0 时跳出：
class Solution {fun evenOddBit(n: Int): IntArray {val ret = intArrayOf(0, 0)
var x = n
var index = 0
while (x != 0) {ret[i] += x and 1 // 计数
x = x ushr 1 // 右移
i = i xor 1 // 0 -> 1 或 1 -> 0
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(lgn)$
- 空间复杂度：$O(1)$ 仅应用常量级别空间。
题解二（位掩码 + bitCount）
应用二进制掩码 01010101 取出偶数下标，再应用 Integer.bitCount() 计算位 1 的个数：
class Solution {fun evenOddBit(n: Int): IntArray {
val mask = 0b0101_0101_0101_0101_0101_0101_0101_0101
return intArrayOf(Integer.bitCount(n and mask),
Integer.bitCount(n) - Integer.bitCount(n and mask)
)
}
}复杂度剖析：
- 工夫复杂度：$O(1)$ Java Integer.bitCount() 库函数的工夫复杂度是 $O(1)$，如果依照惯例实现是 $O(lgn)$；
- 空间复杂度：$O(1)$
2596. 查看骑士巡视计划（Medium）
题目地址
https://leetcode.cn/problems/check-knight-tour-configuration/
题目形容
骑士在一张 n x n 的棋盘上巡视。在无效的巡视计划中，骑士会从棋盘的 左上角 登程，并且拜访棋盘上的每个格子 恰好一次。
给你一个 n x n 的整数矩阵 grid，由范畴 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 示意单元格 (row, col) 是骑士拜访的第 grid[row][col] 个单元格。骑士的口头是从下标 0 开始的。
如果 grid 示意了骑士的无效巡视计划，返回 true；否则返回 false。
留神，骑士口头时能够垂直挪动两个格子且程度挪动一个格子，或程度挪动两个格子且垂直挪动一个格子。下图展现了骑士从某个格子登程可能的八种口头路线。
题解（模仿）
二维简略模拟题。
class Solution {fun checkValidGrid(grid: Array<IntArray>): Boolean {if (grid[0][0] != 0) return false
val directions = arrayOf(intArrayOf(1, 2),
intArrayOf(2, 1),
intArrayOf(2, -1),
intArrayOf(1, -2),
intArrayOf(-1, -2),
intArrayOf(-2, -1),
intArrayOf(-2, 1),
intArrayOf(-1, 2)
)
val n = grid.size
var row = 0
var column = 0
var count = 1
outer@ while (count < n * n) {for (direction in directions) {val newRow = row + direction[0]
val newColumn = column + direction[1]
if (newRow < 0 || newRow >= n || newColumn < 0 || newColumn >= n) continue
if (count == grid[newRow][newColumn]) {
row = newRow
column = newColumn
count++
continue@outer
}
}
return false
}
return true
}
}复杂度剖析：
- 工夫复杂度：$O(C·n^2)$ 其中 $C$ 是骑士的行走方向，$C$ 为常数 8；
- 空间复杂度：$O(1)$
2597. 漂亮子集的数目（Medium）
题目地址
https://leetcode.cn/problems/the-number-of-beautiful-subsets/
题目形容
给你一个由正整数组成的数组 nums 和一个 正 整数 k。
如果 nums 的子集中，任意两个整数的相对差均不等于 k，则认为该子数组是一个 漂亮 子集。
返回数组 nums 中 非空 且 漂亮 的子集数目。
nums 的子集定义为：能够经由 nums 删除某些元素（也可能不删除）失去的一个数组。只有在删除元素时抉择的索引不同的状况下，两个子集才会被视作是不同的子集。
准备常识
- 同余性质：
如果 x % m == y % m，则称 x 和 y 对模 m 同余，即为 x ≡ (y mod m)
- 乘法定理：
如果某个工作有 n 个环节，每个环节别离有 ${m_1, m_2, m_3, …, m_n}$ 种计划，那么实现工作的总计划数就是 $m_1*m_2*m3*…*m_n$。
题解一（暴力回溯）
因为题目的数据量十分小（数组长度只有 20），所以能够间接使用暴力算法。
算法：枚举所有子集，并且减少约束条件：如果曾经抉择过 x - k 或 x + k，则不能抉择 x。
class Solution {
private var ret = 0
fun beautifulSubsets(nums: IntArray, k: Int): Int {subsets(nums, 0, k, IntArray(k + 1001 + k)/* 左右减少 k 防止数组下标越界 */)
return ret - 1 // 题目排除空集
}
// 枚举子集
private fun subsets(nums: IntArray, start: Int, k: Int, cnts: IntArray) {
// 记录子集数
ret++
if (start == nums.size) return
for (index in start until nums.size) {val x = nums[index] + k // 偏移 k
if (cnts[x - k] != 0 || cnts[x + k] != 0) continue // 不容许抉择
// 抉择
cnts[x]++
// 递归
subsets(nums, index + 1, k, cnts)
// 回溯
cnts[x]--
}
}
}复杂度剖析：
- 工夫复杂度：$O(2^n)$ 其中 $n$ 为 $nums$ 数组长度，每个地位有选和不选两种状态，每个状态的工夫复杂度是 $O(1)$，因而整体工夫复杂度是 $O(2^n)$；
- 空间复杂度：$O(C)$ 数组空间。
题解二（同余分组 + 动静布局 / 打家劫舍）
这道题如果不使用暴力解法，难度应该算 Hard。
依据同余性质，如果 x 和 y 对模 k 同余，那么 x 和 y 有可能相差 k；如果 x 和 y 对模 k 不同余，那么 x 和 y 不可能相差 k。 因而，咱们能够将原数组依照模 k 分组，而后独自计算每个分组外部计划数，再依据乘法定理将不同分组的计划数相乘即失去最终后果。
那么，当初的是如何计算分组外部的计划数？
咱们发现，“如果曾经抉择过 x - k 或 x + k，则不能抉择 x” 的语义跟经典动静布局题 198. 打家劫舍 的 “如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警” 的语义十分相似，咱们能够套用雷同的解题思路：
1、先对分组外部排序，因为只有相邻的数才有可能不能同时抉择；
2、定义 dp[i] 示意抉择到 i 为止的计划数，则有递推关系：
$$
dp[i] = \begin{cases}
dp[i-1] + dp[i-2] &\text{if} a_i – a_{i-1} =k\\
dp[i-1]*2 &\text{if} a_i – a_{i-1} \not=k
\end{cases}
$$
如果不选 $a_i$，那么 $a_{i-1}$ 肯定可选，即 $dp[i-1]$ 的计划数。
如果抉择 $a_i$，那么须要思考 $a_{i-1}$ 与 $a_i$ 的关系：
- 如果 $a_i – a_{i-1} =k$，那么 $a_i$ 与 $a_{i-1}$ 不能同时抉择，$dp[i] = dp[i-1] + dp[i-2]$ 示意在 $a_{i-1}$ 和 $a_{i-2}$ 上的计划数之和；
- 如果 $a_i – a_{i-1} \not=k$，那么 $a_i$ 与 $a_{i-1}$ 能够同时抉择 $dp[i] = dp[i-1]*2$
最初，还须要思考数字反复的状况，设 c_i 示意 a_i 的呈现次数：
- 如果不选 $a_i$，则只有 1 种计划，即空集；
- 如果抉择 $a_i$，则有 $2^{c_i}$ 种计划，最初在减去 1 个空集计划。
整顿到递归公式中有：
$$
dp[i] = \begin{cases}
dp[i-1] + dp[i-2]*(2^{c_i}-1) &\text{if} a_i – a_{i-1} =k\\
dp[i-1]*(2^{c_i}) &\text{if} a_i – a_{i-1} \not=k
\end{cases}
$$
以 [2, 3, 4, 5, 10], k = 2 为例，依照模 2 分组后：
- 余数为 0 的分组 [2, 4, 10]：计划为 [2]、[4]、[10]、[2, 10]、[4, 10]
- 余数为 1 的分组 [3, 5]：计划为 [3]、[5]
class Solution {fun beautifulSubsets(nums: IntArray, k: Int): Int {
// 1、同余分组
// < 余数 to < 元素，元素计数 >>
val buckets = HashMap<Int, TreeMap<Int, Int>>()
for (num in nums) {val cntMap = buckets.getOrPut(num % k) {TreeMap<Int, Int>() }
cntMap[num] = cntMap.getOrDefault(num, 0) + 1
}
// 2、枚举分组
var ret = 1
for ((_, bucket) in buckets) {
// 3、动静布局
val n = bucket.size
// dp[i] 示意抉择到 i 地位的计划数，这里应用滚动数组写法
// val dp = IntArray(n + 1)
var pre2 = 0 // dp[i-2]
var pre1 = 1 // dp[i-1]
var index = 1
var preNum = -1
for ((num, cnt) in bucket) {if (index > 1 && num - preNum == k) {
// a_i 不可选
val temp = pre1
pre1 = pre1 + pre2 * ((1 shl cnt) - 1)
pre2 = temp
} else {
// a_i 可选可不选
val temp = pre1
pre1 = pre1 * (1 shl cnt)
pre2 = temp
}
preNum = num
index++
}
ret *= pre1
}
return ret - 1
}
}复杂度剖析：
- 工夫复杂度：$O(nlgn + n)$ 其中 $n$ 为 $nums$ 数组的长度，应用有序汇合进行分组的工夫复杂度是 $O(nlgn)$，枚举分组的步骤每个元素最多拜访一次，工夫复杂度是 $O(n)$；
- 空间复杂度 $O(n)$：有序汇合空间 $O(n)$，动静布局过程中应用滚动数组空间为 $O(1)$。
类似题目
- 78. 子集
- 784. 字母大小写全排列
- 198. 打家劫舍
近期周赛子集问题：
LeetCode 周赛 333 · 无平方子集计数（Medium）
2598. 执行操作后的最大 MEX（Medium）
题目地址
https://leetcode.cn/problems/smallest-missing-non-negative-in…
题目形容
给你一个下标从 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 。
准备常识
- 同余性质：
如果 x % m == y % m，则称 x 和 y 对模 m 同余，即为 x ≡ (y mod m)
- 正数取模技巧：
如果 x 和 y 都大于 0，则 x ≡ (y mod m) 等价于 x % m == y % m
$$
\begin{matrix}
10\ \% \ 3 == 1\\
-4\ \%\ 3 == 1
\end{matrix}
$$
如果 x 和 y 都小于 0，则 x ≡ (y mod m) 等价于 x % m == y % m
$$
\begin{matrix}
-10\ \%\ 3== -1\\
-4\ \%\ 3==-1
\end{matrix}
$$
如果 x < 0，而 y≥0，则 x ≡ (y mod m) 等价于 x % m + m == y % m
$$
\begin{matrix}
-10\ \%\ 3== -1 + 3 == 2\\
-4\ \%\ 3 == -1 + 3 == 2\\
5\ \%\ 3==2
\end{matrix}
$$
能够看到，为了防止思考正负数，能够对立应用 (x % m + m) % m 对 x 取模，如此无论 x 为正负数，余数都能转换到 [0,m) 范畴内。
题解（同余分组 + 贪婪）
这道题仍然考同余性质。
依据同余性质，如果 x 和 y 对模 value 同余，那么通过若干次操作后 x 总能转换为 y。如果 x 和 y 对模 value 不同余，那么无论通过多少次操作 x 也无奈转换为 y。
举个例子：{-10、-4、-1、2、5} 都对模 3 同余，而 1 对模 3 不同余。只有通过若干次 +value/-value，总能转换为同余的其余数；
- -10 + 3 * 2 = -4
- -10 + 3 * 3 = -1
- -10 + 3 * 4 = 2
- -10 + 3 * 5 = 5
- 其它同理。
- -10 无奈转换为 1
贪婪思路：持续剖析题目，因为不同分组中的数不可能转换为其它分组的数，为了让指标 “的确的最小非负整数尽可能大”，应该取尽可能小的同余数，否则无奈使后果更优。
举个例子，假如 value 为 3，且不同分组的个数如下：
- 余数为 0 的分组中有 3 个元素：应该取 0、3、6
- 余数为 1 的分组中有 4 个元素：应该取 1、4、7、10
- 余数为 2 的分组中有 1 个元素：应该取 2、[缺失 5]
如果余数为 0 的分组取 0、6、9，则缺失的元素会变成 4。
class Solution {fun findSmallestInteger(nums: IntArray, value: Int): Int {
// 同余分组
val buckets = HashMap<Int, Int>()
for (num in nums) {val mod = (num % value + value) % value
buckets[mod] = buckets.getOrDefault(mod, 0) + 1
}
// 试错
var mex = 0
while (true) {
val mod = mex % value // mex 肯定是非正数
buckets[mod] = buckets.getOrDefault(mod, 0) - 1
// 计数有余
if (buckets[mod]!! < 0) break
mex++
}
return mex
}
}复杂度剖析：
- 工夫复杂度：$O(n)$ 其中 $n$ 为 $nums$ 数组的长度，计数工夫为 $O(n)$，试错最多尝试 $n$ 次，整体工夫复杂度为 $O(n)$；
- 空间复杂度：$O(value)$ 散列表最多记录 $value$ 个分组。
类似题目：
- 264. 丑数 II
OK，这场周赛就讲这么多，咱们下周见。