代码随想录刷题笔记(DAY2)

2023-12-29 04:15:53

今日总结:今天在学 vue 做项目,学校还有很多作业要完成,熬到现在写完了三道题,有点太晚了,最后一道题的题解明天早起补上。

Day 2

01. 有序数组的平方(No. 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.1 笔记

这道题我一开始是准备使用比较器根据绝对值排序来实现的,但是 Comparator<Integer> 是无法作用于 int[] 的,小小踩坑

然后回想起昨天的双指针思想,这道题可以通过两个分别指向负数和正数的,因为是非递减排序的,所以负数是按照绝对值非递增排序的,也就是前一个负数的绝对值一定大于后一个负数的绝对值,平方也同理。

所以不妨设置一个新数组来存储这些元素,利用 left 指针去遍历小于零的元素,right 指针去遍历大于零的元素,当遍历结束后(如果有)剩余的元素,也就是正数和负数个数不相等的情况,就按照绝对值的顺序继续放入新数组。

1.2 代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] resArr = new int[nums.length]; // 存储结果的新数组
        int index = resArr.length - 1; // 从后往前循环赋值新数组
        // 正数组直接返回结果
        if (nums[left] >= 0) {
            for (int i = 0; i < nums.length; i++) {
                nums[i] = nums[i] * nums[i];
            }
            return nums;
        }
        // left 索引负数部分,right 索引整数部分
        while (nums[left] < 0 && nums[right] >= 0) {
            if (Math.abs(nums[left]) > nums[right]) {
                resArr[index] = nums[left] * nums[left];
                index--;
                left++;
            } else if (Math.abs(nums[left]) < nums[right]) {
                resArr[index] = nums[right] * nums[right];
                index--;
                right--;
            } else {
                // 相等的情况,赋值两次
                resArr[index] = nums[left] * nums[left];
                index--;
                resArr[index] = nums[left] * nums[left];
                index--;
                left++;
                right--;
            }
        }
        if (nums[left] >= 0) {
            // 负数部分已经遍历完,处理正数部分
            for (int i = index; i >= 0; i--) {
                resArr[i] = nums[right] * nums[right];
                right--;
            }
        } else if (nums[right] < 0) {
            // 说明正数部分已经遍历完了
            for (int i = index; i >= 0; i--) {
                resArr[i] = nums[left] * nums[left];
                left++;
            }
        }
        return resArr;
    }
}

02. 长度最小的子数组(No. 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

2.1 笔记

这道题采用的是滚动数组的方法,所谓滚动数组就是不断的调节子序列的起始和终止的位置,从而得出我们想要的结果,首先要考虑的是我们遍历的是数组的起始位置还是终止位置,如果遍历的是起始位置的话那终止位置该如何确定?通过 for 循环继续向后遍历,来确定以每个元素为起始元素所得到的所有的子数组,这样就是暴力解法,显然时间复杂度是不符合题目要求的。

所以我们采用 for 循环遍历终止位置,那要考虑的就是,我们的起始位置该什么时候更新呢?很明显,当我们循环遍历直到这个数组的 sum 和大于等于题目中的 target 起始位置向后移动缩小范围,这样就避免了暴力解法中我们每到一个起始位置都要从头开始加和:通过起始位置的向后递增,这时候我们的 sum 应该等于原本的 sum 减去每次的 nums[i] **直到 **我们发现 sum < target 就再去更新终止位置的值,这样就实现了数组滚动前进的效果,遍历以 nums 中的每个元素作为结尾的所有子数组。

2.2 代码
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0; // 起点
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        for (int j = 0; j < nums.length; j++) {
            // 外层去循环遍历滑动窗口的终点,起点在找到符合的区间再更新
            sum += nums[j];
            // 一直使起始位置向后移动直到 sum < target 为止
            while (sum >= target) {
                // 更新最短的值
                minLen = Math.min(minLen, (j - i + 1));
                // 移动起始位置
                sum -= nums[i];
                i++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

03. 螺旋矩阵 II(No. 59)

给你一个正整数 n ,生成一个包含 1n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1:

输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入:n = 1
输出:[[1]]

3.1 笔记
3.2 代码
class Solution {
    public int[][] generateMatrix(int n) {
        int index = 0;
        int loop = 0; // 控制循环次数,总共需要遍历 n / 2 次
        // n 阶矩阵
        int[][] res = new int[n][n];
        int start = 0;
        int i, j; // 因为遍历另一条边的时候需要前一条边的结束位置,需要保存
        int count = 1; // 这是每次填充的数字
        while(loop++ < n / 2) {
            for (j = start; j < n - loop; j++) {
                // 区间是左闭右开的不遍历最后一个元素
                res[start][j] = count++;
            }
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }
        if (n % 2 == 1) {
            res[start][start] = count;
        }

        return res;
    }
}

文章来源:https://blog.csdn.net/weixin_74895237/article/details/135280688
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。