算法/编程练习:寻找和至少为K的最短子数组

2024-09-04 18:32

本文主要是介绍算法/编程练习:寻找和至少为K的最短子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

寻找和至少为K的最短子数组


1. 题目

题目来自LeetCode:
https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/

题目:

返回非空列表A的最短的非空连续子数组的长度,该子数组的和至少为K。
如果没有和至少为K的非空子数组,返回 -1 。
例如,
input: A = [1, 2],  K = 4
output:  -1input: A = [2, -1, 2],  K = 3
output:  3

2. 思路(来自官方题解):

题目转换:
记P存放A的累计求和列表(P[x+1] = P[x] + A[x])
找到在满足P[y]-P[x] >= K情况下使y-x最小的y-x解答思路:全局最优解:最终需要的结果特定最优解x:当y固定时,满足条件的最大x特定最优解x满足规律:当y固定的时候,若x2 > x1且P[x2] <= P[x1](相当于A[x1]和A[x2]之间有负数)则x1必然不是y对应的特定最优解,因为若x1可行,则x2也可行且比x1更优因此(在x递增的方向)寻找y的特定最优解时,若x1 < x2且P[x1] >= P[x2],则x1可直接删除当x为多个y的特定最优解时的规律:对于任何y2 > y1,若x同时是y1和y2对应的特定最优解,则y1-x一定优于y2-x因此在y递增的方向寻找全局最优解时,若x是y的特定最优解,则后续不用再考虑x(因为y递增)用一个双端列队deq存放可能是特定最优解的下标x,然后求解分两个步骤,对A的每个元素A[y]:1) 首先y固定,删除deq中所有x < y且P[x] > P[y]的x2) 对deq中的从小到大的每个下标x,若x为y的特定最优解,则将其删除

3. Python代码:

# -*- coding: utf-8 -*-import collectionsdef SumKShortestSublist(A, K):if not isinstance(A, list) or len(A) < 1:print('A须为非空列表!')return -1N = len(A)P = [0] # 存放累计和列表for a in A:P.append(P[-1] + a)best_ans = N+1 # best_ans记录全局最优解,N+1 is impossible    deq = collections.deque() # 双端列队deq存放可能是特定最优解的下标xfor y, P_y in enumerate(P):# 当y固定时,删除d中所有x < y且P[x] > P[y]的xwhile deq and P_y <= P[deq[-1]]:deq.pop()# 若x是y的特定最优解,则后续不用再考虑xwhile deq and P_y - P[deq[0]] >= K:best_ans = min(best_ans, y-deq.popleft())deq.append(y)return best_ans if best_ans < N+1 else -1if __name__ == '__main__':A = [1]K = 1print(SumKShortestSublist(A, K))A = [1, 2]K = 5print(SumKShortestSublist(A, K))    A = [2, 1, 2]K = 3print(SumKShortestSublist(A, K))A = [2, -1, 2]K = 3print(SumKShortestSublist(A, K))A = [84, -37, 32, 40, 95]K = 167print(SumKShortestSublist(A, K))

欢迎关注公众号:一本正经d胡说
Genlovy562

这篇关于算法/编程练习:寻找和至少为K的最短子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1136699

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Python 异步编程 asyncio简介及基本用法

《Python异步编程asyncio简介及基本用法》asyncio是Python的一个库,用于编写并发代码,使用协程、任务和Futures来处理I/O密集型和高延迟操作,本文给大家介绍Python... 目录1、asyncio是什么IO密集型任务特征2、怎么用1、基本用法2、关键字 async1、async

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