乐趣区

关于android:LeetCode-周赛-333你管这叫-Medium-难度

jiezi

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

大家好，我是小彭。

上周是 LeetCode 第 333 场周赛，你加入了吗？这场周赛品质很高，但难度标得不对，我真的会谢。算法解题思维须要长时间锤炼，退出咱们一起刷题吧~

小彭的 Android 交换群 02 群曾经建设啦，公众号回复“加群”退出咱们~

2570. 合并两个二维数组 – 求和法（Easy）

题目地址

https://leetcode.cn/problems/…

题目形容

给你两个 二维 整数数组 nums1 和 nums2.

  • nums1[i] = [idi, vali] 示意编号为 idi 的数字对应的值等于 vali。
  • nums2[i] = [idi, vali] 示意编号为 idi 的数字对应的值等于 vali。

每个数组都蕴含 互不雷同  的 id，并按 id 以  递增 顺序排列。

请你将两个数组合并为一个按 id 以递增顺序排列的数组，并合乎下述条件：

  • 只有在两个数组中至多呈现过一次的 id 能力蕴含在后果数组内。
  • 每个 id 在后果数组中 只能呈现一次，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id，则认为其对应的值等于 0。

返回后果数组。返回的数组须要按 id 以递增顺序排列。

题解

简略模拟题，应用双指针合并数组即可。

class Solution {fun mergeArrays(nums1: Array<IntArray>, nums2: Array<IntArray>): Array<IntArray> {
        val n = nums1.size
        val m = nums2.size
        val result = LinkedList<IntArray>()
        var index1 = 0
        var index2 = 0
        while (index1 < n && index2 < m) {val e1 = nums1[index1]
            val e2 = nums2[index2]
            if (e1[0] == e2[0]) {result.add(intArrayOf(e1[0], e1[1] + e2[1]))
                index1++
                index2++
            } else if (e1[0] < e2[0]) {result.add(e1)
                index1++
            } else {result.add(e2)
                index2++
            }
        }
        while (index1 < n) {result.add(nums1[index1++])
        }
        while (index2 < m) {result.add(nums2[index2++])
        }
        return result.toTypedArray()}
}

复杂度剖析：

  • 工夫复杂度：$O(n + m)$
  • 空间复杂度：$O(1)$

2571. 将整数缩小到零须要的起码操作数（Medium）

题目地址

https://leetcode.cn/problems/…

题目形容

给你一个正整数 n，你能够执行下述操作 任意 次：

  • n 加上或减去 2 的某个 幂

返回使 n 等于 0 须要执行的 起码 操作数。

如果 x == 2i 且其中 i >= 0，则数字 x 是 2 的幂。

题解一（贪婪 + 记忆化递归）

这道题在比赛时的标签是 Easy，实际上应该是 Medium，收录到题库后官网也改成 Medium 了。

题目显著是决策模型，首先要想到回溯、贪婪、动静布局等思路。

如果用暴力回溯如何解决呢？显然，在每一轮决策中，咱们能够抉择数字的二进制示意中任意一个“1”，并相应地加上 $2^k$ 或减去 $2^k$，终止条件为剩下最初一个“1”时，必然减去 $2^k$。

事实上，咱们发现在每一轮决策中并不需要枚举所有抉择，只须要从最低位的“1”开始打消，最终总能失去最优解。这是因为最低位受到的束缚最小，低位的加法会影响高位并产生间断的 111，有可能使后果更优，而高位的加减对低位没有影响，不会对后果产生更优解。

所以咱们的算法是：获取以后数字最低位的 $1= 2^k$，尝试加上 $2^k$ 或减去 $2^k$ 并将问题转换为规模更小的数，直到剩下的数正好是 2 的幂完结。递归过程中会存在反复状态，所以须要加上记忆化剪枝。

class Solution {
    // 备忘录
    private val memo = HashMap<Int, Int>()

    fun minOperations(n: Int): Int {
        // n 是 2 的幂
        if (n and (n - 1) == 0) return 1
        if (memo.containsKey(n)) return memo[n]!!
        // 最低位 1
        val lowbit = n and -n
        val result = 1 + Math.min(minOperations(n + lowbit), minOperations(n - lowbit))
        memo[n] = result
        return result
    }
}

