内容简介:给定一个整数数组 A ,考虑 A 的所有非空子序列。对于任意序列 S ,设 S 的宽度是 S 的最大元素和最小元素的差。返回 A 的所有子序列的宽度之和。
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后 码农 的学习与生活
以上所述就是小编给大家介绍的《LeetCode算法系列_0891_子序列宽度之和》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法题:两数之和
- LeetCode-1-两数之和
- Leetcode 1:两数之和
- LeetCode题解 - 1. 两数之和
- LeetCode 第 1 号问题:两数之和
- LeetCode 1:两数之和 Two Sum
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Ajax Design Patterns
Michael Mahemoff / O'Reilly Media / 2006-06-29 / USD 44.99
Ajax, or Asynchronous JavaScript and XML, exploded onto the scene in the spring of 2005 and remains the hottest story among web developers. With its rich combination of technologies, Ajax provides a s......一起来看看 《Ajax Design Patterns》 这本书的介绍吧!