LeetCode 双周赛 104（2023/05/13）流水的动

2023-05-13  本文已影响0人  彭旭锐

T1. 老人的数目（Easy）

T2. 矩阵中的和（Medium）

T3. 最大或值（Medium）

T4. 英雄的力量（Hard）

T1. 老人的数目（Easy）

https://leetcode.cn/problems/number-of-senior-citizens/

简单模拟题，直接截取年龄字符后计数即可：

class Solution {
    fun countSeniors(details: Array<String>): Int {
        return details.count { it.substring(11, 13).toInt() > 60 }
    }
}

除了将字符串转为整数再比较外，还可以直接比较子串与 “60” 的字典序：

class Solution {
    fun countSeniors(details: Array<String>): Int {
        return details.count { it.substring(11, 13) > "60" }
    }
}

复杂度分析：

T2. 矩阵中的和（Medium）

https://leetcode.cn/problems/sum-in-a-matrix/

简单模拟题。

先对每一行排序，再取每一列的最大值。

class Solution {
    fun matrixSum(nums: Array<IntArray>): Int {
        var ret = 0
        for (row in nums) {
            row.sort()
        }
        for (j in 0 until nums[0].size) {
            var mx = 0
            for (i in 0 until nums.size) {
                mx = Math.max(mx, nums[i][j])
            }
            ret += mx
        }
        return ret
    }
}

复杂度分析：

T3. 最大或值（Medium）

https://leetcode.cn/problems/maximum-or/

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 **nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

提示：

问题结构化

1、概括问题目标

计算可以获得的最大或值。

2、分析问题要件

在每次操作中，可以从数组中选择一个数乘以 2，亦相当于向左位移 1 位。

3、观察问题数据

4、观察测试用例

以示例 1 nums=[12, 9], k = 1 为例，最优答案是对 9 乘以 2，说明操作最大值并不一定能获得最大或值。

5、提高抽象程度

6、具体化解决手段

题解一（贪心 + 前后缀分解）

枚举所有数字并向左位移 k 次，计算所有方案的最优解：

class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 前后缀分解
        val pre = IntArray(n + 1)
        val suf = IntArray(n + 1)
        for (i in 1 .. n) {
            pre[i] = pre[i - 1] or nums[i - 1]
        }
        for (i in n - 1 downTo 0) {
            suf[i] = suf[i + 1] or nums[i]
        }
        var ret = 0L
        for (i in nums.indices) {
            ret = Math.max(ret, (1L * nums[i] shl k) or pre[i].toLong() or suf[i + 1].toLong())
        }
        return ret
    }
}

由于每个方案都需要枚举前后 n - 1 个数字的或值，因此这是一个 O(n^2) 的解法，会超出时间限制。我们可以采用空间换时间的策略，预先计算出每个位置（不包含）的前后缀的或值，这个技巧就是「前后缀分解」。

在实现细节上，我们可以把其中一个前缀放在扫描的时候处理。

class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 前后缀分解
        val suf = IntArray(n + 1)
        for (i in n - 1 downTo 0) {
            suf[i] = suf[i + 1] or nums[i]
        }
        var ret = 0L
        var pre = 0L
        for (i in nums.indices) {
            ret = Math.max(ret, pre or (1L * nums[i] shl k) or suf[i + 1].toLong())
            pre = pre or nums[i].toLong()
        }
        return ret
    }
}

复杂度分析：

题解二（动态规划）

使用背包问题模型时，定义 dp[i][j] 表示在前 i 个元素上操作 k 次可以获得的最大或值，则有：

 class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 以 i 为止，且移动 k 次的最大或值
        val dp = Array(n + 1) { LongArray(k + 1) }
        for (i in 1 .. n) {
            for (j in 0 .. k) {
                for (m in 0 .. j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - m] or (1L * nums[i - 1] shl m) /* 移动 m 次 */)
                }
            }
        }
        return dp[n][k]
    }
}

另外，这个背包问题可以取消物品维度来优化空间：

class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 以 i 为止，且移动 k 次的最大或值
        val dp = LongArray(k + 1)
        for (i in 1 .. n) {
            // 逆序
            for (j in k downTo 0) {
                for (m in 0 .. j) {
                    dp[j] = Math.max(dp[j], dp[j - m] or (1L * nums[i - 1] shl m) /* 移动 m 次 */)
                }
            }
        }
        return dp[k]
    }
}

相似题目：

T4. 英雄的力量（Hard）

https://leetcode.cn/problems/power-of-heroes/

题目描述

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。

示例 1：

输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 22 * 2 = 8 。
第 2 组：[1] 的力量为 12 * 1 = 1 。
第 3 组：[4] 的力量为 42 * 4 = 64 。
第 4 组：[2,1] 的力量为 22 * 1 = 4 。
第 5 组：[2,4] 的力量为 42 * 2 = 32 。
第 6 组：[1,4] 的力量为 42 * 1 = 16 。
第 7 组：[2,1,4] 的力量为 42 * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

示例 2：

输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。

提示：

问题结构化

1、概括问题目标

计算所有组合方案的「力量」总和。

2、分析问题要件

枚举所有子集，计算子集的力量值计算公式为「最大值^2*最小值」。