复杂度剖析：

  • 工夫复杂度：$O(C)$ 其中 $C$ 是所有测试用例合并的状态数，每个状态的工夫复杂度是 $O(1)$。如果以单个测试用例剖析复杂度，则工夫复杂度是 $O(c)$，$c$ 是 int 的位数。
  • 空间复杂度：$O(C)$ 散列表空间。

题解二（贪婪 + 统计 1 的个数）

咱们发现：当执行某个操作后，使得二进制中 1 的个数更少的计划最终总的操作次数肯定更低。

例如：当最低位 1 是间断的多个 111 时，采纳加法能够一次性打消多个“1”，否则减法固定打消单个“1”更优。

  • 1011, 1101：加法后 = 1011, 1110，减法后：1011, 1100（减法更优）

  • 1011, 1111：加法后 = 1100, 0000，减法后：1011, 1110（加法更优）

    因而咱们的算法是：在每一步抉择中间接以试错的形式做贪婪抉择，先比拟操作后后果中二进制中 1 的个数，再抉择更优的操作。

class Solution {fun minOperations(n: Int): Int {
        var num = n
        var operateCount = 0
        while (num != 0) {
            // 最低位 1
            val lowbit = num and -num
            // 直接判断
            if (Integer.bitCount(num + lowbit) <= Integer.bitCount(num - lowbit)) {num += lowbit} else {num -= lowbit}
            operateCount++
        }
        return operateCount
    }
}

复杂度剖析：

  • 工夫复杂度：$O(mlgm)$ 其中 $m$ 是数字中 1 的个数，单次统计位 1 的操作工夫复杂度是 $O(lgm)$。
  • 空间复杂度：$O(1)$ 只应用常数级别空间。

题解三（位运算优化）

思路参考：灵茶山艾府的题解

持续题解二的思路，间断多个 1 的最优解是先加上 lowbit 再减去 lowbit，那么最多须要操作两次，而单个 1 的最优解是间接减去 lowbit，最多只有操作一次。

咱们发现：

// 间断 1 的状况：n        = 0011, 1111
3n       = 1011, 1101
n xor 3n = 1000, 0010 // 正好失去 2 个 1

// 单个 1 的状况：n        = 0100
3n       = 1100
n xor 3n = 1000 // 正好失去 1 个 1

因而答案就是 n xor 3n 中 1 的个数。

class Solution {fun minOperations(n: Int): Int {return Integer.bitCount(n xor 3 * n)
    }
}

复杂度剖析：

  • 工夫复杂度：$O(1)$
  • 空间复杂度：$O(1)$

2572. 无平方子集计数（Medium）

题目地址

https://leetcode.cn/problems/…

题目形容

给你一个正整数数组 nums。

如果数组 nums 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个  无平方 子集。

无平方因子数 是无奈被除 1 之外任何平方数整除的数字。

返回数组 nums 中 无平方  且  非空 的子集数目。因为答案可能很大，返回对 109 + 7 取余的后果。

nums 的 非空子集 是能够由删除 nums 中一些元素（能够不删除，但不能全副删除）失去的一个数组。如果形成两个子集时抉择删除的下标不同，则认为这两个子集不同。

准备常识

  • 质数 / 素数：只能被 1 和自身整除的数，例如 3，5，7；
  • 合数：除了能被 1 和自身整除外，还能被其余数整除的数。也能够了解为由多个不为 1 的质数相乘组成的数，例如 4 = 2 2，6 = 2 3。
  • 1 既不是质数也不是合数。
  • 质因数分解：将合数合成为多个质数相乘的模式，其中的质数就是合数的质因子。例如 10 蕴含质因子 2 和 5，12 蕴含质因子 2 和 3。
  • 状态压缩：用一个维度（通常是二进制数）示意所有物品存在或不存在的状态。

题解一（状态压缩 + 01 背包）

这道题的标签是 Medium，但实际上是 Hard。

题目的外围是求“乘积是无平方因子数的子集”数目，显然有：

  • 1、当子集中存在平方数时，该子集肯定不是解。 例如子集中存在 4 或 9 或 25 时，子集的乘积肯定存在平方因子；
  • 2、当子集中任意两个数存在雷同的质因子时，该子集肯定不是解。 例如子集中存在 6 和 2，这两个数都存在雷同的质因子 “2”，因而它们的乘积肯定存在平方因子。

  • 3、咱们察看到本题的输出数据范畴只有 [1, 30]，30 以内的质数只有 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 总共 10 个数，所以咱们能够事后对 2 ~ 30 的数字进行质因数分解，并且应用二进制掩码 Mask 记录数字是否蕴含某个质因子。 例如：

    • 00, 0000, 0011：示意存在质因子 2 和 3
    • 11, 1111, 1111：示意存在所有质因子（只是举例，本题不存在）

