刷爆 LeetCode 周赛 337，位掩码 / 回溯 / 同余 / 分桶 / 动态规划·打家劫舍 / 贪心-六虎

本文已收录到 AndroidFamily，技能和职场问题，请重视公众号 [彭旭锐] 提问。

大家好，我是小彭。

上周末是 LeetCode 第 337 场周赛，你参加了吗？这场周赛第三题有点放水，假如依照标题的数据量来说最多算 Easy 题，但假如依照动态规划来做能够算 Hard 题。

周赛概览

2595. 奇偶位数（Easy）

题解一：模仿 $O (l g n)$
题解二：位掩码 + bitCount $O (1)$

2596. 查看骑士巡视计划（Medium）

题解一：模仿 $O(n^2)$

2597. 美丽子集的数目（Medium）

题解一：回溯 $O(2^n)$
题解二：同余分组 + 动态规划 / 打家劫舍 $O (n l g n)$

2598. 履行操作后的最大 MEX（Medium）

题解一：同余分组 + 贪心 $O (n)$

刷爆 LeetCode 周赛 337，位掩码 / 回溯 / 同余 / 分桶 / 动态规划打家劫舍 / 贪心

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)$ 其间 $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 (l g n)$
空间复杂度： $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 (l g n)$ ；
空间复杂度： $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(Cn^2)$ 其间 $C$ 是骑士的行走方向， $C$ 为常数 8；
空间复杂度： $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 个环节，每个环节分别有 ${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$ 为 $n u m s$ 数组长度，每个位置有选和不选两种状况，每个状况的时刻复杂度是 $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 为止的计划数，则有递推联系：

\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}$ 必定可选，即 $d p [i - 1]$ 的计划数。

假如挑选 $a_i$ ，那么需要考虑 $a_{i-1}$ 与 $a_i$ 的联系：

假如 $a_i – a_{i-1} =k$ ，那么 $a_i$ 与 $a_{i-1}$ 不能一起挑选， $d p [i] = d p [i - 1] + d p [i - 2]$ 表明在 $a_{i-1}$ 和 $a_{i-2}$ 上的计划数之和；
假如 $ai−ai−1=ka_i – a_{i-1} \not=k$ ，那么 $a_i$ 与 $a_{i-1}$ 能够一起挑选 $d p [i] = d p [i - 1] * 2$

最终，还需要考虑数字重复的情况，设 c_i 表明 a_i 的呈现次数：

假如不选 $a_i$ ，则只要 1 种计划，即空集；
假如挑选 $a_i$ ，则有 $2^{c_i}$ 种计划，最终在减去 1 个空集计划。

整理到递归公式中有：

\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 (n l g n + n)$ 其间 $n$ 为 $n u m s$ 数组的长度，运用有序集合进行分组的时刻复杂度是 $O (n l g n)$ ，枚举分组的过程每个元素最多拜访一次，时刻复杂度是 $O (n)$ ；
空间复杂度 $O (n)$ ：有序集合空间 $O (n)$ ，动态规划过程中运用滚动数组空间为 $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

10%3==1−4%3==1\begin{matrix} 10\ \% \ 3 == 1\\ -4\ \%\ 3 == 1 \end{matrix}

假如 x 和 y 都小于 0，则 x ≡ (y mod m) 等价于 x % m == y % m

−10%3==−1−4%3==−1\begin{matrix} -10\ \%\ 3== -1\\ -4\ \%\ 3==-1 \end{matrix}

假如 x < 0，而 y≥0，则 x ≡ (y mod m) 等价于 x % m + m == y % m

−10%3==−1+3==2−4%3==−1+3==25%3==2\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$ 为 $n u m s$ 数组的长度，计数时刻为 $O (n)$ ，试错最多尝试 $n$ 次，全体时刻复杂度为 $O (n)$ ；
空间复杂度： $O (v a l u e)$ 散列表最多记载 $v a l u e$ 个分组。

类似标题：

264. 丑数 II

OK，这场周赛就讲这么多，咱们下周见。

本文正在参加「金石计划」

刷爆 LeetCode 周赛 337，位掩码 / 回溯 / 同余 / 分桶 / 动态规划·打家劫舍 / 贪心

周赛概览

2595. 奇偶位数（Easy）

标题地址

标题描绘

题解一（模仿）

题解二（位掩码 + bitCount）

2596. 查看骑士巡视计划（Medium）

标题地址

标题描绘

题解（模仿）

2597. 美丽子集的数目（Medium）

标题地址

标题描绘

准备知识

题解一（暴力回溯）

题解二（同余分组 + 动态规划 / 打家劫舍）

2598. 履行操作后的最大 MEX（Medium）

标题地址

标题描绘

准备知识

题解（同余分组 + 贪心）

作者信息

推广

刷爆 LeetCode 周赛 337，位掩码 / 回溯 / 同余 / 分桶 / 动态规划·打家劫舍 / 贪心

周赛概览

2595. 奇偶位数（Easy）

标题地址

标题描绘

题解一（模仿）

题解二（位掩码 + bitCount）

2596. 查看骑士巡视计划（Medium）

标题地址

标题描绘

题解（模仿）

2597. 美丽子集的数目（Medium）

标题地址

标题描绘

准备知识

题解一（暴力回溯）

题解二（同余分组 + 动态规划 / 打家劫舍）

2598. 履行操作后的最大 MEX（Medium）

标题地址

标题描绘

准备知识

题解（同余分组 + 贪心）

相关文章

CLion开发环境配置完全解析（Qt开发？STM32？速通cmake？

基于java+SpringBoot+vue+element民宿管理系统详细设计

定时任务报警通知解决方案详解

06 从迪迦（光、闪耀、火花）三种形态领悟的知识（实现Spring上下文，提供Bean创建的扩展）

作者信息

推广