本文已收录到 AndroidFamily,技能和职场问题,请重视公众号 [彭旭锐] 提问。
大家好,我是小彭。
上周末是 LeetCode 第 337 场周赛,你参加了吗?这场周赛第三题有点放水,假如依照标题的数据量来说最多算 Easy 题,但假如依照动态规划来做能够算 Hard 题。
周赛概览
2595. 奇偶位数(Easy)
- 题解一:模仿 O(lgn)O(lgn)
- 题解二:位掩码 + bitCount O(1)O(1)
2596. 查看骑士巡视计划(Medium)
- 题解一:模仿 O(n2)O(n^2)
2597. 美丽子集的数目(Medium)
- 题解一:回溯 O(2n)O(2^n)
- 题解二:同余分组 + 动态规划 / 打家劫舍 O(nlgn)O(nlgn)
2598. 履行操作后的最大 MEX(Medium)
- 题解一:同余分组 + 贪心 O(n)O(n)
2595. 奇偶位数(Easy)
标题地址
leetcode.cn/problems/nu…
标题描绘
给你一个 正 整数 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)O(U) 其间 UU 是整数二进制位长度;
- 空间复杂度:O(1)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(lgn)
- 空间复杂度:O(1)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)O(1) Java Integer.bitCount() 库函数的时刻复杂度是 O(1)O(1),假如依照惯例实现是 O(lgn)O(lgn);
- 空间复杂度:O(1)O(1)
2596. 查看骑士巡视计划(Medium)
标题地址
leetcode.cn/problems/ch…
标题描绘
骑士在一张 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⋅n2)O(Cn^2) 其间 CC 是骑士的行走方向,CC 为常数 8;
- 空间复杂度:O(1)O(1)
2597. 美丽子集的数目(Medium)
标题地址
leetcode.cn/problems/th…
标题描绘
给你一个由正整数组成的数组 nums
和一个 正 整数 k
。
假如 nums
的子会集,任意两个整数的肯定差均不等于 k
,则认为该子数组是一个 美丽 子集。
回来数组 nums
中 非空 且 美丽 的子集数目。
nums
的子集界说为:能够经由 nums
删去某些元素(也或许不删去)得到的一个数组。只要在删去元素时挑选的索引不同的情况下,两个子集才会被视作是不同的子集。
准备知识
- 同余性质:
假如 x % m == y % m
,则称 x 和 y 对模 m 同余,即为 x ≡ (y mod m)
- 乘法定理:
假如某个使命有 n 个环节,每个环节分别有 m1,m2,m3,…,mn{m_1, m_2, m_3, …, m_n} 种计划,那么完成使命的总计划数便是 m1∗m2∗m3∗…∗mnm_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(2n)O(2^n) 其间 nn 为 numsnums 数组长度,每个位置有选和不选两种状况,每个状况的时刻复杂度是 O(1)O(1),因而全体时刻复杂度是 O(2n)O(2^n);
- 空间复杂度:O(C)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 为止的计划数,则有递推联系:
假如不选 aia_i,那么 ai−1a_{i-1} 必定可选,即 dp[i−1]dp[i-1] 的计划数。
假如挑选 aia_i,那么需要考虑 ai−1a_{i-1} 与 aia_i 的联系:
- 假如 ai−ai−1=ka_i – a_{i-1} =k,那么 aia_i 与 ai−1a_{i-1} 不能一起挑选,dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2] 表明在 ai−1a_{i-1} 和 ai−2a_{i-2} 上的计划数之和;
- 假如 ai−ai−1=ka_i – a_{i-1} \not=k,那么 aia_i 与 ai−1a_{i-1} 能够一起挑选 dp[i]=dp[i−1]∗2dp[i] = dp[i-1]*2
最终,还需要考虑数字重复的情况,设 c_i 表明 a_i 的呈现次数:
- 假如不选 aia_i,则只要 1 种计划,即空集;
- 假如挑选 aia_i,则有 2ci2^{c_i} 种计划,最终在减去 1 个空集计划。
整理到递归公式中有:
以 [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)O(nlgn + n) 其间 nn 为 numsnums 数组的长度,运用有序集合进行分组的时刻复杂度是 O(nlgn)O(nlgn),枚举分组的过程每个元素最多拜访一次,时刻复杂度是 O(n)O(n);
- 空间复杂度 O(n)O(n):有序集合空间 O(n)O(n),动态规划过程中运用滚动数组空间为 O(1)O(1)。
类似标题
- 78. 子集
- 784. 字母巨细写全排列
- 198. 打家劫舍
近期周赛子集问题:
LeetCode 周赛 333 无平方子集计数(Medium)
2598. 履行操作后的最大 MEX(Medium)
标题地址
leetcode.cn/problems/sm…
标题描绘
给你一个下标从 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
假如 x 和 y 都小于 0,则 x ≡ (y mod m)
等价于 x % m == y % m
假如 x < 0,而 y≥0,则 x ≡ (y mod m)
等价于 x % m + m == y % m
能够看到,为了防止考虑正负数,能够一致运用 (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)O(n) 其间 nn 为 numsnums 数组的长度,计数时刻为 O(n)O(n),试错最多尝试 nn 次,全体时刻复杂度为 O(n)O(n);
- 空间复杂度:O(value)O(value) 散列表最多记载 valuevalue 个分组。
类似标题:
- 264. 丑数 II
OK,这场周赛就讲这么多,咱们下周见。
本文正在参加「金石计划」