T1. 老人的数目(Easy)
T2. 矩阵中的和(Medium)
T3. 最大或值(Medium)
T4. 英雄的力量(Hard)
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" } } }
复杂度分析:
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 } }
复杂度分析:
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 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 15
计算可以获得的最大或值。
在每次操作中,可以从数组中选择一个数乘以 2,亦相当于向左位移 1 位。
以示例 1 nums=[12, 9], k = 1 为例,最优答案是对 9 乘以 2,说明操作最大值并不一定能获得最大或值。
枚举所有数字并向左位移 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(n2)O(n^2)O(n2) 的解法,会超出时间限制。我们可以采用空间换时间的策略,预先计算出每个位置(不包含)的前后缀的或值,这个技巧就是「前后缀分解」。
在实现细节上,我们可以把其中一个前缀放在扫描的时候处理。
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] } }
相似题目:
https://leetcode.cn/problems/power-of-heroes/
给你一个下标从 0 开始的整数数组 nums
,它表示英雄的能力值。如果我们选出一部分英雄,这组英雄的 力量 定义为:
i0
,i1
,… ik
表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik])
。请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大,请你将结果对 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 <= nums.length <= 105
1 <= nums[i] <= 109
计算所有组合方案的「力量」总和。
枚举所有子集,计算子集的力量值计算公式为KaTeX parse error: Expected 'EOF', got '「' at position 1: 「̲最大值^2*最小值」。
以数组 nums=[1, 2, 3] 为例:
子集 | 最大值 | 最小值 | 力量值 |
---|---|---|---|
{} | 0 | 0 | 0 |
{1} | 1 | 1 | 12∗11^2*112∗1 |
{2} | 2 | 2 | 22∗22^2*222∗2 |
{3} | 3 | 3 | 32∗33^2*332∗3 |
子集 | 最大值 | 最小值 | 力量值 |
---|---|---|---|
{1, 2} | 2 | 1 | 22∗12^2*122∗1 |
{1, 3} | 3 | 1 | 32∗13^2*132∗1 |
{2, 3} | 3 | 2 | 32∗23^2*232∗2 |
子集 | 最大值 | 最小值 | 力量值 |
---|---|---|---|
{1, 2, 3} | 3 | 1 | 32∗13^2*132∗1 |
至此,问题陷入瓶颈,解决方法是重复以上步骤,枚举掌握的数据结构、算法和技巧寻找思路,突破口在于从另一个角度来理解问题规模(动态规划的思路)。
同样以数组 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∗(32∗1)2*(3^2*1)2∗(32∗1)。同理会累加 1 次以 2 为最小值的力量值:1∗(3∗2∗2)1*(3*2*2)1∗(3∗2∗2),另外还要累加从空集转移而来的 {3}。
至此,问题的解决办法逐渐清晰。
考虑有 a, b, c, d, e 五个数,按顺序从小到大排列,且从小到大枚举。
当枚举到 d 时,复制增加的新子集包括:
另外还有以 d 本身为最小值的子集 1 个:累加力量值 1∗(d2∗d)1*(d^2*d)1∗(d2∗d),将 d 左侧元素对结果的贡献即为 s,则有 pow(d)=d2∗(s+d)pow(d) = d^2*(s + d)pow(d)=d2∗(s+d)。
继续枚举到 e 是,复制增加的新子集包括:
另外还有以 e 本身为最小值的子集 1 个:累加力量值 1∗(e2∗e)1*(e^2*e)1∗(e2∗e),将 e 左侧元素对结果的贡献即为 s`,则有 pow(e)=e2∗(s‘+e)pow(e) = e^2*(s` + e)pow(e)=e2∗(s‘+e)。
观察 s 和 s` 的关系:
s=4∗a+2∗b+1∗cs = 4*a + 2*b + 1*cs=4∗a+2∗b+1∗c
s=8∗a+4∗b+2∗c+d=s∗2+ds = 8*a + 4*b + 2*c + d = s*2 + ds=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() } }
复杂度分析: