LeetCode算法系列_0891_子序列宽度之和

栏目: 编程工具 · 发布时间: 6年前

内容简介:给定一个整数数组 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
}

个人思路

  1. 子序列即部分数组元素进行排列组合形成若干数组,数组中最大值-最小值即该子数组宽度
  2. [3,2,4,1]和[1,2,3,4]的子序列不一样,但是子序列的宽度之和,是相同的
  3. 对数组排序,某子序列宽度即数组头尾元素之差
  4. 举例:数组[1,2,3,4],每个元素都可能作为某子序列的最大值,最小值,n是数组长度
  5. a[i]作为最大值,有i个元素比它小,可以形成2^i个子序列
  6. a[i]作为最小值,有n-1-i个元素比它大,可以形成2^(n-1-i)个子序列
  7. 规律:a[0]作为最大值的子序列个数==a[n-1]作为最小值的子序列个数,同理a[1]与a[n-1-1]....,即a[i]最大值与a[n-1-i]最小值次数相等
  8. 子序列宽度之和=(最大值a[i] 2^i+...)-(最小值a[n-1-i] 2^i...)
  9. 子序列宽度之和=(a[i]-a[n-1-i]*2^i)+......
  10. 2^i的值,依次是1,2,4,8....,会很大,所以需要 对10^9+7取模

总结

  • 解决问题,最终总是找出问题背后的数学规律

GitHub

  • 项目源码在这里
  • 笔者会一直维护该项目,对leetcode中的算法题进行解决,并写下自己的思路和见解,致力于人人都能看懂的算法

个人公众号

  • 喜欢的朋友可以关注,谢谢支持
  • 记录90后 码农 的学习与生活

LeetCode算法系列_0891_子序列宽度之和


以上所述就是小编给大家介绍的《LeetCode算法系列_0891_子序列宽度之和》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

标签

标签

Gene Smith / 张军、陈军亮 / 机械工业出版社 / 2012-6 / 59.00元

本书对标记系统这一概念的内涵和外延进行了系统化的、深入浅出的阐述。从什么是标记系统、标记系统有什么价值,到标记系统的架构和与其他分类系统的对比,再到标签的呈现方式和标记系统的实现细节,作者都用通俗易懂的语言进行了阐述,并附有详细的示例和具体的案例研究。本书的每一章都涵盖了标记系统的一个方面,主要内容包括:标记系统的模型、价值、架构,标签的分类、可视化、管理方法,最后介绍标记系统设计方法。本书带领读......一起来看看 《标签》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具