牛客NC343 和大于等于K的最短子数组【困难 前缀和 Java/Go】

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/3e1fd3d19fb0479d94652d49c7e1ead1

思路

本答案利用前缀和解答,Java,Go答案通过,但是同样的代码用PHP的话有一个测试用例超时
应该还有更优秀的答案,后面找到更优答案再更新博客

Java代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型ArrayList* @param k int整型* @return int整型*/public int shortestSubarray (ArrayList<Integer> nums, int k) {//前缀和int n = nums.size();int[] sum = new int[n + 1];for (int i = 0; i < n; i++) {sum[i + 1] = sum[i] + nums.get(i);sum[i + 1]%=1000000007;  //关键if (nums.get(i) == k) return 1;}int ans = 0x7fffffff;for (int i = 0; i <= n ; i++) {if (sum[i] >= k) {ans = Math.min(ans, i);for (int j = i ; j >= 0 ; j--) {int diff = sum[i] - sum[j];if (diff >= k) {ans = Math.min(ans, i - j);break;}}}}if (ans == 0x7fffffff)return -1;return ans;}
}

Go代码

package main/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型一维数组* @param k int整型* @return int整型*/
func shortestSubarray(nums []int, k int) int {//前缀和n := len(nums)ans := 0x7fffffffsum := make([]int, n+1)for i := 0; i < n; i++ {sum[i+1] = sum[i] + nums[i]if nums[i] == k {return 1}}for i := 0; i <= n; i++ {if sum[i] >= k { //剪枝if sum[i] >= k {if i < ans {ans = i}}for j := i; j >= 0; j-- {diff := sum[i] - sum[j]if diff >= k {if i-j < ans {ans = i - j}break}}}}if ans == 0x7fffffff {return -1}return ans
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328536.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

fastadmin对登录token的处理

fastadmin对token的操作 最近开发遇到一个场景&#xff0c;需要绕过验证获取登录&#xff0c;所以恶补了一下这个知识点&#xff0c;这个主要就是控制fastadmin的token的问题 代码分步实现 class Xcxuser extends Api {//关于鉴权protected $noNeedLogin [login,getopenid,…

AWS简介

AWS AWS&#xff0c;全称为Amazon Web Services&#xff0c;是亚马逊公司旗下的云计算服务平台&#xff0c;自2006年起向全球用户提供广泛而深入的云计算服务。AWS是全球最全面、应用最广泛的云平台之一&#xff0c;它从全球的数据中心提供超过200项功能齐全的服务&#xff0c…

ospf基础

ospf 概述&#xff1a; 什么是ospf 开放式最短路径优先协议&#xff0c;一种最受欢迎的动态路由协议版本&#xff1a;ospfv2&#xff08;ipv4&#xff09;和ospfv3&#xff08;ipv6&#xff09;ospf位于OSI参考模型的第三层&#xff0c;数据封装在ip报头的后面协议号&#xf…

(2)双指针练习:复写零

复写零 题目链接&#xff1a;1089. 复写零 - 力扣&#xff08;LeetCode&#xff09; 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入…

详解绝对路径和相对路径的区别

绝对路径和相对路径是用于描述文件或目录在文件系统中位置的两种不同方式。 绝对路径&#xff08;Absolute Path&#xff09;是从文件系统的根目录开始的完整路径&#xff0c;可以唯一地确定一个文件或目录的位置。在不同的操作系统中&#xff0c;根目录的表示方式可能略有不同…

那些年我与c++的叫板(一)--string类自实现

引子&#xff1a;我们学习了c中的string类&#xff0c;那我们能不能像以前数据结构一样自己实现string类呢&#xff1f;以下是cplusplus下的string类&#xff0c;我们参考参考&#xff01; 废话不多说&#xff0c;直接代码实现&#xff1a;&#xff08;注意函数之间的复用&…

【Qt】Qt开源项目

1、Flameshot 截图工具 1.1 简介 Flameshot是一款功能强大但易于使用的屏幕截图软件,中文名称火焰截图。 Flameshot 简单易用并有一个CLI版本,所以可以从命令行来进行截图。 Flameshot 是一个Linux发行版中完全免费且开源的截图工具 1.2 源码 github:https://github.com…

波搜索算法(WSA)-2024年SCI新算法-公式原理详解与性能测评 Matlab代码免费获取

​ 声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原理简介 一、初始化阶段 二、全…

计算机Java项目|Springboot高校心理教育辅导设计与实现

作者主页&#xff1a;编程指南针 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、腾讯课堂常驻讲师 主要内容&#xff1a;Java项目、Python项目、前端项目、人工智能与大数据、简…

ThreadLocal,一次到位

一、定义 ThreadLocal是线程私有变量&#xff0c;用于保存每个线程的私有数据。 那么什么情况下需要进行线程隔离 二、源码分析 public class ThreadLocalTest01 {ThreadLocal<Integer> t new ThreadLocal<>();public void test() {t.set(1);Integer integer…

前馈神经网络FNN、多层感知机MLP和反向传播推导

目录 一、前馈神经网络FNN 激活函数的使用 二、多层感知机MLP MLP的典型结构 多层感知机MLP的特点 和前馈神经网络FNN的区别 三、传播推导 1、前向传播(Forward propagation) &#xff08;1&#xff09;输入层到隐藏层 &#xff08;2&#xff09;隐藏层到输出层 2、…

如何去除字符串两侧的空白字符?

TRIM函数会去掉字符串左侧和右侧的空格&#xff0c;语法是&#xff1a;TRIM(字符串) excel中&#xff0c;TRIM函数能去掉字符串左侧和右侧的空格&#xff0c;它的ASCII码是32。 以下设定一个字符串组合&#xff0c;它的第一个字符中空格&#xff0c;最后一个字符是换行符 &q…

头歌实践教学平台:CG1-v1.0-点和直线的绘制

第3关&#xff1a;OpenGL直线绘制 一.任务描述 根据下面要求&#xff0c;在右侧修改代码&#xff0c;绘制出预期输出的图片。平台会对你编写的代码进行测试。 1.本关任务 理解基本图形元素光栅化的基本原理&#xff1b; 了解和使用OpenGL的生成直线的命令&#xff0c;来验证…

MySQL深入理解MVCC机制(详解)

深入理解MVCC 1、MVCC定义 MVCC:Multi-Version Concurrency Control&#xff0c;多版本并发控制机制。 在mysql中&#xff0c;为了满足事务的四大特性之一的隔离性&#xff0c;就是当前事务中的查询的数据不受其他事务的增删改操作的影响&#xff0c;因此mysql主要是通过这个…

VUE之旅—day2

文章目录 Vue生命周期和生命周期的四个阶段created应用—新闻列表渲染mounted应用—进入页面搜索框就获得焦点账单统计&#xff08;Echarts可视化图表渲染&#xff09; Vue生命周期和生命周期的四个阶段 思考&#xff1a; 什么时候可以发送初始化渲染请求&#xff1f;&#xff…

08 - hive的集合函数、高级聚合函数、炸裂函数以及窗口函数

目录 1、集合函数 1.1、size&#xff1a;集合中元素的个数 1.2、map&#xff1a;创建map集合 1.3、map_keys&#xff1a; 返回map中的key 1.4、map_values: 返回map中的value 1.5、array 声明array集合 1.6、array_contains: 判断array中是否包含某个元素 1.7、sort_a…

Java中的数组、Set、List、Map类型的互相转换总结

序言 数组、Set、List、Map是Java语言非常常用的几种数据类型&#xff0c;他们之间存在着千丝万缕的联系。关于底层的数据结构我这里就不再多说啦&#xff0c;直接从应用出发&#xff0c;总结他们之间的转换方法&#xff0c;并给出推荐方法。 大家可以点赞收藏等到需要的时候…

四、基于Stage模型的应用架构设计

前面我们了解了如何构建鸿蒙应用以及开发了第一个页面&#xff0c;这只是简单的demo&#xff1b;那么如何去设计&#xff0c;从0到1搭建一个真正的应用呢 一、基本概念 1、Stage模型基本概念 Stage模型概念图 AbilityStage&#xff1a;是一个Module级别的组件容器&#xff0…

C语言/数据结构——栈的实现

一.前言 今天我们讲解新的领域——栈。 二.正文 1.栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其允许在固定的一段进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#…

LLama3大模型本地部署 仅需6步完成对话模型本地安装部署。附送可视化ui安装、自定义模型目录,修改模型保存地址,第三方微调模型、中文模型下载地址

本篇分为三部分 一&#xff1a;6步完成llama3大模型本地部署 二&#xff1a;8步完成llama3可视化对话界面安装 三&#xff1a;重设模型文件路径 四&#xff1a;微调模型、中文模型下载资源分享 一、LLama3 大模型本地部署安装 首先去mata官网下载ollama客户端 Ollama 选择合适…