977.有序数组的平方

给你一个按 非递减顺序排序的整数数组 nums,返回 每个数字的平方组成的新数组,要求也按 非递减顺序排序。
输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为
[0,1,9,16,100]
思路1:平方后排序,排序的话第一反应考虑最简单的冒泡排序
class Solution { public int[] sortedSquares(int[] nums) { int[] NewArry=new
int[nums.length]; for(int i=0;i<nums.length;i++){ NewArry[i]=nums[i]*nums[i]; }
//冒泡排序 for(int i=0;i<NewArry.length;i++){ for(int j=i+1;j<NewArry.length;j++){
if(NewArry[i]>NewArry[j]){ int temp=NewArry[j]; NewArry[j]=NewArry[i];
NewArry[i]=temp; } } } return NewArry; } }
平方的过程很简单,遍历数组,给数据进行平方

冒泡排序的基本原理:

* 比较相邻的元素,如果前一个元素比后一个元素大,则交换位置
* 对每一对相邻元素做同样的工作,从开始第一对元素到结尾第一对元素,最终最后位置即为最大值。
该思路的缺点,冒泡排序需要双层1for循环,算法时间复杂度为O(N^2),适用于排序数量过少的时候,所以较浪费时间。

思路2:使用双指针

Day1进行过双指针的训练,但是看到这道题还是没有想起如何运用,看了部分解析之后明白了输入数组是有序的,平方之后也可以找到一定的规律,从左边和右边分别出发对比提高效率。
class Solution { public int[] sortedSquares(int[] nums) { int[] NewArry=new
int[nums.length]; int j=nums.length-1; int i=0; int index=nums.length-1;
while(i<=j){ if(nums[i]*nums[i]<=nums[j]*nums[j]){
NewArry[index--]=nums[j]*nums[j]; j--; }else{ NewArry[index--]=nums[i]*nums[i];
i++; } } return NewArry; } }
定义一个新数组NewArry,和nums数组一样的大小,让index指向NewArry数组终止位置。

如果nums[i]*nums[i]<=nums[j]*nums[j] 那么NewArry[index--]=nums[j]*nums[j],并且让j--

如果nums[i]*nums[i]>nums[j]*nums[j] 那么NewArry[index--]=nums[i]*nums[i],并且让i++

该算法的的时间复杂度为O(n)

209.长度最小的子数组

给定一个含有 n ****个正整数的数组和一个正整数 target **。**找出该数组中满足其和 ****≥ target **的长度最小的 连续子数组 
[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。**如果不存在符合条件的子数组,返回 0 。
输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
该题的思路也是双指针的一个扩展,刚开始做没办法确定结束的指针怎么处理,于是看了解析才有了思路。

滑动窗口:不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。

1、设置左右两个指针

2、又指针遍历数组,并将遍历到的数据相加

若while(sum≥target)(等号的必要性是为了确定最短子序列),移动左指针,并将左指针遍历到的数据减去在进行循环判断

3、最终找到最短子序列
class Solution { public int minSubArrayLen(int target, int[] nums) { int
left=0; int sum=0; int reslut=Integer.MAX_VALUE; for(int
right=0;right<nums.length;right++){ sum+=nums[right]; while(sum>=target){
reslut=Math.min(reslut,right-left+1); sum-=nums[left]; left++; } } return
reslut==Integer.MAX_VALUE?0:reslut; } }
刚开始不理解reslut=Integer.MAX_VALUE的必要性,到了后续才知道都是为了后续的比较,使用Math.min

59. 螺旋矩阵 II

给你一个正整数 n,生成一个包含 1到 n2所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
输入:n = 3 输出:[[1,2,3],[8,9,4],[7,6,5]]
这道题看似复杂,但并不需要复杂的推导只需要按照循环逐步去解决

* 上侧的从左到右 处理行(start,n-loop);列++
* 右侧的从上到下 处理列(start,n-loop); 行++
* 下侧的从右到左 处理行(接上侧最后的一列,loop);列—
* 左侧的从下到上 处理行(loop,2中最后处理的一行);行— class Solution { public int[][]
generateMatrix(int n) { int loop=0; //循环次数 int start=0; int[][] NewArray=new
int[n][n]; int i,j; int count=1; while(loop++<n/2){ //1.上面从左到右
for(j=start;j<n-loop;j++){ NewArray[start][j]=count++; } //2.右侧从上到下
for(i=start;i<n-loop;i++){ NewArray[i][j]=count++; } //3.下面从右到左
for(;j>=loop;j--){ NewArray[i][j]=count++; } //4.左边从下到上 for(;i>=loop;i--){
NewArray[i][j]=count++; } start++; } if(n%2==1){ NewArray[start][start]=count;
} return NewArray; } }
很多小细节点:

①这里循环次数是0所以一开始就要++

②当n是奇数的时候,最中间会出现一个最终累加的count需要记得添加

③行和列的变化不要搞错,可以画图让自己理清楚

④在循环之外定义了i,j所以1,2步循环结束后i,j是可以保存继续使用到3,4步骤

今日总结:难度比昨天的大了一些,但都是双指针的变形,切记将问题考虑复杂,需要简单化理解和处理,接下来不仅要完成每日题目,还要提高训练速度。

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信