代码随想录算法训练营第二天 | 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. 数组总结

相关文章
|
6天前
|
机器学习/深度学习
leetcode代码记录(旋转图像
leetcode代码记录(旋转图像
10 0
|
6天前
|
算法
leetcode代码记录(全排列 II
leetcode代码记录(全排列 II
13 4
|
6天前
|
算法
leetcode代码记录(全排列
leetcode代码记录(全排列
12 1
|
6天前
|
索引
leetcode代码记录(Z 字形变换
leetcode代码记录(Z 字形变换
12 1
|
6天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0
|
6天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
12 0
|
6天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
25 4
【刷题】 leetcode 面试题 08.05.递归乘法
|
6天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
27 5
【刷题】 leetcode 面试题 01.06 字符串压缩
|
6天前
|
存储 算法 测试技术