3、观察问题数据

4、观察问题测试用例：

以数组 nums=[1, 2, 3] 为例：

子集 最大值 最小值 力量值
{} 0 0 0
{1} 1 1 1^2*1
{2} 2 2 2^2*2
{3} 3 3 3^2*3
子集 最大值 最小值 力量值
{1, 2} 2 1 2^2*1
{1, 3} 3 1 3^2*1
{2, 3} 3 2 3^2*2
子集 最大值 最小值 力量值
{1, 2, 3} 3 1 3^2*1

5、如何解决问题

至此，问题陷入瓶颈，解决方法是重复以上步骤，枚举掌握的数据结构、算法和技巧寻找思路，突破口在于从另一个角度来理解问题规模（动态规划的思路）。

6、继续观察问题测试用例

同样以数组 nums = [1, 2, 3] 为例：

子集 最大值 最小值
{} 0 0
子集 最大值 最小值
{} 0 0
{1} 1 1
子集 最大值 最小值
{} 0 0
{1} 1 1
{2} 2 2
{1, 2} 2 1
子集 最大值 最小值
{} 0 0
{1} 1 1
{2} 2 2
{1, 2} 2 1
{3} 3 3
{1,3} 3 1
{2,3} 3 2
{1,2,3} 3 1

这又说明了什么呢？

我们发现子集问题可以用递推地方式构造，当我们增加考虑一个新元素时，其实是将已有子集复制一份后，再复制的子集里添加元素。例如我们在考虑「2」时，是将 {} 和 {1} 复制一份后添加再添加元素「2」。

由于我们是从小到大增加元素，所以复制后新子集中的最大值一定等于当前元素，那么问题的关键就在「如何计算这些新子集的最小值」。

由于我们采用子集复制的方式理解子集构造问题，容易发现数字越早出现，最小值出现次数越大（哆啦 A 梦的翻倍药水）。

例如最初最小值为 1 的子集个数为 1 次，在处理「2」后最小值为 1 的子集个数为 2 次，因此在处理「3」时，就会累加 2 次以 1 为最小值的力量值：2*(3^2*1)。同理会累加 1 次以 2 为最小值的力量值：1*(3*2*2)，另外还要累加从空集转移而来的 {3}。

至此，问题的解决办法逐渐清晰。

7、解决问题的新手段

考虑有 a, b, c, d, e 五个数，按顺序从小到大排列，且从小到大枚举。

当枚举到 d 时，复制增加的新子集包括：

另外还有以 d 本身为最小值的子集 1 个：累加力量值 1*(d^2*d)，将 d 左侧元素对结果的贡献即为 s，则有 pow(d) = d^2*(s + d)。

继续枚举到 e 是，复制增加的新子集包括：

另外还有以 e 本身为最小值的子集 1 个：累加力量值 1*(e^2*e)，将 e 左侧元素对结果的贡献即为 s`，则有 pow(e) = e^2*(s` + e)。

观察 s 和 s` 的关系：

s = 4*a + 2*b + 1*c

s = 8*a + 4*b + 2*c + d = s*2 + d

这说明，我们可以维护每个元素左侧元素的贡献度 s，并通过 s 来计算当前元素新增的所有子集的力量值，并且时间复杂度只需要 O(1)！

[4,3,2,1]
 1 1 2 4
追加 5：
[5,4,3,2,1]
 1 1 2 4 8

题解（动态规划）

根据问题分析得出的递归公式，使用递推模拟即可，先不考虑大数问题：

class Solution {
    fun sumOfPower(nums: IntArray): Int {
        var ret = 0L
        // 排序
        nums.sort()
        // 影响因子
        var s = 0L
        for (x in nums) {
            ret += (x * x) * (s + x)
            s = s * 2 + x
        }
        return ret.toInt()
    }
}

再考虑大数问题：

class Solution {
    fun sumOfPower(nums: IntArray): Int {
        val MOD = 1000000007
        var ret = 0L
        // 排序
        nums.sort()
        // 影响因子
        var s = 0L
        for (x in nums) {
            ret = (ret + (1L * x * x % MOD) * (s + x)) % MOD // x*x 也可能溢出
            s = (s * 2 + x) % MOD
        }
        return ret.toInt()
    }
}

实战中我用的是先计算最大影响因子，再累减的写法：

class Solution {
    fun sumOfPower(nums: IntArray): Int {
        val MOD = 1000000007
        var ret = 0L
        val n = nums.size
        // 排序
        nums.sortDescending()
        // 影响因子
        var s = 0L
        var p = 1L
        for (i in 1 until n) {
            s = (s + nums[i] * p) % MOD 
            p = (2 * p) % MOD
        }
        // 枚举子集
        for (i in 0 until n) {
            val x = nums[i]
            ret = (ret + x * x % MOD * (s + x)) % MOD
            if (i < n - 1) {
                s = (s - nums[i + 1]) % MOD
                if (s and 1L != 0L) {
                    s += MOD // 奇数除 2 会丢失精度
                }
                s = (s / 2) % MOD
            }
        }
        return ret.toInt()
    }
}

复杂度分析：

往期回顾

上一篇下一篇

猜你喜欢

热点阅读