首页 > 编程语言 >【每日一道算法题】有序数组的平方、长度最小的子数组

【每日一道算法题】有序数组的平方、长度最小的子数组

时间:2024-04-02 23:59:25浏览次数:28  
标签:平方 窗口 nums int 算法 数组 指针

文章目录

有序数组的平方

写在前面

本人是一名在java后端寻路的小白,希望记录此博客来帮助自己理解和日后复习,希望也能够帮助到你。

题目

力扣题目链接

给你一个按 非递减顺序 排序的整数数组 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]
思路解析
暴力解法

这道题目给了一个数组,当中的元素是非递减的(非递减表示元素可能递增,也可能当中有重复值,不算严格的递增),要求把元素进行平方,并且也进行非递减排序。

最容易想到的方法,也就是暴力解法,就是将每个元素进行平方,然后对平方后得到的数组使用Arrays类当中的sort方法直接进行排序。

但是一瞬间竟不知如何返回数组的平方。。菜狗如我

双指针法

采用双指针是因为数组平方之后,最大值最有可能出现在数组两端,最不可能出现在数组中间。(因为数组是非递减的,而且存在负数,所以在平方之后最大值肯定出现在两端)。根据这个想法,我们可以采用双指针,一个指针start指向起始索引,一个指针end指向末尾索引,然后判断这两个指针指向的数哪一个的平方更大,指针指向的元素的平方更大的一者用倒序添加的方式添加到新数组的末尾,然后该指针向中间移动一位,另一个指针不动,继续进行下一次比较。

我的代码
暴力解法
class Solution {
    public int[] sortedSquares(int[] nums) {
        //先创建新的数组,长度等同于旧数组
        int[] newArr = new int[nums.length];
        //对旧数组中的元素进行平方,然后赋值给新数组的对应位置上的元素
        for(int i = 0; i < nums.length; i++){
            newArr[i] = nums[i]*nums[i];
        }

        //直接调用类Arrays中的sort方法对新数组进行排序
        Arrays.sort(newArr);
        //返回新数组
        return newArr;
        
    }
}
双指针法
class Solution {
    public int[] sortedSquares(int[] nums) {
        //双指针法,一个指针i指向数组的起始索引,一个指针j指向数组的末尾索引length-1
        int i = 0;
        int j = nums.length - 1;
        int k = nums.length - 1;
        //定义一个新数组,长度等于老数组
        int[] newArr = new int[nums.length];

        //指针移动的循环结束条件,两者相遇表示最后一个元素,此时这个元素是需要写入新数组中的
        while(i <= j){
            //比较两个指针指向的元素的平方
            //假如i指针指向元素的平方更大,那么将其写进新数组的末尾元素,i指针向后移动,j指针不动
            if(nums[i]*nums[i] > nums[j]*nums[j]){
                newArr[k] = nums[i]*nums[i];
                i++;
                k--;
            }
            //假如j指针指向元素的平方更大或者相等,那么将其写进新数组的末尾元素,j指针向前移动,i指针不动
            else{
                newArr[k] = nums[j]*nums[j];
                j--;
                k--;
            }
        }

        return newArr;

    }
}
参考答案解法
暴力方法
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }
}


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

长度最小的子数组

原题

力扣题目链接

给你一个按 非递减顺序 排序的整数数组 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]
思路解析
暴力法

这题我没有采用暴力法,直接采用了滑动窗口(感觉滑动窗口的思想反而更直观一些)。暴力法是用两次for循环,初始化子数组的最小长度为无穷大,第一个for循环遍历数组 nums 中的每个下标作为子数组的开始下标,对于每个开始下标 i,需要找到大于或等于 i 的最小下标 j,使得从 nums[i] 到 nums[j]的元素和大于或等于 s,并更新子数组的最小长度(此时子数组的长度是 j−i+1)

滑动窗口法

滑动窗口其实就是双指针的变种。窗口其实就是一个连续的子数组,定义两个指针,一个指针start指向窗口的开始索引,一个指针end指向窗口的末尾索引,这两个指针最开始都指向数组的0索引。

滑动窗口法的过程就是,end指针通过一个for循环遍历逐步扩大窗口,start指针保持不动,end每扩大一次,就判断start~end窗口当中的元素总和是否大于目标值target。如果窗口的总和大于目标值,那么start指针就往前移动一位,目的是寻找是否存在潜在的长度更小的而且符合要求的子数组。

怎么求窗口的元素和,这里也是我当时临时想出来的。就是在一开始定义一个变量sum,表示窗口元素的总和。在end指针往前走、而start指针保持不动的时候,每当end向前走一位、窗口扩大一格的时候,窗口元素的总和就往前追加;而每次start往前走一位,窗口元素的总和就减去原来start指针指向的那个元素。

我的代码

