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

代码随想录算法训练营第2天| 977有序数组的平方、209长度最小的子数组。

JAVA代码编写

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题

文章讲解:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

视频讲解: https://www.bilibili.com/video/BV1QB4y1D7ep

方法一:暴力排序

思路:遍历数组中的元素,算出平方和,再调用函数排序即可。

复杂度分析:取决于排序的复杂度

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
  • 空间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
class Solution {public int[] sortedSquares(int[] nums) {for (int i = 0; i < nums.length; i++) {nums[i]*=nums[i];}Arrays.sort(nums);return nums;}
}

方法二:双指针法

思路:因为输入的数组是递增的,平方操作后的最大值只可能在数组两边,此时,只需要比较两边的数,找到最大的数,依次进行比较。

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
class Solution {public int[] sortedSquares(int[] nums) {int left=0;int right=nums.length-1;int k=nums.length-1;int[] resuslt=new int[nums.length];//定义一个新的数组,存放结果while(left<=right){if(nums[left]*nums[left] > nums[right]*nums[right]){resuslt[k]=nums[left]* nums[left];//result[k]赋值为较大的值k--;//result[k]赋值完后,k要相对于减一进行下一次赋值left++;//左指针右移}else{resuslt[k]=nums[right]*nums[right];k--;right--;//右指针左移}}return resuslt;}
}

其他写法:

class Solution {public int[] sortedSquares(int[] nums) {int right = nums.length - 1;int left = 0;int[] result = new int[nums.length];int index = result.length - 1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {// 正数的相对位置是不变的, 需要调整的是负数平方后的相对位置result[index--] = nums[left] * nums[left];++left;} else {result[index--] = nums[right] * nums[right];--right;}}return result;}
}
class Solution {public int[] sortedSquares(int[] nums) {int l = 0;int r = nums.length - 1;int[] res = new int[nums.length];int j = nums.length - 1;while(l <= r){if(nums[l] * nums[l] > nums[r] * nums[r]){res[j--] = nums[l] * nums[l++];}else{res[j--] = nums[r] * nums[r--];}}return res;}
}

这两个写法,只是在++和–上有简化代码作用,使得代码更为简洁。

209. 长度最小的子数组

给定一个含有 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)) 时间复杂度的解法。

文章讲解:https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

视频讲解:https://www.bilibili.com/video/BV1tZ4y1q7XE

方法一:暴力解法

思路:两层for循环,第一层表示子序列的起始位置,第二层表示子序列的结束位置,计算子序列起始位置到终止位置的和sum,如何和sum大于等于target,就计算当前子序列的长度,与初始长度,比较,找最小的长度。找不到的话返回0。

复杂度分析

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {public int minSubArrayLen(int target, int[] nums) {int subLength=0;//子序列的长度int result=Integer.MAX_VALUE;//将result定义为最大值int sum=0;//子序列的和for (int i = 0; i < nums.length; i++) {//子序列起始位置i(下标)sum=0;//每次更新子序列起始位置,就将子序列和置为0for (int j = i; j < nums.length; j++) {//子序列结束位置j(下标)sum+=nums[j];//计算子序列的和if (target<=sum ){subLength=j-i+1;result=result<subLength?result:subLength;//result=min(subLength,result)break;}}}return result == Integer.MAX_VALUE ? 0 : result;//result没有被赋值,就说明不存在这样的子序列,返回0}
}

方法二:滑动窗口

思路:用一个循环干方法一的事,方法一是从子序列的起始位置开始变量的,这里我们从子序列的结束位置开始往前遍历。

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {public int minSubArrayLen(int target, int[] nums) {int left=0;int result=Integer.MAX_VALUE;//将result定义为最大值int sum=0;//子序列的和for(int right=0;right < nums.length; right++){sum+=nums[right];while(sum>=target){result= result<(right-left+1)?result:(right-left+1);sum-=nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}

这里还是以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:

209.长度最小的子数组

相关文章:

代码随想录算法训练营第2天| 977有序数组的平方、209长度最小的子数组。

JAVA代码编写 977. 有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,100] 解释&…...

微信小程序通过startLocationUpdate,onLocationChange获取当前地理位置信息,配合腾讯地图解析获取到地址

先创建个getLocation.js文件 //获取用户当前所在的位置 const getLocation () > {return new Promise((resolve, reject) > {let _locationChangeFn (res) > {resolve(res) // 回传地里位置信息wx.offLocationChange(_locationChangeFn) // 关闭实时定位wx.stopLoc…...

C/C++字符三角形 2020年12月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析

目录 C/C字符三角形 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C字符三角形 2020年12月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 给定一个字符&#xff0c;用它构造一个底边长5个字…...

Python数据挖掘:入门、进阶与实用案例分析——基于非侵入式负荷检测与分解的电力数据挖掘

文章目录 摘要01 案例背景02 分析目标03 分析过程04 数据准备05 属性构造06 模型训练07 性能度量08 推荐阅读赠书活动 摘要 本案例将根据已收集到的电力数据&#xff0c;深度挖掘各电力设备的电流、电压和功率等情况&#xff0c;分析各电力设备的实际用电量&#xff0c;进而为电…...

基于 Qt控制开发板 LED和C语言控制LED渐变亮度效果

## 资源简介 在STM32开发板,板载资源上有两个可自由控制的 LED。如下图原理 图其中我们以操作 LED1 为示例,LED1 为出厂系统的心跳指示灯。 ## 应用实例 想要控制这个 LED,首先出厂内核已经默认将这个 LED 注册成了 gpio-leds类型设备。所以我们可以直接在应用层接口直接…...

Android 11.0 禁用插入耳机时弹出的保护听力对话框

1.前言 在11.0的系统开发中,在某些产品中会对耳机音量调节过高限制,在调高到最大音量的70%的时候,会弹出音量过高弹出警告,所以产品 开发的需要要求去掉这个音量弹窗警告功能 2.禁用插入耳机时弹出的保护听力对话框的核心类 frameworks\base\packages\SystemUI\src\com\and…...

微信小程序案例2-3:婚礼邀请函

文章目录 一、运行效果二、知识储备&#xff08;一&#xff09;导航栏配置&#xff08;二&#xff09;标签栏配置&#xff08;三&#xff09;vw、vh单位&#xff08;四&#xff09;video组件&#xff08;五&#xff09;表单组件&#xff08;六&#xff09;Node.js概述 三、实现…...

K8S部署Dashboard

获取recommended.yaml文件 Dashboard是官方提供的一个UI&#xff0c;可用于基本管理K8s资源。 YAML下载地址&#xff1a; wget https://raw.githubusercontent.com/kubernetes/dashboard/v2.4.0/aio/deploy/recommended.yaml如果网络错误无法直接下载&#xff0c;可以直接访问…...

【OJ比赛日历】快周末了,不来一场比赛吗? #10.29-11.04 #7场

CompHub[1] 实时聚合多平台的数据类(Kaggle、天池…)和OJ类(Leetcode、牛客…&#xff09;比赛。本账号会推送最新的比赛消息&#xff0c;欢迎关注&#xff01; 以下信息仅供参考&#xff0c;以比赛官网为准 目录 2023-10-29&#xff08;周日&#xff09; #3场比赛2023-10-30…...

常用应用安装教程---在centos7系统上安装Docker

在centos7系统上安装Docker 1&#xff1a;切换镜像源 wget https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo -O /etc/yum.repos.d/docker-ce.repo2&#xff1a;查看当前镜像源中支持的docker版本 yum list docker-ce --showduplicates | sort -r3&#x…...

CTFHub-SSRF-读取伪协议

WEB攻防-SSRF服务端请求&Gopher伪协议&无回显利用&黑白盒挖掘&业务功能点-CSDN博客 伪协议有&#xff1a; file:/// — 访问本地文件系统 http:/// — 访问 HTTP(s) 网址 ftp:/// — 访问 FTP(s) URLs php:/// — 访问各个输入/输出流(I/O streams) dic…...

推荐一款适合科技行业的CRM系统

推荐您一款科技行业好用的CRM系统——Zoho CRM客户管理系统&#xff0c;旨在帮助企业管理客户数据、销售过程、营销活动以及服务支持&#xff0c;助力业务增长及数字化转型&#xff0c;实现“以客户为中心”的企业管理和运营模式。 近些年&#xff0c;随着政府鼓励政策的出台、…...

ChatGPT 与 Python Echarts 完成热力图实例

热力图是一种数据可视化方式&#xff0c;它通过颜色的变化来表示数据的差异和分布。以下是使用热力图的一些作用和好处&#xff1a; 数据可视化&#xff1a;热力图可以将复杂的数据集转化为更直观、更易理解的形式。这对于很多人来说&#xff0c;尤其是那些没有深入统计学或数…...

vue3项目报错The template root requires exactly one element.eslint-plugin-vue

解决方案&#xff1a; 1.禁用 Vetur 并改用Volar》它现在是 Vue 3 项目的官方推荐。【必须重启vsCode】 从官方迁移指南&#xff1a; 建议使用带有我们官方扩展 Volar (opens new window) 的 VSCode&#xff0c;它为 Vue 3 提供了全面的 IDE 支持。 2.package.json文件中 &…...

【C++系列】STL容器——vector类的例题应用(12)

前言 大家好吖&#xff0c;欢迎来到 YY 滴C系列 &#xff0c;热烈欢迎&#xff01;本章主要内容面向接触过C的老铁&#xff0c;下面是收纳的一些例题与解析~ 主要内容含&#xff1a; 目录 【例1] 只出现一次的数字i&#xff08;范围for与模等&#xff08;^&#xff09;)【例2]…...

常用应用安装教程---在centos7系统上安装JDK8

在centos7系统上安装JDK8 1&#xff1a;进入oracle官网下载jdk8的tar.gz包&#xff1a; 2&#xff1a;将下载好的包上传到每个服务器上&#xff1a; 3&#xff1a;查看是否上传成功&#xff1a; [rootkafka01 ~]# ls anaconda-ks.cfg jdk-8u333-linux-x64.tar.gz4&#xf…...

阿里云/腾讯云国际站代理:国际腾讯云的优势

国际腾讯云具有以下优势&#xff1a; 1. 全球覆盖&#xff1a;腾讯云在全球拥有30个区域&#xff0c;覆盖6个大洲&#xff0c;能够提供全球范围的云服务&#xff0c;满足不同地区用户的需求。 2. 大规模网络&#xff1a;腾讯云拥有庞大的全球网络&#xff0c;包括多个高速骨干…...

【软件教程】如何用C++检查TCP或UDP端口是否被占用

一、检查步骤 使用socket函数创建socket_fd套接字。使用sockaddr_in结构体配置协议和端口号。使用bind函数尝试与端口进行绑定&#xff0c;成功返回0表示未被占用&#xff0c;失败返回-1表示已被占用。 二、CODE 其中port需要修改为想要检测的端口号&#xff0c;也可以将代码…...

Flutter报错RenderBox was not laid out: RenderRepaintBoundary的解决方法

文章目录 报错问题分析问题原因 解决办法RenderBox was not laid out错误的常见原因常见原因解决方法 RenderRepaintBoundaryRenderRepaintBoundary用途 报错 RenderBox was not laid out: RenderRepaintBoundary#d4abf relayoutBoundaryup1 NEEDS-PAINT NEEDS-COMPOSITING-BI…...

0基础学习PyFlink——用户自定义函数之UDAF

大纲 UDAF入参并非表中一行&#xff08;Row&#xff09;的集合计算每个人考了几门课计算每门课有几个人考试计算每个人的平均分计算每课的平均分计算每个人的最高分和最低分 入参是表中一行&#xff08;Row&#xff09;的集合计算每个人的最高分、最低分以及所属的课程计算每课…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

JDK 17 新特性

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

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...