算法训练营——day3长度最小子数组

1 长度最小子数组-力扣209(中等)

1.1 题目: 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0 。

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3]是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

进阶:

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

1.2 思路解法

暴力解法(2024年更新数据后力扣超时)

思路:两个for循环遍历求解

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum=0;int ret = Integer.MAX_VALUE;int subLen=0;for(int i=0;i<nums.length;i++){sum=0;for(int j=i;j<nums.length;j++){sum+=nums[j];if(sum>=target){subLen=j-i+1;ret=ret<subLen?ret:subLen;break;}}}return ret==Integer.MAX_VALUE?0:ret;}
}

滑动窗口

//JAVA版本
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= target) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}
//CPP
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX;int sum = 0; // 滑动窗口数值之和int i = 0; // 滑动窗口起始位置int subLength = 0; // 滑动窗口的长度for (int j = 0; j < nums.size(); j++) {sum += nums[j];// 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件while (sum >= s) {subLength = (j - i + 1); // 取子序列的长度result = result < subLength ? result : subLength;sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)}}// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

1.3 进阶O(n)

//双向双指针
class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] ret = new int[n];for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {if (nums[i] * nums[i] > nums[j] * nums[j]) {ret[pos] = nums[i] * nums[i];++i;} else {ret[pos] = nums[j] * nums[j];--j;}--pos;}return ret;}
}

2 水果成篮-力扣904(中等)

2.1 题目:904. 水果成篮

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

示例 1:

输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。

示例 2:

输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。

示例 3:

输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。

示例 4:

输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。

提示:

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

2.2 思路及解法

class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;if (n < 2)return n;// 把小于2的单独拎出,后续只考虑ret>2int right = 0, ret = 2, left = 0;// 左右指针,结果最小值为2int[] flags = new int[n];int count = 0;// 水果种类,上限为2while (right < n) {//右指针一直往右遍历flags[fruits[right]]++;//对应flags标记增加if (flags[fruits[right]] == 1)//种类增加count++;right++;//指针偏移while (count > 2) {//种类超过了2,左指针右移,缩短区间flags[fruits[left]]--;if (flags[fruits[left]] == 0) {//标记值为0时,count一直减少回2count--;}left++;}ret = ret > (right - left) ? ret : (right - left);//因为每次右指针多偏移一次,所以长度不用+1}return ret;}
}

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

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

相关文章

基于orangePi的智能家居系统

目录 一.接线图 1.orangePi接线 2.继电器接线 二.语音模块的配置 1.pin脚的配置 2.命令词自定义信息 三.测试 1.通过gpio指令测试烟雾检测器是否正确连接 2.编写脚本测试其他模组接线是否正常 四.人脸识别方案 1.首先开通人脸搜索识别服务 2. 点击产品控制台,向人…

2024年四川省安全员B证证考试题库及四川省安全员B证试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年四川省安全员B证证考试题库及四川省安全员B证试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;质检局&#xff09;特种设备作业人员上岗证考试大…

ARM----时钟

时钟频率可以是由晶振提供的&#xff0c;我们需要高频率&#xff0c;但是外部接高的晶振会不稳定&#xff0c;所有使用PLL&#xff08;锁相环&#xff09;来放大频率。接下来就让我们学习用外部晶振提供的频率来配置时钟频率。 一.时钟源的选择 在这里我们选择外部晶振作为时钟…

数据库面试题学习

B树和B树 B树 排好序的 节点内部有多个元素 B树 排好序的 节点内多个元素 叶子节点有指针&#xff08;双向指针&#xff09; 非叶子节点冗余了一份在叶子节点 mysql定义B树 InnoDB B树是B树的升级版~ InnoDB b树是怎么产生的 mysql 页 目录 16KB 自增id uuid 一页最多可以存储…

【精选】文件摆渡系统:跨网文件传输的安全与效率之选

文件摆渡系统可以解决哪些问题&#xff1f; 文件摆渡系统&#xff08;File Shuttle System&#xff09;主要是应用于不同网络、网段、区域之间的文件数据传输流转场景&#xff0c; 用于解决以下几类问题&#xff1a; 文件传输问题&#xff1a; 大文件传输&#xff1a;系统可…

Windows bat脚本学习九(srec_cat)

一、简介 srec_cat是一个在嵌入式开发中&#xff0c;使用非常频繁的软件&#xff0c;这里做个常用功能的介绍。 二、常用参数 文件类型 在使用srec_cat指令时&#xff0c;在输入文件和输出文件时&#xff0c;要指明文件的类型&#xff0c;如&#xff1a; input.hex -intel …

2024国赛数学建模C题完整论文:农作物的种植策略

农作物种植策略优化的数学建模研究&#xff08;完整论文&#xff0c;持续更新&#xff0c;大家持续关注&#xff0c;更新见文末名片 &#xff09; 摘要 在本文中&#xff0c;建立了基于整数规划、动态规划、马尔科夫决策过程、不确定性建模、多目标优化、相关性分析、蒙特卡洛…