我忘记考虑了数组长度为0的情况,这时候需要直接返回0。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //滑动窗口解法,定义窗口的起始指针和末尾指针
        int i = 0;
        int j = 0;
        //定义一个变量来存储窗口的和
        int sum = 0;
        //定义一个变量记录最小的窗口长度
        int shortest = nums.length + 1;
        //用一个for循环中的i指针表示窗口的末尾索引,用j指针表示窗口的起始索引
        for(i = 0; i < nums.length; i++){
            sum = sum + nums[i];

            //判断窗口当中所有元素的和是否大于等于目标值
            while(sum >= target){
                //窗口元素和大于目标值
                //判断,如果窗口的长度=1,说明此时是最小长度,直接返回1
                if(i-j+1 == 1){
                    return 1;
                }
                //如果子数组的长度不是1,说明还可能存在潜在的最小窗口长度,此时j++
                else{
                    //如果此时窗口长度小于最小窗口长度,则将此时窗口的长度赋值给最小长度
                    if(i-j+1 < shortest){
                        shortest = i-j+1;
                    }
                    sum = sum - nums[j];
                    j++;
                }
            }
            //如果窗口之和不符合条件,则i继续++,然后给窗口之和加上i指向的最新的值,随后继续判断
        }
        
        if(shortest == nums.length + 1){
            return 0;
        }
        return  shortest;   
    }
}
官方题解
滑动窗口法
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

标签:平方,窗口,nums,int,算法,数组,指针
From: https://blog.csdn.net/m0_69580082/article/details/137250740

相关文章

  • array_merge 和 [] 追加元素在处理数组时的区别
    $array1=[['id'=>1,'name'=>'商品A','quantity'=>2],['id'=>2,'name'=>'商品B','quantity'=>1],];$array2=[['id'=>3,�......
  • Java(对象数组与继承性的一些特点)
    1.数组是语言中重要的一种数据类型,我们常用于大型数据处理,当我们需要创建某类的许多对象,为了提高效率,Java中提供了对象数组,即将对象作为引用类型。a.使用对象数组时必须为每个元素赋值;b.构建对象数组时与平常数组构造相似,类名[]数组名=new类名[对象个数];2.代码展示—......
  • 几种常见的路径规划算法
    几种常见的路径规划算法路径规划是机器人、自动驾驶车辆、无人机等领域中的关键技术之一,它涉及到如何为移动实体找到从起点到终点的最优或可行路径。随着技术的不断发展,路径规划算法也在不断进步和优化。下面将介绍几种常见的路径规划算法。1.Dijkstra算法Dijkstra算法是一......
  • 几种嵌入式中常见的滤波算法
    在嵌入式系统开发中,滤波算法是不可或缺的一部分,用于从带有噪声的数据中提取有用信息,提高数据质量,并减少错误决策的可能性。下面将介绍几种在嵌入式系统中常见的滤波算法。1.移动平均滤波(MovingAverageFilter)移动平均滤波是一种简单的滤波算法,通过计算一定窗口内数据点的平......
  • 嵌入式工程师常用的几种算法
    嵌入式工程师常用的几种算法嵌入式系统在现代电子设备中无处不在,从简单的家电到复杂的工业控制系统,都离不开嵌入式技术的支持。作为嵌入式工程师,掌握一些常用的算法对于提高系统性能和优化资源利用至关重要。本文将介绍几种嵌入式工程师常用的算法。1.排序算法排序算法在嵌......
  • 代码随想录算法训练营第38天|理论基础|509. 斐波那契数 |70. 爬楼梯 |746. 使用最小花
    代码随想录算法训练营第38天|理论基础|509.斐波那契数|70.爬楼梯|746.使用最小花费爬楼梯详细布置今天正式开始动态规划!理论基础无论大家之前对动态规划学到什么程度,一定要先看我讲的动态规划理论基础。如果没做过动态规划的题目,看我讲的理论基础,会有感觉是不......
  • 算法题:经商(并查集+01背包)
    链接:经商来源:牛客网题目描述小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段,当然人际关系是需要放在首位的。小d每一个月都需要列出来一个人际关系表,表示他们搞房地产的人的一个人际关系网,但是他的精力有限,对应他只能和能够接触到的人交际。比如1认识2,2认识3,那......
  • 简单算法-1
    先来先淘汰(FIFO)packagecom.itheima.release;importjava.util.Iterator;importjava.util.LinkedList;publicclassFIFO{LinkedList<Integer>fifo=newLinkedList<Integer>();intsize=3;//添加元素publicvoidadd(inti){f......
  • 简单算法-2
    计数器packagecom.itheima.limit;importjava.util.concurrent.*;publicclassCounter{publicstaticvoidmain(String[]args){//计数器,这里用信号量实现finalSemaphoresemaphore=newSemaphore(3);//定时器,到点清零Sc......
  • 粒子群算法(主要针对连续型函数优化问题)
    文章主要参考了以下博文:https://zhuanlan.zhihu.com/p/5648197181.简介粒子群算法是一种解决最优化问题的通用方法,其优点是求解速度快,数值相对稳定,算法简单。粒子群算法分为连续型粒子群算法和离散型粒子群算法,分别用于解决连续型问题和离散型问题。粒子群优化算法源自对鸟......