乐趣区

关于前端:LeetCode-双周赛-10420230513流水的动态规划铁打的结构化思考

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

  • 往期回顾:LeetCode 单周赛第 344 场 · 手写递归函数的通用套路

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

复杂度剖析:

  • 工夫复杂度:$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(nmlgm + nm)$ 其中 n 和 m 别离为矩阵的行数和列数,排序工夫 $O(nmlgm)$,扫描时间 $O(nm)$;
  • 空间复杂度:$O(lgm)$ 排序递归栈空间。

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)$ 后缀或值数组长度空间。

题解二(动静布局)

应用背包问题模型时,定义 dpi 示意在前 i 个元素上操作 k 次能够取得的最大或值,则有:

  • 状态转移方程:$dp[i][j] = max{dp[i-1][j], dp[i – 1][j – x] | (nums[i] << x)}$
  • 终止条件:$dp[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(n·k^2)$ 其中 n 为 nums 数组的长度;
  • 空间复杂度:$O(k)$ DP 数组空间

类似题目:

  • 238. 除本身以外数组的乘积
  • 416. 宰割等和子集

T4. 英雄的力量(Hard)

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

题目形容

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

  • i0i1,… 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(n·2^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(nlgn)$ 其中 n 为 nums 数组的长度,瓶颈在排序上,计算力量值局部工夫复杂度为 O(n);
  • 空间复杂度:$O(lgn)$ 排序递归栈空间。

往期回顾

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