LeetCode算法系列_0891_子序列宽度之和
题目描述
给定一个整数数组 A ，考虑 A 的所有非空子序列。
对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。
返回 A 的所有子序列的宽度之和。
由于答案可能非常大，请返回答案模 10^9+7。
示例1:
输入：[2,1,3]
输出：6
解释：
子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。
相应的宽度是 0，0，0，1，1，2，2 。
这些宽度之和是 6 。提示:
- 1 <= A.length <= 20000
- 1 <= A[i] <= 20000
算法
const mod = 1e9 + 7
func sumSubseqWidths(a []int) int {
//[3,2,4,1] 和 排序后的 [1,2,3,4] 宽度之和相同
sort.Ints(a)
n := len(a)
res := 0
/**
作为最大值出现的次数
a[0] a[1] a[2]
1 2 4
[2,1,3],3作为最大值进行排列组合
[2,3],[1,3][,2,1,3],[3]
*/
times := 1
for i := 0; i < n; i++ {
//a[i]作为最大值出现的次数==a[n-1-i]作为最小值出现的次数
res += (a[i] - a[n-1-i]) * times
//res可能非常大,所以取模
res %= mod
//times可能非常大,取模
times = (times << 1) % mod
}
return res
}个人思路
- 子序列即部分数组元素进行排列组合形成若干数组,数组中最大值-最小值即该子数组宽度
- [3,2,4,1]和[1,2,3,4]的子序列不一样,但是子序列的宽度之和,是相同的
- 对数组排序,某子序列宽度即数组头尾元素之差
- 举例:数组[1,2,3,4],每个元素都可能作为某子序列的最大值,最小值,n是数组长度
- a[i]作为最大值,有i个元素比它小,可以形成2^i个子序列
- a[i]作为最小值,有n-1-i个元素比它大,可以形成2^(n-1-i)个子序列
- 规律:a[0]作为最大值的子序列个数==a[n-1]作为最小值的子序列个数,同理a[1]与a[n-1-1]....,即a[i]最大值与a[n-1-i]最小值次数相等
- 子序列宽度之和=(最大值a[i]2^i+...)-(最小值a[n-1-i]2^i...)
- 子序列宽度之和=(a[i]-a[n-1-i]*2^i)+......
- 2^i的值,依次是1,2,4,8....,会很大,所以需要 对10^9+7取模
总结
- 解决问题,最终总是找出问题背后的数学规律
GitHub
- 项目源码在这里
- 笔者会一直维护该项目,对leetcode中的算法题进行解决,并写下自己的思路和见解,致力于人人都能看懂的算法
个人公众号
- 喜欢的朋友可以关注,谢谢支持
- 记录90后码农的学习与生活
