代码随想录算法训练营第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;//每次更新子序列起始位置,就将子序列和置为0
            for (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.长度最小的子数组

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PDF编辑工具Acrobat Pro DC 2023中文

Acrobat Pro DC 2023是一款全面、高效的PDF编辑和管理软件。它提供了丰富的PDF编辑功能&#xff0c;如创建、编辑、合并、分割、压缩、旋转、裁剪等&#xff0c;让用户可以轻松处理各种PDF文档。同时&#xff0c;该软件还具有智能的PDF处理技术&#xff0c;可以自动识别和修复P…

中国铁路线路数据,分为高速铁路和普通铁路,有shp格式和xlsx格式,免费下载

数据地址&#xff1a; 中国铁路线路数据https://www.xcitybox.com/datamarketview/#/Productpage?id274 基本信息. 数据名称: 中国铁路线路数据 数据格式: ShpXlsx 数据时间: 2018年 数据几何类型: 线 数据坐标系: WGS84坐标系 数据来源&#xff1a;网络公开数据 数据…

Java 使用 poi 和 aspose 实现 word 模板数据写入并转换 pdf 增加水印

本项目所有源码和依赖资源都在文章顶部链接&#xff0c;有需要可以下载使用 1. 需求描述 从指定位置读取一个 word 模板获取业务数据并写入该 word 模板&#xff0c;生成新的 word 文档将新生成的 word 文档转换为 pdf 格式对 pdf 文档添加水印 2. 效果预览 word 模板 带水印的…

openpnp - SlotSchultzFeeder source code bugfix

文章目录 openpnp - SlotSchultzFeeder source code bugfix概述笔记openpnp源码调试环境排查思路开git分支查到的问题 - 1查到的问题 - 2查到的问题 - 3针对以上问题进行的逻辑修正D:\my_openpnp\openpnp_github\src\main\java\org\openpnp\machine\reference\driver\wizards\G…

Spark On Hive原理和配置

目录 一、Spark On Hive原理 &#xff08;1&#xff09;为什么要让Spark On Hive&#xff1f; 二、MySQL安装配置&#xff08;root用户&#xff09; &#xff08;1&#xff09;安装MySQL &#xff08;2&#xff09;启动MySQL设置开机启动 &#xff08;3&#xff09;修改MySQL…

用 Rust 和 cURL 库制作一个有趣的爬虫

目录 一、介绍 二、准备工作 三、代码实现 四、解析 HTML 并提取特定元素示例 总结 本文将介绍如何使用 Rust 编程语言和 cURL 库制作一个有趣的网络爬虫。我们将通过实例代码来展示如何抓取网页内容、处理数据和解析 HTML 结构。同时&#xff0c;还将探讨爬虫技术的原理、…

YOLOv5 添加 OTA,并使用 coco、CrowdHuman数据集进行训练。

YOLO-OTA 第一步&#xff1a;拉取 YOLOv5 的代码第二步&#xff1a;添加 ComputeLossOTA 函数第二步&#xff1a;修改 train 和 val 中损失函数为 ComputeLossOTA 函数1、在 train.py 中 首先添加 ComputeLossOTA 库。2、在 train.py 修改初始化的损失函数3、在 train.py 修改一…

ChatGPT 与 Python Echarts 完成热力图实例

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

YouTrack 中如何设置邮件通知

在 YouTrack 中&#xff0c;默认是不会邮件通知的。 你可以为你的账号设置邮件通知。 设置的方法为单击用户属性&#xff0c;然后在弹出的小窗口中选择属性选项。 设置邮件通知 在通知 Tab 页面中&#xff0c;选择发送邮件的方式&#xff0c;默认这个选项是不选择的。 用户…

IDEA 断点高阶

一、按钮介绍 1.1 补充 返回断点处&#xff1a; 设置debug配置&#xff1a; 二、增加/切换debugger视图 三、window快捷键 所在行处&#xff1a; CtrlF8断点属性编辑&#xff1a; CtrlShiftF8 四、一些常用的高级功能 4.1 查看对象内存-Attach memory agent 1.勾选Atta…

vscode下ssh免密登录linux服务器

vscode使用ssh免密登录linux 1、安装SSH插件2、生成密钥3、linux安装ssh服务4、linux下配置公钥5、vscode远程登录 注&#xff1a;测试环境为window10Ubuntu1804/Ubuntu2204 1、安装SSH插件 扩展->搜索SSH->点击install进行安装&#xff0c;如下图所示&#xff1a; 2、…

非小米笔记本小米妙享中心安装最新教程 3.2.0.464 兼容所有Windows系统

小米妙享中心 3.2.0.464 版本帮助 : 支持音频流转、屏幕镜像、屏幕拓展、键鼠拓展、无线耳机、小米互传 目录 小米妙享中心 3.2.0.464 版本帮助 : 1.常规教程使用安装包方式安装失败 或者 1.1安装失败可使用大佬的加载补丁方法解决 补充卸载残留 1.2 截图存档 2. 本教程…

原生JavaScript实现的SPA单页应用(hash路由)

什么叫做SPA单页应用 单页Web应用 &#xff08;single page web application&#xff0c;SPA&#xff09; &#xff0c;就是只有一张Web页面的应用&#xff0c;是加载单个HTML 页面并在用户与应用程序交互时动态更新该页面的Web应用程序。 单页应用的说法是在JavaScript和AJA…

每日一练——返回链表的中间结点

&#x1d649;&#x1d65e;&#x1d658;&#x1d65a;!!&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦ &#x1f44f;&#x1f3fb;‧✧̣̥̇:Solitary-walk ⸝⋆ ━━━┓ - 个性标签 - &#xff1a;来于“云”的“羽球人”。…

Nginx 的配置文件(负载均衡,反向代理)

Nginx可以配置代理多台服务器&#xff0c;当一台服务器宕机之后&#xff0c;仍能保持系统可用。 cmd查找端口是否使用&#xff1a;netstat -ano Nginx出现403 forbidden #解决办法&#xff1a;修改web目录的读写权限&#xff0c;或者是把nginx的启动用户改成目录的所属用户&…

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

大纲 标量函数入参并非表中一行&#xff08;Row&#xff09;入参是表中一行&#xff08;Row&#xff09;alias PyFlink中关于用户定义方法有&#xff1a; UDF&#xff1a;用户自定义函数。UDTF&#xff1a;用户自定义表值函数。UDAF&#xff1a;用户自定义聚合函数。UDTAF&…

Go学习第十章——文件操作,Json和测试

Go文件操作&#xff0c;Json和测试 1 文件1.1 基本介绍1.2 读取的基本操作1.3 写入的基本操作1.4 使用案例(三个) 2 Go语言的Json使用2.1 序列化案例2.2 反序列化案例 3 单元测试3.1 先看个需求3.2 快速入门3.3 入门总结 1 文件 1.1 基本介绍 文件在程序中是以流的形式来操作…

使用Jenkins触发gitlab的webhook

满足条件&#xff1a; 首先手动构建可以完成构建 例如&#xff1a; 打开项目点击配置 在“Build Triggers”栏勾选&#xff0c;Build when a change is pushed to GitLab. GitLab webhook &#xff1b;如下 复制URL链接&#xff0c;我的链接是&#xff1a;http://192.168.44…

HarmonyOS鸿蒙原生应用开发设计- 流转图标

HarmonyOS设计文档中&#xff0c;为大家提供了独特的流转图标&#xff0c;开发者可以根据需要直接引用。 开发者直接使用官方提供的流转图标内容&#xff0c;既可以符合HarmonyOS原生应用的开发上架运营规范&#xff0c;又可以防止使用别人的图标侵权意外情况等&#xff0c;减…

【每日一题】切割后面积最大的蛋糕

文章目录 Tag题目来源题目解读解题思路方法一&#xff1a;排序 其他语言python3 写在最后 Tag 【排序】【数组】【2023-10-27】 题目来源 1465. 切割后面积最大的蛋糕 题目解读 切割后面积最大的蛋糕。 解题思路 方法一&#xff1a;排序 本题较为简单&#xff0c;找出最大…