gpt4 book ai didi

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

转载 作者:我是一只小鸟 更新时间:2023-03-22 22:32:12 30 4
gpt4 key购买 nike

本文已收录到 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-integer-after-operations/ 。

题目描述

给你一个下标从   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,这场周赛就讲这么多,我们下周见.

最后此篇关于刷爆LeetCode周赛337,位掩码/回溯/同余/分桶/动态规划·打家劫舍/贪心的文章就讲到这里了,如果你想了解更多关于刷爆LeetCode周赛337,位掩码/回溯/同余/分桶/动态规划·打家劫舍/贪心的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com