代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II

简介: 代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II

1. LeetCode 977.有序数组的平方

1.1 自己的思路:

  1. 将数组每个元素平方
  2. 然后冒泡排序
  3. 但怕这样效率太低过不了,但还是过了

1.2 代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        //将数组元素平方
        for(int i=0;i<nums.length;i++){
            nums[i]=nums[i]*nums[i];
        }
        //冒泡排序
        for(int i=0;i<nums.length-1;i++){
            for(int j=0;j<nums.length-1-i;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
        }
        return nums;
    }
}

1.3 双指针思路

  1. 为什么想到的呢?
  2. 因为对于题目的数组中的元素平方后,一定会呈现于两边大中间小的情况,因为有负数嘛,这样可以用两个指针逐步向中间靠拢得到一个由大到小的数组
  3. 创建一个新数组result,k=nums.length-1,元素从右往左更新
  4. 定义左指针(i)右指针(j)放入循环中,只有左指针在右指针左边(i<=j)就继续循环,为什么要有=呢?假如两指针相遇时如果没有=就退出循环了,就会落下了那个元素就没有更新
  5. i什么时候++,取决于最大值是不是在i那个位置,j什么时候--取决于那个值是否要取j那个位置的元素
  6. 比较i和j两个位置的值哪个大,把大的放入result的k位置,然后k--,取了i位置的元素i就++,取了j位置的元素j就--

1.4 代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        //创建一个新的数组,长度和原来一样
        int[] result=new int[nums.length];
        //定义一个指针k,从右往左给result添加元素
        int k=nums.length-1;
        //定义左指针i,右指针j,只要左指针在右指针左边包括相遇都继续执行
        for(int i=0,j=nums.length-1;i<=j;){//为什么要<=呢?因为没有等于的话相遇后就落下了相遇的元素
            if(nums[i]*nums[i]>nums[j]*nums[j]){//左指针的元素平方后更大
                result[k--]=nums[i]*nums[i++];//将平方后元素放入,然后k--,i++
            }else{//右指针的元素平方后更大
                result[k--]=nums[j]*nums[j--];//将平方后元素放入,然后k--,j--
            }
        }
        return result;
    }
}

2. LeetCode 209.长度最小的子数组

2.1 自己的思路

       说实话,没思路,我开始以为会是贪心,但贪心我也不会啊

2.2 滑动窗口(双指针)思路

  1. j表示滑动窗口的起始还是终止位置呢?可以假设是起始,但如果是这样的话那么求和时终止位置就要把j后面所有的元素都遍历一遍才能又回到j这个位置,这样跟暴力求解思路是一样的,所以j应该表示终止位置
  2. 关键在如何移动起始位置,j随着for循环后移,当sum大于等于target时起始位置就可以移动了,当sum大于等于target时滑动窗口就形成了
  3. 形成滑动窗口后就求窗口的长度,subL=j-i+1,result应该在result和subL中取个最小值作为长度最小的子数组,然后sum总和要减去nums[i]这个起始位置的值
  4. 中间条件(sum>=target)前是写if还是while呢?举个例子:假如数组[1,1,1,100,...],target=100,只有[1,1,1,100]这部分符合大于等于target的,如果写if,那么只去掉了一个1,还没有达到最短,只有写while才能求得最后的子数组长度为1,也就是[100]这个数组

2.3 代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //i为起始位置,左指针
        int i=0;
        //将长度设置为数组长度+1
        int result=nums.length+1;
        int sum=0;
        //j为终止位置,右指针
        for(int j=0;j<nums.length;j++){
            //先求sum,从起始到终止的和
            sum+=nums[j];
            while(sum>=target){
                //在result中和j-1+1取个最小值
                result=Math.min(result,j-i+1);
                //sum减去起始位置的值,然后起始位置后移
                sum-=nums[i++];
            }
        }
        //如果长度仍为数组长度+1,则说明没有符合target条件,则返回0
        return result==(nums.length+1)?0:result;
    }
}

3. LeetCode 59. 螺旋矩阵 II

3.1 自己的思路

       尝试过把图画出后找找看能不能发现数学上的规律,结果不能

3.2 二分法思路

  1. 遍历每条边的规则是左闭右开还是左闭右闭呢?按道理都可以
  2. 如果是按照左闭右开的规则呢?处理最上面的边的时候从左至右除了最后一个节点就都处理了,就是处理每一条边的时候都只是处理第一个节点到最后倒数第二个节点也就是最后一个节点不处理,留给下一条边
  3. 我们定义loop为要转的圈数,loop=n/2的,可以画个正方形的图,然后按照题意模拟转圈就可以知道要转多少圈了
  4. 我们定义startX、startY为0作为每一圈的起始位置,到下一圈了就++
  5. 我们定义offset=1来控制每条边遍历的长度,每转了一圈就++,含义就是从左至右以及从上至下遍历的时候距离边界的距离为1
  6. 当n为奇数时按照我们上面的定义是少转了一圈,差了中间位置的值,因此定义mid=n/2,表示中间位置,循环结束后直接赋值

3.3 代码

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res=new int[n][n];
        int startx = 0, starty = 0; // 作为每一圈的起始位置,到下一圈了就++
        int loop = n / 2; // 表示要转的圈数
        int mid = n / 2; // 矩阵中间的位置
        int count = 1; 
        int offset = 1; // 控制每条边遍历的长度,每转了一圈就++
        int i,j;
        while (loop!=0) {
            i = startx;
            j = starty;
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }
            //已经转了一圈了,起始位置要+1
            startx++;
            starty++;
            // offset 控制每一圈里每一条边遍历的长度,每转一圈就++,距离边界的距离+1
            offset++;
            //转的圈数-1
            loop--;
        }
        // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
        if (n % 2==1) {
            res[mid][mid] = count;
        }
        return res;
    }
}

4. 数组总结

目录
打赏
0
0
0
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
127 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
67 3
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等