LeetCode 双周赛 104（2023/05/13）流水的动态规划，铁打的结构化思考-六虎

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

往期回忆：LeetCode 单周赛第 344 场手写递归函数的通用套路

T1. 白叟的数目（Easy）

标签：模仿、计数

T2. 矩阵中的和（Medium）

标签：模仿、排序

T3. 最大或值（Medium）

标签：动态规划、前后缀分化、贪心

LeetCode 双周赛 104（2023/05/13）流水的动态规划，铁打的结构化思考

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" }
    }
}

复杂度剖析：

时刻复杂度： $O (n)$ 其间 n 为 details 数组的长度；
空间复杂度： $O (1)$ 仅运用常量级别空间。

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
    }
}

复杂度剖析：

时刻复杂度： $O (nm l g m + nm)$ 其间 n 和 m 分别为矩阵的行数和列数，排序时刻 $O (nm l g m)$ ，扫描时刻 $O (nm)$ ；
空间复杂度： $O (l g m)$ 排序递归栈空间。

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 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 15

问题结构化

1、归纳问标题标

核算能够获得的最大或值。

2、剖析问题要件

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

3、调查问题数据

数据量：问题数据量上界为 $10^5$ ，要求算法时刻复杂度低于 $O(n^2)$ ；
数据巨细：元素值的上界为 $10^9$ ，操作次数 k 的上界为 15（这个性质有什么用呢？）；
输出成果：以长整型 Long 的方法回来成果。

4、调查测试用例

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

5、提高笼统程度

权重：二进制位越高的位对数字巨细的影响越大，因而咱们应该尽量让高位的二进制方位为 1；
是否为决策问题？因为每次操作有多种方位挑选，因而这是一个决策问题。

6、详细化处理手法

1、贪心：结合「数据巨细」剖析，因为操作次数 k 的上界为 15 次，无论如何位移都不会溢出 Long。因而，咱们能够将 k 次位移操作作用在同一个数字上，尽或许让高位的方方位为 1；
2、动态规划（背包）：假定已经核算出数组前 i – 1 个元素能够组成的最大或值，那么考虑拼接 nums[i]，能够挑选不操作 nums[i]，也能够挑选在 nums[i] 上操作 x 次，那么问题就变成「前 i – 1 个元素中操作 k – x 次的最大或值」与「num[i] 操作 x 次的或值」兼并的或值。「前 i – 1 个元素中操作 k – x 次的最大或值」这是一个与原问题类似但规划更小的子问题，能够用动态规划处理，更详细地能够用背包问题模型处理。

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

枚举一切数字并向左位移 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
    }
}

复杂度剖析：

时刻复杂度： $O (n)$ 其间 n 为 nums 数组的长度；
空间复杂度： $O (n)$ 后缀或值数组长度空间。

题解二（动态规划）

运用背包问题模型时，界说 dp[i][j] 表明在前 i 个元素上操作 k 次能够获得的最大或值，则有：

状况搬运方程： $dp[i][j] = max{dp[i-1][j], dp[i – 1][j – x] | (nums[i] << x)}$
终止条件： $d p [n] [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]
    }
}

时刻复杂度： $O(nk^2)$ 其间 n 为 nums 数组的长度；
空间复杂度： $O (k)$ DP 数组空间

类似标题：

238. 除自身以外数组的乘积
416. 切割等和子集

T4. 英豪的力气（Hard）

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

问题结构化

1、归纳问标题标

核算一切组合方案的「力气」总和。

2、剖析问题要件

枚举一切子集，核算子集的力气值核算公式为 $最大值^2*最小值」$ 。

3、调查问题数据

数据量：问题数据量上界为 $10^5$ ，要求算法时刻复杂度低于 $O(n^2)$ ；
数据巨细：元素值的上界为 $10^9$ ，乘法运算会溢出整型上界，需求考虑大数问题。

4、调查问题测试用例：

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

剖析小规划问题：[] 空集的力气值是 0，只包含 1 个元素子集的力气值核算也没有问题；

子集	最大值	最小值	力气值
{}	0	0	0
{1}	1	1	$1^2*1$
{2}	2	2	$2^2*2$
{3}	3	3	$3^2*3$

剖析规划为 2 的子集问题：