所以，咱们的算法思路应该是：从数字列表抉择中若干个数，如果所有质因子的呈现次数不超过 1，则能够组成非法的子集， 例如 [3, 5] 中所有质因子最多只呈现 1 次，因而形成一个非法的子集。

“从数字列表抉择中若干个数”， 由此咱们发现原问题能够转换为相熟背包问题 —— 计算背包能够包容的物品组合计划数：

  • 物品：每一个数字是一个不可分割的物品，咱们不可能抉择半个数；
  • 物品体积：每个物品所蕴含的质因子就是该物品的体积；
  • 背包容积：背包容积为 10，即背包最多只能蕴含 10 个质因子；
  • 限度条件：背包内的数字的质因子不能反复。

实现问题转换后，依照相熟的背包问题模板解决即可：

  • 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i - 1][j xor mask]
class Solution {

        companion object {
        private val MOD = 1000000007
        private val primeList = listOf(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
        private val masks = IntArray(31).apply {for (i in 2..30) {for ((j, prime) in primeList.withIndex()) {
                    // 过滤平方因子数
                    if (i % (prime * prime) == 0) {this[i] = -1
                        break
                    }
                    // 记录质因子
                    if (i % prime == 0) this[i] = this[i] or (1 shl j)
                }
            }
        }
    }

    fun squareFreeSubsets(nums: IntArray): Int {
        // 背包问题

        // 过滤平方因子数（数字 1 的 mask == 0）val numsFiltered = nums.filter {masks[it] >= 0 }
        // 物品总数
        val n = numsFiltered.size
        // 背包容积 11,1111,1111
        val amount = (1 shl 10) - 1
        // dp[i][j] 示意抉择前 i 个物品且体积为 j 的计划数
        val dp = Array(n + 1) {IntArray(amount + 1) }.apply {
            // 抉择前 i 个物品且体积为 0 的计划为 1
            this[0][0] = 1
        }
        // 枚举物品
        for (i in 1..n) {
            // 物品的质因子属性
            val mask = masks[numsFiltered[i - 1]]
            // 枚举体积
            for (j in 0..amount) {dp[i][j] = dp[i - 1][j]
                // j | mask == j => mask 是 j 的子集
                if (j or mask == j) dp[i][j] += dp[i - 1][j xor mask]
            }
        }
        // 题目不要求背包装满，所以 dp[n - 1][...] 的计划都蕴含，最初再去掉空集
        return dp[n].sum() - 1}
}

思考大数越界问题：

fun squareFreeSubsets(nums: IntArray): Int {
    // 背包问题

    // 过滤平方因子数（数字 1 的 mask == 0）val numsFiltered = nums.filter {masks[it] >= 0 }
    // 物品总数
    val n = numsFiltered.size
    // 背包容积 11,1111,1111
    val amount = (1 shl 10) - 1
    // dp[i][j] 示意抉择前 i 个物品且体积为 j 的计划数
    val dp = Array(n + 1) {IntArray(amount + 1) }.apply {
        // 抉择前 i 个物品且体积为 0 的计划为 1
        this[0][0] = 1
    }
    // 枚举物品
    for (i in 1..n) {
        // 物品的质因子属性
        val mask = masks[numsFiltered[i - 1]]
        // 枚举体积
        for (j in 0..amount) {dp[i][j] = dp[i - 1][j]
            // j | mask == j => mask 是 j 的子集
            if (j or mask == j) dp[i][j] = (dp[i][j] + dp[i - 1][j xor mask]) % MOD
        }
    }
    // 题目不要求背包装满，所以 dp[n - 1][...] 的计划都蕴含，最初再去掉空集
    var sum = 0L
    for (count in dp[n]) {sum += count}
    return ((sum - 1 + MOD) % MOD).toInt()}

01 背包问题能够勾销物品维度升高空间复杂度：

fun squareFreeSubsets(nums: IntArray): Int {
    // 背包问题

    // 物品总数
    val n = nums.size
    // 背包容积 11,1111,1111
    val amount = (1 shl 10) - 1
    // dp[i][j] 示意抉择前 i 个物品且体积为 j 的计划数
    val dp = IntArray(amount + 1).apply {
        // 抉择前 i 个物品且体积为 0 的计划为 1
        this[0] = 1
    }
    // 枚举物品
    for (i in 1..n) {
        // 物品的质因子属性
        val mask = masks[nums[i - 1]]
        // 过滤平方因子数
        if (mask < 0) continue
        // 枚举体积（从大到小遍历）for (j in amount downTo 0) {
            // j | mask == j => mask 是 j 的子集
            if (j or mask == j) dp[j] = (dp[j] + dp[j xor mask]) % MOD
        }
    }
    // 题目不要求背包装满，所以 dp[n - 1][...] 的计划都蕴含，最初再去掉空集
    var sum = 0L
    for (count in dp) {sum += count}
    return ((sum - 1 + MOD) % MOD).toInt()}

复杂度剖析：

  • 工夫复杂度：$O(n^{2m})$ 其中 $n$ 是 $nums$ 数组的长度，$m$ 是质数的个数（m ≤ 10）。
  • 空间复杂度：$O(2^{2m} + 31)$ $dp$ 数组空间与预处理的二进制掩码数组。

题解二（计数优化）

题解一还有优化空间。

在外层循环中，咱们枚举的是物品维度，如果同一个物品中存在多个时，会存在反复计算。因而，咱们能够预处理物品列表，统计不同物品的呈现次数。举例说明：

  • 在物品列表 [3, 3, 5] 中物品 [3] 呈现了两次，而这两个物品 3 都能够和物品 [5] 组成指标子集，总个数 = [3] 呈现次数 * 其余子集个数；
  • 物品 1 较非凡，在物品列表 [1, 1, 5] 中，物品 [1] 能够与物品 [5] 组成指标子集，同时任意个数的 [1, 1] 也能够 [5] 组成指标子集，总个数 = $2^{[1] 呈现次数}$ * 其余子集个数；
class Solution {

    companion object {
        private val MOD = 1000000007
        private val primeList = listOf(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
        private val masks = IntArray(31).apply {for (i in 2..30) {for ((j, prime) in primeList.withIndex()) {
                    // 过滤平方因子数
                    if (i % (prime * prime) == 0) {this[i] = -1
                        break
                    }
                    // 记录质因子
                    if (i % prime == 0) this[i] = this[i] or (1 shl j)
                }
            }
        }
    }

    fun squareFreeSubsets(nums: IntArray): Int {
        // 元素计数
        var pow1 = 1L
        val cnts = IntArray(31).apply {for (element in nums) {if (element == 1) pow1 = pow1 * 2 % MOD else this[element]++
            }
        }
        // 物品总数
        val n = nums.size
        // 背包容积 11,1111,1111
        val amount = (1 shl 10) - 1
        // dp[i][j] 示意抉择前 i 个物品且体积为 j 的计划数
        val dp = LongArray(amount + 1).apply {
            // 抉择前 i 个物品且体积为 0 的计划为 1
            this[0] = 1
        }
        // 枚举去重物品
        for ((num, cnt) in cnts.withIndex()) {
            // 物品的质因子属性
            val mask = masks[num]
            // 过滤不存在的物品
            if (cnt <= 0) continue
            // 过滤平方因子数和 1 
            if (mask <= 0) continue
            // 枚举体积（从大到小遍历）for (j in amount downTo 0) {
                // j | mask == j => mask 是 j 的子集
                if (j or mask == j) dp[j] = (dp[j] + dp[j xor mask] * cnt) % MOD
            }
        }
        // 题目不要求背包装满，所以 dp[n - 1][...] 的计划都蕴含，最初再去掉空集
        var sum = 0L
        for (count in dp) {sum = (sum + count) % MOD
        }
        // 1 的任意组合能够与其余子集组合
        return ((sum * pow1 - 1 + MOD) % MOD).toInt()}
}

复杂度剖析：

  • 工夫复杂度：$O(n + q^{2m})$ 其中 $n$ 是 $nums$ 数组的长度，$m$ 是质数的个数（m ≤ 10），$q$ 是输出数据范畴内非平方因子数的个数 $（q ≤ 18）$
  • 空间复杂度：$O(2^{2m} + 31)$ $dp$ 数组空间与预处理的二进制掩码数组。

2573. 找出对应 LCP 矩阵的字符串（Hard）

题目地址

