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

news/2024/7/24 2:36:03 标签: 算法, 数据结构, leetcode

JAVA代码编写

leetcode.cn/problems/squares-of-a-sorted-array/">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;
    }
}

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

leetcode.cn/problems/minimum-size-subarray-sum/">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.长度最小的子数组


http://www.niftyadmin.cn/n/5125897.html

相关文章

众和策略可靠吗?股权除息是好是坏?

可靠 股权除息&#xff0c;指的是公司在股息发放前&#xff0c;将公司股票分拆&#xff0c;以减少股东持有的股份&#xff0c;添加每股的股息金额。简略来说&#xff0c;就是将股份拆成更小的比例&#xff0c;每股股息也随之添加。 股权除息关于股东来说&#xff0c;好坏参半…

MVC架构_Qt自己的MV架构

文章目录 前言模型/视图编程1.先写模型2. 视图3. 委托 例子&#xff08;Qt代码&#xff09;例1 查询本机文件系统例2 标准模型项操作例3 自定义模型示例:军事武器模型例4 只读模型操作示例例5 选择模型操作例6 自 定 义委 托(在testSelectionModel上修改) 前言 在Qt中&#xf…

基于51单片机的四种波形信号发生器仿真设计(仿真+程序源码+设计说明书+讲解视频)

本设计 基于51单片机信号发生器仿真设计 &#xff08;仿真程序源码设计说明书讲解视频&#xff09; 仿真原版本&#xff1a;proteus 7.8 程序编译器&#xff1a;keil 4/keil 5 编程语言&#xff1a;C语言 设计编号&#xff1a;S0015 这里写目录标题 基于51单片机信号发生…

Visual Studio远程连接Linux编译代码时,头文件在/usr/include中找不到,文件存在于/usr/include的子目录中

文章目录 1 问题的提出2 问题分析3 问题的解决 1 问题的提出 VS2022在编译数据安全传输平台时&#xff0c;远程连接到Centos上进行编译&#xff0c;但是提示找不到json头文件。 2 问题分析 在Linux系统下编译代码时&#xff0c;系统会主动到/usr/include目录主动搜索头文件。…

测试C#调用Vlc.DotNet组件播放视频

除了Windows Media Player组件&#xff0c;在百度上搜索到还有不少文章介绍采用Vlc.DotNet组件播放视频&#xff0c;关于Vlc.DotNet的详细介绍见参考文献1&#xff0c;本文学习Vlc.DotNet的基本用法。   VS2022中新建基于.net core的winform程序&#xff0c;在Nuget包管理器中…

Android stdio 无法新建或打开AIDL文件(解决方法)

1.在gradle文件中添加如下代码 2.AIDL要求minsdk>16,并且要使aidl true&#xff08;在Gradle中添加&#xff09; android{ buildFeatures { aidl true } } 我们看见&#xff0c;可以创建AIDL文件了 3.接着&#xff0c;我们看到文件出现如下提示 4.在gradle…

Hyperledger Fabric搭建测试网络

本文使用的Fabric版本&#xff1a;V2.5.4 Ubuntu系统&#xff1a;16.04LTS 前序文章已经详细介绍了如何安装部署Hyperledger Fabric系统&#xff0c;这里不再赘述。本篇文章主要介绍如何使用Fabric的测试网络。在正式开始之前&#xff0c;有一点需要说明&#xff1a; Hyperled…

前端访问geoserver服务发生跨域的解决办法,以及利用html2canvas下载绘制的地图

我的业务场景: 需要利用html2canvas下载Openlayers绘制的地图。 预期:可以下载成图片甚至其他格式(svg)文件。 结果:下载下来是个空白图片。 排查错误:请求数据正常回显到页面上,利用html2canvas截取的时候会发生跨域,导致无法绘制。 首先处理tomcat跨域问题 第一步…