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

【算法-数组2】有序数组的平方 和 长度最小的子数组

今天,带来数组相关算法的讲解。文中不足错漏之处望请斧正!

理论基础点这里


有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶:

请你设计时间复杂度为 O(n) 的算法解决本问题

1. 思路

只有正数时,平方的大小就是从头到尾即由小到大。

在这里插入图片描述

那顺序遍历升序数组,作平方,就能得到升序结果。

但有负数时该怎么办?最小的平方应该是从两端趋向中间的最接近0的那个值。
在这里插入图片描述

从这个值往两边走,谁的平方大,谁就先插入结果集。题目要求升序,那我们就从结果集的尾部到结果集的头部放入结果。

要“往两边走”我们用双指针从两边遍历就好啦,谁大谁先插入结果数组。

2. 参考代码

class Solution {
public:// 找0, 双指针从两头向中间找, 平方和大的插入结果集的后面vector<int> sortedSquares(vector<int>& nums) {vector<int> result(nums.size());int left = 0;int right = nums.size() - 1;int insertIndex = result.size() - 1;while (left <= right) { // left==righrt时, nums[left]的平方和也要插入结果集long long squre1 = pow(nums[left], 2);long long squre2 = pow(nums[right], 2);if (squre1 > squre2) {result[insertIndex--] = squre1;++left;} else {result[insertIndex--] = squre2;--right;}}return result;}
};

长度最小的子数组

1. 思路

理解题意

分析如何满足需求

1.1 暴力遍历

两层for,一个指针确定当前想遍历的区间的起始位置,另一个指针遍历来确定终止位置,把所有可能的区间都遍历一遍,一旦区间和大于target,就对比并取最小的长度。

参考代码如下:

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int minLen = INT_MAX;int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s,更新resultsubLength = j - i + 1; // 取子序列的长度result = result < subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列,所以一旦符合条件就break,不要再累加元素了}}}return result == INT_MAX ? 0 : result;}
};
1.2 滑动窗口

暴力的方法比较死板:直接把所有可能得区间都遍历一遍。每一次都是静态确认好一个区间 [i, j] ,再累加求结果,有没有办法更灵活地确认这个连续子数组地区间呢?有的。

我们可以维护一个连续子数组的区间(右边的指针固定走,左边的指针能跟就跟,保证长度最小),——滑动窗口。

什么是滑动窗口?其实是双指针的一种应用,两个指针动态移动,维护一个区间,像滑动的窗口一样。

滑动窗口在本题中怎么用呢?

在这里插入图片描述

为什么是end固定往后走,begin根据策略走?

首先,end必须把整个数组遍历一遍;其次,begin作为起始位置,不一定需要固定走(如果区间和不大于等于target,走了有什么意义呢)。

end遍历给定数组nums,当区间和大于target的时候,就得到了当前最小的连续子序列但不是最终的。所以在end往后移动的时候,begin也要根据一定策略追赶end,保证得到最终的最小连续子序列。

begin到底是怎样移动的呢?
  • 如果当前区间是连续子数组,begin就要移动
  • 如果当前区间不是连续子数组,那么begin就不能移动

这样子移动,每次begin移动完,[begin, end]的和都会小于target(不再是连续子数组),但这不影响,因为在它最后还是连续子数组的时候,我们已经用minLen记录了它的长度。这样走下去,就能获取到最短的长度。

2. 参考代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int begin = 0; // [begin, end] 就是期望的最短子数组区间int end = 0;int curLen = 0;int minLen = INT_MAX;long long sum = 0;while (end < nums.size()) {sum += nums[end];while (sum >= target) { // 已经是子数组, 开始缩减长度curLen = end - begin + 1;minLen = min(curLen, minLen);sum -= nums[begin++]; // 缩减长度}++end;}return minLen == INT_MAX ? 0 : minLen;}
};

今天的分享就到这里了,感谢您能看到这里。

这里是培根的blog,期待与你共同进步!

相关文章:

【算法-数组2】有序数组的平方 和 长度最小的子数组

今天&#xff0c;带来数组相关算法的讲解。文中不足错漏之处望请斧正&#xff01; 理论基础点这里 有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输…...

H5游戏源码分享-接苹果游戏拼手速

H5游戏源码分享-接苹果游戏拼手速 看看在20秒内能接多少个苹果 <html> <head><title>我是你的小苹果</title><meta charset"utf-8"/><meta name"viewport" content"initial-scale1, user-scalableno, minimum-scale…...

详解类生到死的来龙去脉

类生命周期和加载过程 一个类在 JVM 里的生命周期有 7 个阶段&#xff0c;分别是加载&#xff08;Loading&#xff09;、校验&#xff08;Verification&#xff09;、准备&#xff08;Preparation&#xff09;、解析&#xff08;Resolution&#xff09;、初始化&#xff08;Ini…...

寻找倒数第K个节点

这篇文章也是凑数的 ... 寻找倒数第K个节点 描述 : 找出单向链表中倒数第 k 个节点。返回该节点的值。 题目 : LeetCode 返回倒数第K个节点 : 面试题 02.02. 返回倒数第 k 个节点 说明 : 给定的 k 保证是有效的。 分析 : 我们给出个例子 : 首先&#xff0c;我们创建两个…...

[ROS系列]ubuntu 20.04 从零配置orbslam3(无坑版)

目录 背景: 结果展示: 一、配置虚拟机 二、 同步网络时间 三、ping网络 四、 安装ros 五、下载源码 六、下载orb_slam3 error1:Pangolin error2: ./HelloPangolin: error while loading shared libraries: libpango_windowing.so: cannot open shared object file…...

网络协议--TCP的保活定时器

