当前位置: 首页 > news >正文

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

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后码农的学习与生活

image

相关文章:

  • python数据库mysql第二天
  • c语言:输入两个正整数 求最大公约数和最小公倍数
  • Maven依赖构建版本冲突(实战cxf asm和cglib冲突)
  • 【SublimeText】【DeleteBlankLines】使用说明
  • FTP服务器的三种用户创建(部分)
  • CentOS下的apache配置支持php
  • 洛谷P2668 斗地主
  • 使用 Traefik 的一些补充细节
  • Java 内存分配及垃圾回收机制初探
  • 密码学原理学习笔记
  • 杂谈
  • 07 numpy 一元函数
  • IBM AIX系统日志配置远程Syslog采集
  • 【跃迁之路】【585天】程序员高效学习方法论探索系列(实验阶段342-2018.09.13)...
  • css的transform属性让子元素在父元素里面垂直水平居中
  • CSS 专业技巧
  • Druid 在有赞的实践
  • exif信息对照
  • Javascripit类型转换比较那点事儿,双等号(==)
  • linux学习笔记
  • Spring思维导图,让Spring不再难懂(mvc篇)
  • vue-cli3搭建项目
  • Vue源码解析(二)Vue的双向绑定讲解及实现
  • 对话:中国为什么有前途/ 写给中国的经济学
  • 京东美团研发面经
  • 老板让我十分钟上手nx-admin
  • 每天10道Java面试题,跟我走,offer有!
  • 前端学习笔记之观察者模式
  • 树莓派 - 使用须知
  • 限制Java线程池运行线程以及等待线程数量的策略
  • 小程序测试方案初探
  • 一个普通的 5 年iOS开发者的自我总结,以及5年开发经历和感想!
  • puppet连载22:define用法
  • #我与Java虚拟机的故事#连载19:等我技术变强了,我会去看你的 ​
  • (C#)if (this == null)?你在逗我,this 怎么可能为 null!用 IL 编译和反编译看穿一切
  • (Java实习生)每日10道面试题打卡——JavaWeb篇
  • (zz)子曾经曰过:先有司,赦小过,举贤才
  • (附源码)php新闻发布平台 毕业设计 141646
  • (论文阅读23/100)Hierarchical Convolutional Features for Visual Tracking
  • (使用vite搭建vue3项目(vite + vue3 + vue router + pinia + element plus))
  • (一)Dubbo快速入门、介绍、使用
  • (一)Spring Cloud 直击微服务作用、架构应用、hystrix降级
  • .MyFile@waifu.club.wis.mkp勒索病毒数据怎么处理|数据解密恢复
  • .NET CLR Hosting 简介
  • .net 获取url的方法
  • .NET 使用 XPath 来读写 XML 文件
  • .NET成年了,然后呢?
  • @RequestBody详解:用于获取请求体中的Json格式参数
  • [ Algorithm ] N次方算法 N Square 动态规划解决
  • [.NET 即时通信SignalR] 认识SignalR (一)
  • [3300万人的聊天室] 作为产品的上游公司该如何?
  • [acwing周赛复盘] 第 69 场周赛20220917
  • [ai笔记9] openAI Sora技术文档引用文献汇总
  • [Android]使用Android打包Unity工程
  • [C#]C#学习笔记-CIL和动态程序集