https://leetcode.cn/problems/…

题目形容

对任一由 n 个小写英文字母组成的字符串 word，咱们能够定义一个 n x n 的矩阵，并满足：

  • lcp[i][j] 等于子字符串 word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。

给你一个 n x n 的矩阵 lcp。返回与 lcp 对应的、按字典序最小的字符串 word。如果不存在这样的字符串，则返回空字符串。

对于长度雷同的两个字符串 a 和 b，如果在 a 和 b 不同的第一个地位，字符串 a 的字母在字母表中呈现的程序先于 b 中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca"，因为二者不同的第一地位是第三个字母，而 'b' 先于 'c' 呈现。

准备常识

LCP 矩阵的定义是一个字符串中的 [i, 字符串开端] 和 [j, 字符串开端] 两个子串的最长公共前缀的长度。依据定义能够得出根本性质：

  • 性质 1：当 LCP[i][j] 等于 0 时，位于 str[i] 与 str[j] 的两个字符肯定不雷同；反之当 LCP[i][j] 大有 0 时，位于 str[i] 与 str[j] 的两个字符肯定雷同。

  • 性质 2：LCP 矩阵的定义能够利用动静布局推导（与两个字符串的最长公共前缀相似）：

    • 当 str[i] == str[j] 时，LCP[i][j] = 0（无独特前缀）
    • 当 str[i] == str[j] 时，LCP[i][j] = LCP[i + 1][j + 1] + 1

题解（贪婪结构 + 动静布局）

贪婪思路：题目要求输入满足 LCP 矩阵的字典序最小的后果，那么咱们应该优先选择数值最小的字母‘a’。

能够用反证法证实：假如 “bcbc” 是满足条件且字典序最小的后果，那么咱们能够将 ‘b’ 映射为 ‘a’，而 ‘c’ 映射为 ‘b’ 失去 “abab”。因为 LCP 矩阵只思考公共前缀长度而不思考字母，所以 “abab” 肯定合乎同一个 LCP 矩阵定义，与假如矛盾。

因而，咱们的算法思路是：从 s[0] 开始填入 ‘a’，并依据 LCP[0][j] > 0 将所有 s[j] 设置为同一个字符 ‘a’，依此类推。从下一个未填入的地位开始填入 ‘b’，并将所有雷同的 LCP[i][j] > 0 的地位填入 ‘b’，直到字符串完结或候选字符大于 ‘z’ 完结。

class Solution {fun findTheString(lcp: Array<IntArray>): String {
        // 指标字符串长度
        val n = lcp.size
        // 1、结构字符串
        // 指标字符串
        val charArray = CharArray(n) {' '}
        // 候选字符序列 'a' -> 'z'
        var candidate = 'a'
        var i = 0
        while (i < n) {
            // 以后地位曾经填充
            if (charArray[i] != ' ') {
                i++
                continue
            }
            // 候选字符不够
            if (candidate > 'z') {return ""}
            // 填充雷同字符的地位，并且应用字典序最小的候选字符
            for (j in i until n) {if (lcp[i][j] > 0) charArray[j] = candidate
            }
            // 下一个候选字符
            candidate += 1
            i++
        }
        return String(charArray)
    }
}

应用贪婪算法结构出字符串后，咱们还须要查看字符串是否合乎 LCP 矩阵的定义。这是因为结构时只思考 Lcp[i][j] > 0，但至于具体大于 0 的什么数并没有思考，所以咱们还须要验证的过程：

class Solution {fun findTheString(lcp: Array<IntArray>): String {
        // 指标字符串长度
        val n = lcp.size
        // 1、结构字符串
        ...
        // 2、查看字符串是否合乎 LCP（因为结构时只思考 lcp[i][j] > 0）for (i in n - 1 downTo 0) {for (j in n - 1 downTo 0) {if (charArray[i] == charArray[j]) {if (i == n - 1 || j == n - 1) {if (lcp[i][j] != 1) return ""
                    } else {if (lcp[i][j] != lcp[i + 1][j + 1] + 1) return ""
                    }
                } else {if (lcp[i][j] != 0) return ""
                }
            }
        }
        return String(charArray)
    }
}

复杂度剖析：

  • 工夫复杂度：$O(n^2)$ 结构与验证都是 $O(n^2)$ 级别。
  • 空间复杂度：$O(1)$ 不思考后果字符串，只应用了常数级别变量。
退出移动版