23.1 引言 许多TCP/IP的初学者会很惊奇地发现可以没有任何数据流通过一个空闲的TCP连接。也就是说&#xff0c;如果TCP连接的双方都没有向对方发送数据&#xff0c;则在两个TCP模块之间不交换任何信息。例如&#xff0c;没有可以在其他网络协议中发现的轮询。这意味着我们可以…...

leetcode 1353. 最多可以参加的会议数目

给你一个数组 events&#xff0c;其中 events[i] [startDayi, endDayi] &#xff0c;表示会议 i 开始于 startDayi &#xff0c;结束于 endDayi 。 你可以在满足 startDayi < d < endDayi 中的任意一天 d 参加会议 i 。注意&#xff0c;一天只能参加一个会议。 请你返回…...

hadoop权威指南第四版

第一部分 HaDOOP基础知识 1.1 面临的问题 存储越来越大&#xff0c;读写跟不上。 并行读多个磁盘。 问题1 磁盘损坏 – 备份数据HDFS 问题2 读取多个磁盘用于分析&#xff0c;数据容易出错 --MR 编程模型 1.2 衍生品 1 在线访问的组件是hbase 。一种使用hdfs底层存储的模型。…...

LeetCode75——Day20

文章目录 一、题目二、题解 一、题目 2215. Find the Difference of Two Arrays Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where: answer[0] is a list of all distinct integers in nums1 which are not present in nums2. an…...

搭建微信小程序环境及项目结构介绍

一、注册 访问微信公众平台&#xff0c;将鼠标的光标置于账号分类中的小程序上&#xff0c; 点击‘查看详情’ 点击“前往注册” 下方也可以点击注册&#xff1a; 小程序注册页面&#xff1a; 步骤a:进入小程序注册页&#xff0c;根据指引填写信息和提交相应的资料&#x…...

Python通过pyecharts对爬虫房地产数据进行数据可视化分析(一)

一、背景 对Python通过代理使用多线程爬取安居客二手房数据&#xff08;二&#xff09;中爬取的房地产数据进行数据分析与可视化展示 我们爬取到的房产数据&#xff0c;主要是武汉二手房的房源信息&#xff0c;主要包括了待售房源的户型、面积、朝向、楼层、建筑年份、小区名称…...

关于测试组件junit切换testng的示例以及切换方式分享

文章目录 概要首先看看junit和testng的区别实践篇摸拟业务逻辑代码简单对象数据层摸拟类业务逻辑层摸拟类后台任务摸拟类 基于springmockjunit基于springmocktestng 示例的差异点junit与testng的主要变动不大,有以下几个点需要注意注解部分在before,after中testng多出按配置执行…...

nginx 内存管理(二)

共享内存 共享内存结构与接口定义nginx共享内存在操作系统上的兼容性设计互斥锁锁的结构体锁的一系列操作&#xff08;core/ngx_shmtx.c&#xff09;创建锁 原子操作nginx的上锁操作尝试加锁获取锁释放锁强迫解锁唤醒等待进程 slab共享内存块管理nginx的slab大小规格内存池结构…...

【DevChat】智能编程助手 - 使用评测

写在前面&#xff1a;博主是一只经过实战开发历练后投身培训事业的“小山猪”&#xff0c;昵称取自动画片《狮子王》中的“彭彭”&#xff0c;总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域&#xff0c;如今终有小成…...

Geek challenge 2023 EzHttp

打开链接需要使用post请求提交username和password 查看源码得到提示&#xff0c;爬虫想到robots协议 访问robots.txt 访问得到的路径&#xff1a;/o2takuXXs_username_and_password.txt 拿到用户名和密码&#xff1a; username:admin password:dm1N123456r00t# 进行post传参…...

matlabR2021a正版免费使用

目录 matlab介绍&#xff1a; 安装&#xff1a; matlab介绍&#xff1a; MATLAB&#xff08;Matrix Laboratory的缩写&#xff09;是一种高级技术计算和编程环境&#xff0c;由MathWorks公司开发。它在科学、工程、数据分析和数学建模领域中广泛应用&#xff0c;为用户提供了…...

天气数据可视化平台-计算机毕业设计vue

天气变幻无常&#xff0c;影响着我们生活的方方面面&#xff0c;应用天气预报信息可以及时了解天气的趋势&#xff0c;给人们的工作、生活等带来便利&#xff0c;也可以为我们为未来的事情做安排和打算&#xff0c;所以一个精准的、易读 通过利用 程序对气象网站大量的气象信息…...

揭秘Java switch语句中的case穿透现象

揭秘Java switch语句中的case穿透现象 1. switch 语句简介2. case穿透现象的原因关于 goto 3. switch和if的区别4. 总结 导语&#xff1a;在 Java 开发中&#xff0c;我们经常使用switch语句来进行条件判断和分支选择。然而&#xff0c;有一个令人困惑的现象就是&#xff0c;当…...

Java-API简析_java.io.FilterOutputStream类(基于 Latest JDK)(浅析源码)

【版权声明】未经博主同意&#xff0c;谢绝转载&#xff01;&#xff08;请尊重原创&#xff0c;博主保留追究权&#xff09; https://blog.csdn.net/m0_69908381/article/details/134106510 出自【进步*于辰的博客】 因为我发现目前&#xff0c;我对Java-API的学习意识比较薄弱…...

C语言 每日一题 PTA 10.29 day7

1.特殊a串数列求和 给定两个均不超过9的正整数a和n&#xff0c;要求编写程序求a aa aaa⋯ aa⋯a&#xff08;n个a&#xff09;之和。 输入格式&#xff1a; 输入在一行中给出不超过9的正整数a和n。 输出格式&#xff1a; 在一行中按照“s 对应的和”的格式输出。 思路 n…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...