本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
上周末是 LeetCode 第 337 场周赛，你参加了吗？这场周赛第三题有点放水，如果按照题目的数据量来说最多算 Easy 题，但如果按照动态规划来做可以算 Hard 题。
周赛概览
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）
题目地址
题目描述
给你一个 正 整数 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$ 仅使用常量级别空间。
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）
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）
题目地址
题目描述
骑士在一张 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）
题目地址
题目描述
给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。
nums 中 非空 且 美丽 的子集数目。
nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。