网络层 VII(IP多播、移动IP)【★★★★★★】

一、IP 多播 1. 多播的概念 多播是让源主机一次发送的单个分组可以抵达用一个组地址标识的若干目的主机&#xff0c;即一对多的通信。在互联网上进行的多播&#xff0c;称为 IP 多播&#xff08;multicast , 以前曾译为组播&#xff09;。 与单播相比&#xff0c;在一对多的…

Linux_kernel移植uboot07

一、移植 根据硬件平台的差异&#xff0c;将代码进行少量的修改&#xff0c;修改过后的代码在目标平台上运行起来 移植还需要考虑硬件环境&#xff0c;驱动只需要考虑内核的环境 二、移植内容 1、移植Uboot uboot属于bootloader的一种&#xff0c;还有其他的bootloader&#x…

【超简单】1分钟解决ppt全文字体一键设置

省流 ppt的全部字体需要在“幻灯片母版”里面&#xff0c;“自定义字体”去设置好标题与正文的字体之后才算全部设置完毕 “视图”---“幻灯片母版” 找到“字体”---“自定义字体” 设置好中文和西文的字体&#xff0c;都可以按照自己的选择来&#xff0c;保存即可 吐槽 之…

通信工程学习:什么是FEC前向纠错

FEC&#xff1a;前向纠错 FEC&#xff08;Forward Error Correction&#xff0c;前向纠错&#xff09;是一种增加数据通信可信度的技术&#xff0c;广泛应用于计算机网络、无线通信、卫星通信等多种数据传输场景中。其基本原理和特点可以归纳如下&#xff1a; 一、FEC前向纠错…

固态硬盘装系统有必要分区吗?

前言 现在的新电脑有哪一台是不使用固态硬盘的呢&#xff1f;这个好像很少很少了…… 有个朋友买了一台新的笔记本电脑&#xff0c;开机之后&#xff0c;电脑只有一个分区&#xff08;系统C盘500GB&#xff09;。这时候她想要给笔记本分区…… 这个真的有必要分区吗&#xf…

golang关于slice map函数传参的小问题

问题 函数传参了一个slice&#xff0c;在函数内触发了对长度的修改&#xff08;添加或删除&#xff09;&#xff0c;但是未影响函数外的实参由此产生了另一个问题&#xff0c;我们用map在函数内修改会不会有影响不到实参的情况&#xff1f; 结论 map作为函数参数时是引用传递…

TCP 拥塞控制

概念详解 TCP拥塞控制是网络通信中的一个关键机制&#xff0c;它通过动态调整发送数据的速率来避免网络拥塞。以下是TCP拥塞控制的详细概念解释&#xff1a; 拥塞窗口&#xff08;CWND, Congestion Window&#xff09;: 定义&#xff1a;发送方在收到接收方的确认&#xff08;…

Java 面试题:通过JProfile排查OOM问题 内存溢出与内存泄漏问题 --xunznux

文章目录 如何通过JProfile排查OOM或内存泄漏问题1、启动工具观测程序执行状态2、使用默认设置采样3、查看memory&#xff0c;Run GC无效4、查看 Live Memory发现两个byte大数组存在5、通过快照查看堆中的内存使用情况6、找到Full GC无法清除的对象通过大对象列表定位内存泄漏问…

【SpringBoot】电脑商城-12-订单功能

创建订单 1 订单-创建数据表 1.使用use命令先选中store数据库。 USE store;2.在store数据库中创建t_order和t_order_item数据表。 CREATE TABLE t_order (oid INT AUTO_INCREMENT COMMENT 订单id,uid INT NOT NULL COMMENT 用户id,recv_name VARCHAR(20) NOT NULL COMMENT …

Mac 上 YYDS 的自动切换输入法工具:好用到原地炸裂式起飞

有一种幸福的状态就是 任何时刻你都可以全力以赴 被打断、被终止也没有遗憾 因为你对结果没有那么期待 而且已经用尽全力了 当你深刻认识到你所做的事情 是多么好的时候 自然会产生一种想要分享出去 的心情 如今社会大部分工作都被电脑化了&#xff0c;在很多方面我们的…

第140天:内网安全-横向移动局域网ARP欺骗DNS劫持钓鱼中间人单双向

目录 案例一&#xff1a;局域网&工作组-ARP原理-断网限制-单向 案例二&#xff1a;局域网&工作组-ARP欺骗-劫持数据-双向 案例三&#xff1a;局域网&工作组-DNS 劫持-钓鱼渗透-双向 案例一&#xff1a;局域网&工作组-ARP原理-断网限制-单向 原理&#xff1…

数据库MySQL基础

目录 一、数据库的介绍 1.数据库概述 &#xff08;1&#xff09;数据的存储方式 &#xff08;2&#xff09;数据库 2.常见数据库排行榜 二、数据库的安装与卸载 1.数据库的安装 2.数据库的卸载 三、数据库服务的启动与登录 1.Windows 服务方式启动 &#xff08;1&…