子集	最大值	最小值	力气值
{1, 2}	2	1	$2^2*1$
{1, 3}	3	1	$3^2*1$
{2, 3}	3	2	$3^2*2$

剖析规划为 3 的子集问题：

子集	最大值	最小值	力气值
{1, 2, 3}	3	1	$3^2*1$

5、如何处理问题

手法 1（暴力枚举）：假如枚举一切子集，再求每个子集的力气值，那么时刻复杂度会到达非常高的 $O(n2^n)$ ，其间有 $2^n$ 种子集（一共有 n 个数字，每个数字有选和不选两种状况），每个子集花费 $O (n)$ 线性扫描最大值和最小值。

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

6、持续调查问题测试用例

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

考虑空集的力气值问题：

子集	最大值	最小值
{}	0	0

考虑到「1」停止的力气值问题：

子集	最大值	最小值
{}	0	0
{1}	1	1

考虑到「2」停止的力气值问题：

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

考虑到「3」停止的力气值问题：

子集	最大值	最小值
{}	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

这又说明了什么呢？

要害点 1 – 递推地结构子集：

咱们发现子集问题能够用递推地方法结构，当咱们添加考虑一个新元素时，其实是将已有子集仿制一份后，再仿制的子集里添加元素。例如咱们在考虑「2」时，是将 {} 和 {1} 仿制一份后添加再添加元素「2」。

要害点 2 – 最大值的奉献：

因为咱们是从小到大添加元素，所以仿制后新子集中的最大值必定等于当前元素，那么问题的要害就在「如何核算这些新子集的最小值」。

要害点 3 – 最小值的奉献：

因为咱们选用子集仿制的方法了解子集结构问题，容易发现数字越早呈现，最小值呈现次数越大（哆啦 A 梦的翻倍药水）。

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

至此，问题的处理办法逐渐明晰。

7、处理问题的新手法

手法 2（动态规划）：

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

当枚举到 d 时，仿制添加的新子集包含：

以 a 为最小值的子集有 4 个：累加力气值 $4*(d^2*a)$
以 b 为最小值的子集有 2 个：累加力气值 $2*(d^2*b)$
以 c 为最小值的子集有 1 个：累加力气值 $1*(d^2*c)$

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

持续枚举到 e 是，仿制添加的新子集包含：

以 a 为最小值的子集有 8 个：累加力气值 $8*(e^2*a)$
以 b 为最小值的子集有 4 个：累加力气值 $4*(e^2*b)$
以 c 为最小值的子集有 2 个：累加力气值 $2*(e^2*c)$
以 d 为最小值的子集有 1个：累加力气值 $1*(e^2*d)$

另外还有以 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()
    }
}

复杂度剖析：

时刻复杂度： $O (n l g n)$ 其间 n 为 nums 数组的长度，瓶颈在排序上，核算力气值部分时刻复杂度为 O(n)；
空间复杂度： $O (l g n)$ 排序递归栈空间。

往期回忆

LeetCode 单周赛第 344 场手写递归函数的通用套路
LeetCode 单周赛第 343 场结合「下一个排列」的贪心结构问题
LeetCode 双周赛第 103 场区间求和的树状数组经典应用
LeetCode 双周赛第 102 场这次又是最短路。

LeetCode 双周赛 104（2023/05/13）流水的动态规划，铁打的结构化思考

T1. 白叟的数目（Easy）

T2. 矩阵中的和（Medium）

T3. 最大或值（Medium）

标题描述

问题结构化

1、归纳问标题标

2、剖析问题要件

3、调查问题数据

4、调查测试用例

5、提高笼统程度

6、详细化处理手法

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

题解二（动态规划）

T4. 英豪的力气（Hard）

标题描述

问题结构化

1、归纳问标题标

2、剖析问题要件

3、调查问题数据

4、调查问题测试用例：

5、如何处理问题

6、持续调查问题测试用例

7、处理问题的新手法

题解（动态规划）

往期回忆

相关文章

Redis基本数据结构的底层实现(总结版)

iOS 小技能：Method Swizzling （交换方法的IMP）

【K哥爬虫普法】12亿公民信息泄露，仅判3年，个人信息是否为爬虫“禁区”？

推荐系统：协同过滤

作者信息